Rauf

Key Concepts in Search:

• Initial State: The starting point of the agent (e.g., current location in navigation).
• Actions: The choices the agent can make (e.g., moving to a neighboring state).
• Transition Model: Describes how actions result in new states.
• State Space: All possible states the agent can reach.
• Path Cost: The cost (e.g., time, distance) of a path between states.

Solving Search Problems

To solve search problems, we use the frontier, a mechanism to manage the nodes in a search process. Nodes store information about the state, the parent node, the action taken to reach the node, and the path cost. The algorithm explores nodes by following specific strategies, such as Depth-First Search (DFS) or Breadth-First Search (BFS).

Search Algorithms

Depth-First Search (DFS):

• Data Structure: Stack (LIFO).
• Strategy: Explore as deeply as possible along one branch before backtracking.
• Pros: Fast if the solution is found early in the right branch.
• Cons: Can be inefficient and may not find the optimal solution.

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[-1]
        self.frontier = self.frontier[:-1]
        return node

Breadth-First Search (BFS):

• Data Structure: Queue (FIFO).
• Strategy: Explore all directions at the same depth before moving deeper.
• Pros: Guaranteed to find the optimal solution.
• Cons: Can be slower than DFS.

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[0]
        self.frontier = self.frontier[1:]
        return node

Greedy Best-First Search:

• Data Structure: Priority Queue.
• Strategy: Expand the node closest to the goal, based on a heuristic.
• Pros: Efficient when a good heuristic is available.
• Cons: May not find the optimal solution.

A* Search:

• Data Structure: Priority Queue.
• Strategy: Combines the cost so far (g(n)) and the estimated cost to the goal (h(n)).
• Pros: More optimal than Greedy BFS, as it considers both path cost and heuristic.
• Cons: Relies on the quality of the heuristic.

Heuristics: Manhattan Distance

A common heuristic used in search algorithms, especially in grid-based pathfinding, is the Manhattan Distance. It measures the number of steps required to move from one point to another, ignoring obstacles and calculating based on vertical and horizontal movement.

def manhattan_distance(start, goal):
    return abs(start[0] - goal[0]) + abs(start[1] - goal[1])