0

So I understand breadth first search, but I am having trouble with the implementation. When there are multiple branches you are expanding the edges or successors of each branch on every iteration of the function. But when one of your nodes returns GOAL how do you get all of the previous moves to that location?

Do you create a list of actions you took, and if there is a fork in the path you create two new lists with the actions you took to get to the branch, plus the moves you will take while on the branch?

This is a pain in the butt to implement, especially in Python, in which I'm fairly new too. Is there a better way to organize this and get the path I need?

Seitaridis
  • 4,459
  • 9
  • 53
  • 85
ForgottenOne
  • 85
  • 1
  • 4
  • 16
  • possible duplicate of [Breadth-first search trace path](http://stackoverflow.com/questions/8922060/breadth-first-search-trace-path) – jruizaranguren Oct 01 '14 at 07:46

1 Answers1

0

I found the answer. The split lists was a bad idea. I used linked lists instead. You can create a class called "Node" then connect the nodes yourself. Once of the properties of the node is the parent node. With the parent node, you can track all the way back up the tree. Look into linked lists.

ForgottenOne
  • 85
  • 1
  • 4
  • 16