search

aimacode / aima-javascript

Javascript visualization of algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"
http://aimacode.github.io/aima-javascript/
MIT License
541 stars 219 forks source link

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

Open redblobgames opened 6 years ago

redblobgames commented 6 years ago

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 commented 6 years ago

@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 commented 6 years ago

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 commented 6 years ago

@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 commented 6 years ago

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 commented 6 years ago

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.