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
Informed: No
Time: \(O(b^m)\)
Space: \(O(bm)\)
Complete: Yes
Optimal: No
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.