Tree search

Search algorithms

Search algorithms

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.

Types of nodes in a search algorithm

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.

Travelling salesman problem

Shortest path problem

Tree search algorithms

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.

Informed: No

Time: \(O(b^d)\)

Space: \(O(b^d)\)

Complete: Yes

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

Informed: No

Time: \(O(b^m)\)

Space: \(O(bm)\)

Complete: Yes

Optimal: No

Depth-first search with a limit. This is useful if we know the solution is shallower than limit \(l\).

Informed: No

Time:

Space:

Complete:

Optimal:

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.

Informed: No

Time:

Space:

Complete:

Optimal:

Search algorimths with different costs

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

Informed: No

Time: \(O(b^{?})\)

Space: \(O(b^{?})\)

Complete: Yes

Optimal: Yes