Labyrinth: Breadth-first search and plotting search trees

Previous:

1. random-labyrinths
2. labyrinth-complexity

In the previous post we investigated how a depth-first search fares in a labyrinth with N nodes. We showed that:

• A good model for a search cost is to take the number of passed edges. That is equal to 1 times the number of edges in the found path, plus 2 times the remaining visited edges. 
• Worst case cost is 2*N if the end node is a leaf node. If end is not a leaf node, disregard all nodes which are not connected to start, if we remove end. 
• The average case cost is N-1, independently of the labyrinth (but assuming that end is a leaf node).

Let's move on to breadth-first search. BFS is predictable in that we know that if end has a depth of k, then all nodes with depth lower than k will be expanded before end. This allows us to make the following evil example:

A labyrinth where BFS will always get a maximal score.

So when end is on the opposite side from the start, it is easy to "break" the BFS algorithm. When end is in another place, it is not obvious what the labyrinth that forces the greatest search cost for BFS is. We will see this problem developed later.

To help us see how different algorithms work, we can plot the search trees:

For a given labyrinth, BFS always gets about the same score.

DFS is sometimes really lucky...

And other times very unlucky!

DFS was implemented as:

BFS was implemented as:

The implementations of BFS and DFS are very similar. The underlying idea for both algorithms is similar: save nodes in a data structure and apply a decision for which node to expand next.