2

I'm attempting to implement BFS in Python, I understand how the algorithm works but I don't have much programming experience. I've spent hours thinking about the best way to represent everything and how to be as efficient as possible. I've been unable to figure out how to get the path from my start node, to goal node.

I've spent ages googling around and looking at other peoples implementation of the algorithm, but my application is slightly different and this confuses me. When people are implementing BFS, they are assuming they have a graph given to them (as does the wikipedia article on BFS). In my problem, I have an initial state and a goal state I want to reach, but no graph or tree so I'm generating the nodes as I go.

For example:

def BFS(initial, goal):

    q = [initial]
    visited = []

    while q:
        n = q.pop()
        states = generate_states(n)

        for state in states:
            if state == goal:
                pass #placeholder
            q.append(state)
            visited.append(state)

It's not properly fleshed out because I'm having trouble with something, I'm not sure what it specifically is either... If initial and goal are nodes, and I write a struct type class elsewhere in my code such as:

class node:
    state = None
    parent = None

I think this is a suitable way to represent a node. So when I pop a node object off my queue, it has information regarding where it originated which will be initialized by the generate_states function. Then the for loop will append each of these new nodes onto the queue, and visited queue and it will repeated under one of the generated nodes has a state which matches my goal state.

Now that I've found the goal node, I have a list of visited nodes, but if I trace the path the path backwards from the goal node, aren't I slowing down the algorithm? Once a goal has been found I would look at its parent, locate its parent in the visited list, then look at the parent of the parent, etc... until I had a path = [node object, node object, ...] from the initial node to the goal node.

This brings me to another problem, when I create a node object it only lasts for one iteration of the while loop. How am I meant to store the objects in an array, they will each need a unique name and there is no obvious way (to me) to do this. This was the problem I mentioned earlier that I wasn't sure about. So it looks like I'm creating nodes but then only storing the node.state in the queue, which is pointless because I require the node object to access node.parent...

Why am I finding this so difficult, am I missing something obvious or making this too complicated?

Thanks for reading.

Improve this question
0

3 Answers 3

Reset to default
1

I can't comment on most of this, as I don't fully understand what you're trying to do - as you say, normally a BFS would have the graph there already, so I'm not sure how you are proposing to construct it as you go. But I must reply to this bit:

How am I meant to store the objects in an array, they will each need a unique name

This is definitely false. There is absolutely no need to give something a name if you just want to store it in a list - you can just append it. If you're worried about being able to find it later, then the normal thing to do with graphs is just give each node a number, via a single counter that you increase each time you define one. Again, if you're just storing the nodes in a list, then they automatically get a unique number: their position in the list.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

There is an initial state and a goal state and a finite number of operators. I'm not given a graph, as you say, I must construct it as I go which is done by applying a set operations which I'm using the function generate_states(n), where n is a node. Eventually, I'll iterate through each state and end up with a tree, which terminated at the goal node. I'm trying to understand how to do this, then trace backwards from the goal node to find a path in the tree. Sorry if this is even more confusing.
0

Your approach looks fine to me.

For getting the discovery path you can keep track of each nodes parent, e.g. give it a attribute that is set to the node that discovered it. That way you have a linked list that traces back the discovery path. For walking back once you reached the goal you can do

def get_parents(node):
    if node.parent is None:
        return []

    yield node.parent
    get_parents(node)

For keeping track of the nodes generated (variable n), just put the nodes you discover in the lists, not just the states.

    n = q.pop()
    states = generate_states(n)

    for state in states:
        m = node()
        m.state = state
        m.parent = n
        if state == goal:
            pass #placeholder
        q.append(m)
        visited.append(m)
Improve this answer

Comments

0

In general, what you have is fine.

There are a couple of confusions, which I will try to explain. First, you can store the node in a queue, not a state and since a node has a parent you can get to the previous nodes, so you have not lost them. Second, tracing back through parents is not something you need to worry about for efficiency - you only do it when you have a success (also, no need for names - sounds like you are confusing lists with maps?).

So the only thing missing from your code is that you are not creating your nodes. When you get a state, create a node, and save the node, instead of saving the state. Then everything will work.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.