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.

tobias_k · Accepted Answer · 2017-02-09 16:24:07Z

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.

Shafayet Karim · Accepted Answer · 2023-11-25 21:05:53Z

-1

very basic code ig

import queue

adj = { 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }


def bfs(vertex, adj):
  vis = []
  q = queue.Queue()
  popped_res = []
  q.put(vertex)
  vis.append(vertex)

  while q.qsize() != 0:
    top = q.get()
    popped_res.append(top)
    for child in adj[top]:
      if child in vis:
        continue
      vis.append(child)
      q.put(child)


  return popped_res

print(bfs(0, adj))

answered Nov 25, 2023 at 21:05

Shafayet Karim

12 bronze badges

Collectives™ on Stack Overflow

BFS algorithm in python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related