BFS algorithm in python

Question

I am working on a project that requires me to implement the BFS algorithm using Python, which I am new to.

The algorithm finishes execution of a 9 pieces puzzle (3x3), but it takes a really large amount of time to do so (5 minutes):

def bfs(self):

    fringe = deque([])
    # start it
    fringe.append(self.stateObj.getState())

    while len(fringe) > 0:
        state = fringe.popleft()
        self.visited.append(state)

        # just for tracing
        # self.helper.drawBoard(state)

        if self.stateObj.isCurrentStateGoalTest(state):
            return True

        for next_state in self.stateObj.getNextStates(state):
            if (next_state not in (self.visited + list(fringe))):
                fringe.append(next_state)

Can anybody point out what I could improve this to achieve better performance? Any practical answer is well accepted.

Answer 1

The problematic part is probably this: if (next_state not in (self.visited + list(fringe))) This will a) create a new list from fringe, b) create another new list from that list and visited, c) iterate the entire list to see whether the next state is already in.

It seems like self.visited is a list. Make it a set instead, so the in check takes only O(1) instead of O(n). Also, in BFS you can add the elements to visited right in the next_state loop, so you don't have to check whether they are in the fringe, as well.

def bfs(self):
    fringe = deque([self.stateObj.getState()])
    while fringe:
        state = fringe.popleft()
        if self.stateObj.isCurrentStateGoalTest(state):
            return True
        for next_state in self.stateObj.getNextStates(state):
            if next_state not in self.visited:
                fringe.append(next_state)
                self.visited.add(next_state)

If that's not enough, I suggest using A* instead, using the number of misplaced tiles as a heuristic function.