AI Lab 7

1. Best-First Search: The Nearest Apple

Problem Scenario:

Spider-Man needs to find the minimum number of steps to reach the nearest apple cart ('A') from his starting position ('S') on a city grid. The grid contains obstacles (buildings represented by '#'). He can move up, down, left, or right.

Sample Input


Grid:
[
  ['S', '.', '.', '#', '.', '.'],
  ['.', '#', '.', '#', '.', '#'],
  ['.', '#', '.', '.', '.', '.'],
  ['.', '.', '#', '#', '.', '.'],
  ['#', '.', '#', 'A', '.', '#']
]

Expected Output


Minimum steps required: 9


# Define a helper function to calculate Manhattan distance (our heuristic)
def manhattan_distance(p1, p2):
    # p1 and p2 are tuples like (row, col)
    # Calculate and return the absolute difference of coordinates

# Main search function
def best_first_search(grid):
    # Find start ('S') and apple ('A') positions
    
    # Initialize a priority queue to store (heuristic_cost, steps, current_position)
    # The priority queue will automatically sort by the first element (heuristic_cost)
    
    # Initialize a 'visited' set to keep track of visited cells
    
    # Add the starting position to the priority queue with 0 steps
    
    # Loop while the priority queue is not empty:
        # Get the cell with the smallest heuristic cost from the queue
        
        # If this cell is the apple, return the number of steps taken
        
        # If this cell has been visited, continue to the next iteration
        
        # Mark the current cell as visited
        
        # Explore neighbors (up, down, left, right):
            # For each neighbor, check if it's a valid move (within grid, not an obstacle)
            # If valid, calculate its heuristic cost to the apple
            # Add (heuristic_cost, new_steps, neighbor_position) to the priority queue
            
    # If the loop finishes and the apple wasn't found, return -1

Example: Navigating from Bhagalpur to Patna

Find the most promising path from Bhagalpur to Patna using straight-line distance (heuristic) to guide the search.

Best-First Search is a **greedy algorithm**. It always chooses the next node that *appears* to be closest to the goal, based on the heuristic value. It doesn't consider the cost of the path taken so far.

Step 1: Start at Bhagalpur (Heuristic: 210km). Add its neighbors, Munger (H:160) and Banka (H:240), to a priority queue.
Step 2: The queue is now [(160, Munger), (240, Banka)]. The algorithm greedily chooses Munger because its heuristic is lower.
Step 3: From Munger, explore its neighbors (Lakhisarai, Begusarai). Lakhisarai (H:110) is more promising than Begusarai (H:125). The queue now contains [(110, Lakhisarai), (125, Begusarai), (240, Banka)].
Step 4: The algorithm again picks the best option: Lakhisarai (H:110). Its neighbor is Patna (H:0).
Step 5: Patna is the goal (H:0). The search stops and returns the path found.


import heapq

def solve_bihar_navigation_example():
    # Road connections between cities
    graph = {
        'Bhagalpur': ['Munger', 'Banka'],
        'Munger': ['Begusarai', 'Lakhisarai'],
        'Banka': ['Munger'],
        'Begusarai': ['Patna'],
        'Lakhisarai': ['Patna'],
        'Patna': []
    }
    
    # Heuristic: Approx. straight-line distance to Patna in km
    heuristics = {
        'Bhagalpur': 210, 'Munger': 160, 'Banka': 240,
        'Begusarai': 125, 'Lakhisarai': 110, 'Patna': 0
    }
    
    start = 'Bhagalpur'
    goal = 'Patna'

    pq = [(heuristics[start], [start])] # (heuristic, path)
    visited = set()

    while pq:
        h, path = heapq.heappop(pq)
        current_city = path[-1]

        if current_city == goal:
            return f"Path found: {' -> '.join(path)}"

        if current_city in visited:
            continue
        visited.add(current_city)
        
        for neighbor in graph[current_city]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                heapq.heappush(pq, (heuristics[neighbor], new_path))
                
    return "Path not found"

# Expected Output: Path found: Bhagalpur -> Munger -> Lakhisarai -> Patna

2. Beam Search: Tracking Villains

