Search Algorithms

Navigating a hedge maze

Imagine waking up in the middle of a vast, intricate hedge maze. The air is crisp, and you are completely surrounded by towering hedges that seem to stretch endlessly in every direction. The maze is filled with numerous twists, turns, and dead ends. You have no map, no sense of direction, and no visible landmarks to guide you. All you can do is choose a path at each junction, hoping to find your way out. You must make decisions at every turn: left, right, or straight. The question is: which path will lead you to the exit?

You try to apply what you know, decide a rule to stay either left or right whenever you reach the junction. The maze may contain loops where turning left leads you back to the same place, or dead ends where you end up trapped. Without a way to recognize and avoid these, you could end up endlessly circling or stuck in a dead end. We need an algorithm that promises us a way out, which considers the loops, dead ends, the history of visited places.

Search algorithms

A search algorithm is a method for exploring the search space and finding a path from the initial state to the goal state. Search algorithms can help solve complex problems where traditional logic fails. There are two major categories: informed (heuristic) search algorithms and uninformed (blind) search algorithms. Let’s briefly go through the basic terminology and its types.

Terms

Let's begin by clarifying the key terminology essential for understanding search algorithms.

• Search space: The search space is the entire set of possible states or configurations that a problem can have. In a maze, the search space consists of all the positions you could potentially occupy as you navigate through the maze. For chess, the search space consists of all possible board configurations that can arise from any sequence of legal moves in the game.

• State: A state represents a specific configuration or situation within the search space at any given moment. For a maze, a state typically includes your current position, the set of visited positions, and any other relevant information. A state in chess is a specific arrangement of pieces on the board at any given moment.

• Initial state: The initial state is the starting configuration of the problem. In a maze, this would be your starting position. The initial state in chess is the standard starting position, with all pieces arranged in default positions at the beginning of the game.

• Goal state: The goal state is the desired final configuration that solves the problem. In a maze, this would be the exit point. In chess, the goal state could be achieving checkmate, where the opponent's king is in a position to be captured with no legal moves to prevent it.

• Transition: A transition is moving from one state to another, such as moving from one intersection to the next in a maze. In chess, a transition occurs when a player moves, changing the board's configuration from one state to another.

• Path: A path is a sequence of states (or nodes) connected by edges, representing a series of actions that lead from the initial state to the goal state. In chess, a path is a sequence of moves from the initial board setup to the current position, possibly leading to checkmate.

Remember being stuck in the maze, trying to find your way out? To navigate such a maze efficiently, we need a strategy that handles twists, turns, and dead ends effectively. The A* algorithm offers a robust solution by blending two key techniques: it employs a heuristic to estimate the distance to the goal and tracks the actual cost of the path taken. This combination allows A* to intelligently explore the maze, striking a balance between finding the shortest route and avoiding unnecessary detours.

A* search

The A* algorithm is a popular pathfinding and graph traversal algorithm used in various applications, such as computer games, robotics, and network routing. It efficiently finds the shortest path from a start node to a goal node by combining aspects of Dijkstra's algorithm and Greedy Best-First Search. The algorithm uses a heuristic to guide its search, making it more efficient than algorithms that do not use heuristics.

The core of the A* algorithm relies on a cost function that combines two main components:

• G-score (Cost from Start): The cost of the path from the start node to the current node.

• H-score (Heuristic Cost to Goal): The estimated cost from the current node to the goal node.

Cost function

The total cost function,  ...