Pathfinding & AI Search Algorithms: Best-First, Breadth-First, Depth-First, A*

Understanding Core AI Search Algorithms

Best-First Search

If the node that receives the best evaluation is expanded first, then we are performing a Best-First Search. This algorithm expands what appears to be the best option according to its evaluation function. This function takes into account all nodes seen so far to make its decision.

Breadth-First Search

Breadth-First Search evaluates each node at a certain level before moving on to the next level. It is an optimal algorithm, seeking the shortest solution path.

How Breadth-First Search Works

It searches the entire graph or sequence without considering the goal until it is found. This algorithm does not use a heuristic. From an algorithmic point of view, all child nodes obtained by expanding a node are added to a FIFO (First-In, First-Out) queue.

Depth-First Search

Depth-First Search is an algorithm that recursively traverses all nodes of a graph or tree in an orderly, but not uniform, manner. Its operation involves expanding each node it encounters, recurrently, in a specific way. When there are no more nodes in the current path, it backtracks, repeating the process for each branch node that has not yet been processed.

Generic Heuristic Search Pseudocode

This pseudocode illustrates a general heuristic search approach, similar to Best-First Search, where nodes are expanded based on an evaluation function f':

OPEN: = [INITIAL]; CLOSED: = [], f'(START): = h'(INITIAL)
repeat
    if OPEN = [] then FAILURE
    // No nodes left
    MEJORNODO extract from OPEN with f' minimum
    // Priority queue
    Move MEJORNODO from OPEN to CLOSED
    if MEJORNODO contains estado_objetivo then
        SOLUCION_ENCONTRADA: = TRUE
    else
        Generate Successors for MEJORNODO
        for each successor do TRATAR_SUCESOR
until SOLUCION_ENCONTRADA or FAILURE

The A* Algorithm

The A* algorithm takes into account both the heuristic value of nodes and the real cost of the path traversed. This algorithm uses an evaluation function f(n) = g(n) + h(n), where:

• h(n) is the heuristic value estimating the cost from the current node n to the goal.
• g(n) is the real cost of the path to reach node n from the start.

A* maintains two auxiliary data structures: an 'open' list (typically a priority queue) and a 'closed' list, where information about visited nodes is stored. The algorithm is often described as a combination of Dijkstra's algorithm (which uses g(n) for breadth-first exploration) and greedy best-first search (which uses h(n) for depth-first tendencies). This balance shifts as it seeks out the most convenient path nodes.

This algorithm is complete, meaning it will find a solution if one exists. To ensure that A* is optimal (i.e., finds the minimum cost path), the heuristic function h(n) must be admissible. If this condition is not met, the algorithm would not guarantee finding the minimum cost path.

A* Algorithm Pseudocode

While the specific pseudocode for A* was not provided in the original document, its operation follows the general structure of a heuristic search (like the one above), but with the specific evaluation function f(n) = g(n) + h(n) used for prioritizing nodes in the 'open' list.