How can I modify the breadth-first search algorithm to also include the solution path?
I have the following pseudo-code in my book for a breadth-first search:
function breadth_first_search:
begin
open := [Start]
closed := [];
while open != [] do
begin
remove leftmost state from open, call it X;
if X is a goal then return SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open;
end
end
return FAIL;
end
I've implemented a similar algorithm myse开发者_StackOverflow中文版lf following these pseudo-code instructions. My question is, what is the simplest way to modify it so it maintains the solution path?
Simply knowing I can reach a solution isn't nearly as useful as having a list of transitions to get to the solution.
Set Parent[childNode] = currentNode
as you enqueue each node (when you set Visible[Node] = 1
).
Then recursively look up the Parent
array, starting at the node you want and append each node you see in the Parent
array to the path. Parent[root]
is nil
and the recursion will stop there.
Is there any possibility for you to change the Tree structure? If so, you might want to add a parent
pointer in each node/leaf so when you find the solution you go up following parent pointers up to the root.
精彩评论