Problem Scenario:

Spider-Man is tracking multiple leads to find a villain's lair. He starts at a location ('A') and explores connected locations (nodes). To be efficient, he uses Beam Search with a beam width of 2. This means at each level of his search, he only considers the 2 most promising paths based on heuristic values (estimated distance to the goal).

Sample Input


Graph Heuristics (estimated distance to Goal 'G'):
A: 10, B: 8, C: 9, D: 6, E: 4, F: 5, G: 0

Connections:
A -> B, C
B -> D, E
C -> F, G

Beam Width (β): 2
Start Node: 'A'
Goal Node: 'G'

Expected Output


Path Found: ['A', 'C', 'G']


# Main beam search function
def beam_search(graph, heuristics, start, goal, beam_width):
    # Initialize the beam with the starting path: [(heuristic, [path_nodes])]
    # For the start node, this would be [(heuristics[start], [start])]
    
    # Loop until the goal is found or the beam becomes empty
        # Create a list to store all possible next paths (candidates)
        
        # For each path in the current beam:
            # Get the last node of the path
            
            # If the last node is the goal, return this path
            
            # For each neighbor of the last node:
                # Create a new path by extending the current path
                # Calculate the heuristic of the neighbor
                # Add (heuristic, new_path) to the candidates list
        
        # If no candidates were generated, the search fails
        # Sort the candidates based on their heuristic values (ascending)
        
        # Select the top 'beam_width' candidates to form the new beam
        # This is the "pruning" step
        
    # If the loop finishes, no path was found

Example: Food Delivery Route Planning

A delivery agent needs a route from 'Sabor' to 'Tilkamanjhi'. To quickly find a good-enough route, they use Beam Search with a width (β) of 2.

Beam Search is a compromise between greedy search and breadth-first search. It explores multiple paths at once, but limits how many paths it keeps at each step (the "beam width").

Level 1: Start at Sabor. Neighbors are Zero Mile (H:8) and Adampur (H:10). Since β=2, both paths are kept. The beam is now [Path to Zero Mile, Path to Adampur].
Level 2 Candidates: We generate all next steps from our beam.
- From Zero Mile -> Sandis Compound (H:5)
- From Adampur -> Manali Chowk (H:6), Kotwali Chowk (H:4)
This gives us 3 candidate paths.
Level 2 Pruning: The candidates are sorted by heuristic: Path to Kotwali (H:4), Path to Sandis (H:5), Path to Manali (H:6). Since β=2, we **keep the best two** (Kotwali, Sandis) and **prune the path to Manali Chowk**.
Level 3: From Kotwali and Sandis, we explore their neighbors. The path to the goal, Tilkamanjhi (H:0), is found via Kotwali Chowk.


def solve_delivery_example():
    graph = {
        'Sabor': ['Zero Mile', 'Adampur'],
        'Zero Mile': ['Sandis Compound'],
        'Adampur': ['Manali Chowk', 'Kotwali Chowk'],
        'Sandis Compound': ['Tilkamanjhi'],
        'Manali Chowk': [],
        'Kotwali Chowk': ['Tilkamanjhi'],
        'Tilkamanjhi': []
    }
    heuristics = {
        'Sabor': 12, 'Zero Mile': 8, 'Adampur': 10, 'Sandis Compound': 5,
        'Manali Chowk': 6, 'Kotwali Chowk': 4, 'Tilkamanjhi': 0
    }
    start = 'Sabor'
    goal = 'Tilkamanjhi'
    beam_width = 2

    beam = [(heuristics[start], [start])]

    while beam:
        candidates = []
        for h, path in beam:
            last_node = path[-1]
            if last_node == goal:
                return f"Path Found: {' -> '.join(path)}"
            
            for neighbor in graph.get(last_node, []):
                new_path = path + [neighbor]
                candidates.append((heuristics[neighbor], new_path))
        
        if not candidates: break
            
        candidates.sort(key=lambda x: x[0])
        beam = candidates[:beam_width]
        
    return "Path not found"

# Expected Output: Path Found: Sabor -> Adampur -> Kotwali Chowk -> Tilkamanjhi

Return to Archives