Too many nodes expanded in BFS graph search

Question

I am solving a problem for an AI course and I have to implement a graph search with the BFS algorithm in Python. My implementation actually finds the solution, but it expands too many nodes. The answer says that 269 nodes should be expanded, but I got 275.

To keep track of the visited nodes I use a dictionary. The keys are the expanded states and the values are 1. Once I get a node's successors, I check if they are present in the dictionary. If yes, I just ignore this successor. If not, I push it into the fringe (queue). I thought that this process would prevent expanding already visited nodes, but it doesn't seem to be the case.

Anyone could give me a hint about this? No code should be needed, as all I want is some idea of what might be going wrong.

Thanks in advance.

Answer 1

Not a lot of information to go on, but I suspect the following is your problem. You have to add the nodes to the visited dictionary as soon as they are added to the fringe queue. If you wait until you visit them (i.e. when they reach the head of the fringe queue) then you might have the same node in the fringe queue twice.

Also don't forget to add the start node to the visited dictionary.