Ch 3 - Show why Depth-Limited and Iterative-Deepening search is useful

[redblobgames]

The book says we would use depth-limited or iterative-deepening search when the tree is large (maybe infinite), and breadth first search would use too much memory. It might be useful to make that comparison in these two diagrams by showing how much memory is used by breadth first search vs depth limited search.

[Dragneel7]

@redblobgames Can we show this by using the Romania example of the book by visualizing both the algorithms side by side depicting their queue side by sides and as we have prior knowledge of the data type of the node we can calculate the amount of memory space that would be required at each insertion or deletion of a node and showing that value to the reader to help them compare ?

[redblobgames]

I think the number of nodes in the queue is a fine proxy for the amount of memory, and it would be easier to understand than number of bytes.

The Romania example might work. It is fairly small though, and I don't know if iterative deepening will be that much different for small graphs. We might need a much larger graph to show the difference. I don't know :)

[Dragneel7]

@redblobgames That makes sense, implementing the above in a small graph want be much help.
Maybe we can form an larger graph and show it, but it will have a problem due to limited width of the screen.

[redblobgames]

I agree, a larger graph might work. The bidirectional search graph shows hundreds of nodes; something like that might work to show the concept of iterative deepening.

[HitRam]

As far as I understand, iterative deepening DFS has the following advantages -

1. It uses less space as compared to BFS.
2. It finds correct level of the goal node as BFS does and where DFS fails.

So I think, we can have 3 graphs similar to those in bidirectional BFS, one showing that Iterative deepening finds correct level of goal node in lesser space. Other showing BFS on similar graph, but requires more space and the last one showing DFS and stating that the level number of goal node found is not correct.

How can we show more / less space?

One possible solution is highlighting the nodes that will be in OPEN list. I have implemented something similar for my college project. So more the highlighted nodes, more is the space required and vice versa.