CODEWITHSUNDEEP
algorithmsearchartificial-intelligence
Pete
Pete

Reputation: 784

Uninformed search: run breadth-first search followed by iterative deepening search on each node in the frontier

I am trying to combine breadth first search and iterative deepening search. This approach is mentioned in the AI book, AI - A modern approach, chapter 3 (pg. 90). The idea is starting from the initial state, run breadth-first search until some constant memory limit mB is reached, and then run iterative deepening search on each node in the frontier.

Is this search algorithm sound? Complete? Optimal?

Upvotes: 0

Views: 284

Answers (1)

Dennis Soemers
Dennis Soemers

Reputation: 8488

Breadth-First Search itself is sound, complete, and optimal. So, for any problem where the BFS already finds a solution before the memory limit is reached, there are no problems. We'll only have to consider what happens in the cases where the memory limit is reached before finding a solution, e.g. problems where you will start running IDS on nodes in the frontier:

Sound?

Yes, IDS will never somehow return a result that is not correct.

Complete?

This depends on how you implement "IDS on each node in the frontier".

If you first do a complete IDS on the first node in the frontier, then a complete IDS on the second node in the frontier, etc., it will not be complete. Consider the case where there is an infinitely-sized search space under the first node in your frontier, which does not contain the solution. If you try to run a "complete" IDS on that node first, it will never terminate.

However, if you spread out your IDS processes over the nodes in the frontier in a different manner, it can be complete. For instance, if you first do a DFS up to depth 1 for all nodes in the frontier, then a DFS up to depth 2 for all nodes in the frontier, etc., the algorithm will be complete.

Optimal?

The same counts here as for completeness. If you complete a full IDS for the first node in the frontier before moving on to the second node, you may have found a suboptimal solution below the first node in the frontier already, so the algorithm will be suboptimal.

If you complete DFS processes with a depth limit of 1 for all nodes in the frontier before moving on to a DFS process with a depth limit of 2 for any node in the frontier, and complete all of those before moving to a depth limit of 3, etc., the algorithm will be optimal.

Upvotes: 1

Related Questions