Алгоритм BFS в python

Question

Я работаю над проектом, который требует от меня реализовать алгоритм BFS с использованием Python, для которого я новичок.

Алгоритм завершает выполнение головоломки 9 штук (3х3), но это требует очень большого количества времени, чтобы сделать это (5 минут):

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) 

Кто-нибудь может указать на то, что я мог бы улучшить этот для достижения лучшей производительности? Любой практический ответ хорошо принят.

Answer 1

Проблемная часть, вероятно, это: if (next_state not in (self.visited + list(fringe))) Это будет а) создать новый список из fringe, б) создать другой новый список из этого списка и visited, в) перебирать весь список, чтобы увидеть ли следующее состояние уже в.

Похоже, self.visited является list. Сделайте вместо этого set, поэтому проверка in принимает только O (1) вместо O (n). Кроме того, в BFS вы можете добавить элементы в visited прямо в цикле next_state, поэтому вам не нужно проверять, находятся ли они в fringe.

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) 

Если этого не достаточно, я предлагаю использовать вместо A*, используя число неуместных плитки в качестве эвристической функции.