CODEWITHSUNDEEP
algorithmsearchmemorypath
Maricruzz
Maricruzz

Reputation: 405

Breadth First Search implementation

I am trying to make an implementation of Breadth First Search (also other algorithms, but currently bfs) in Javascript.

Eventually I want to apply all the search algorithms on a grid, to find a path from the start to the goal node (I know bfs isn't particularly good at this). I have made an implementation, but the problem is that I do not have the entire tree in advance. What I want is to give it a startnode and endnode and based on that find a path between them.

The problem I am running into is that when I determine the adjacent grid-squares, it returns ALL neighbors, so even the ones that are already traversed. Which turns it into graph search rather than tree search. A way to solve it is to remember all paths so that I can check which neighbors have already been traversed and thus should not need to be examined further. However, as I learned in a course on search algorithms, bfs has a memory usage of all nodes on the current depth level. If I store all the paths, then it consumes much more memory than that right?

Is it possible to only keep in memory the nodes of the current depth that bfs is searching on, when I don't have the tree structure in advance and still avoid having cycles?

I hope I have made my self clear.

Thanks in advance, Stefan

Upvotes: 3

Views: 941

Answers (1)

amit
amit

Reputation: 178481

If you will "forget" the nodes you visit, you might get into the same troubles DFS encounters - it is not optimal (might not find the optimal path) nor complete (due to infinite loops, it might not find a solution even though one exist).

Note that:

  • Even if you remember only the deepest level nodes - it still doesn't help you much - remember that in a binary tree, for instance, half of the nodes are leaves, so space complexity will still be huge.
  • Remembering only part of the nodes does not guarantee optimality, because eventually you will rediscover a vertex you have forgotten - and by then - you got yourself into a loop.

If you are looking for more memory efficient algorithm that is both complete and optimal - an Iterative Deepening DFS might be what you are after.

Upvotes: 1

Related Questions