A search algorithm takes a grid and identifies a path from a start point to an end point. Each node in the grid has connections to other nodes, with costs of moving between nodes.
In each search algorithm there are three types of nodes: unexplored nodes, explored nodes and frontier nodes. At the start of the algorithm the start node is explored, each node connected to the start node is a frontier node, and all other nodes are unexplored nodes.
When an algorithm explores a frontier node, it is added to the explored nodes, and all new nodes are added to the frontier nodes.
A breadth-first search operates First-in First-out (FiFo). That is, it selects the oldest frontier node. This results in a broad, rather than a deep search. Once all branches have been explored, the algorithm will move deeper. Path cost is not considered in this algorithm.
Optimal: Picks the shallowest solution. Optimal of path costs are identical.
A depth-first search operates Last-in First-out (LiFo). That is, it selects the newest frontier node. This results in a deep, rather than a broad search. Once the maximum depth has been reached, the algorithm will move towards breadth. Path cost is not considered in this algorithm.
May not find optimal solution, but is linear in space
Depth-first search with a limit. This is useful if we know the solution is shallower than limit \(l\).
Does a depth-limited search to a layer \(L\), increases the layer and starts again. The repeats are a waste, but earlier layers are much cheaper.
Modify BFS to prioritise cost not depth. expand node with lowest path cost. could be “deep”.
This is the same as Dijkstra’s algorithm.
Can do this in algo by using heaps