Может найти путь с помощью DFS, но не может указать правильные направления для Pacman _ Python

Question

Я работаю над заданием, найденным на странице курса ИИ на сайте Беркли, для развлечения. Мне нужно написать поиск в глубину для игры pacman, чтобы она могла найти свой путь. Проблема в том, что pacman застревает. Сначала я вставлю код, чтобы было понятнее:

import util

class SearchProblem:
  """
  This class outlines the structure of a search problem, but doesn't implement
  any of the methods (in object-oriented terminology: an abstract class).

  You do not need to change anything in this class, ever.
  """

  def getStartState(self):
     """
     Returns the start state for the search problem 
     """
     util.raiseNotDefined()

  def isGoalState(self, state):
     """
       state: Search state

     Returns True if and only if the state is a valid goal state
     """
     util.raiseNotDefined()

  def getSuccessors(self, state):
     """
       state: Search state

     For a given state, this should return a list of triples, 
     (successor, action, stepCost), where 'successor' is a 
     successor to the current state, 'action' is the action
     required to get there, and 'stepCost' is the incremental 
     cost of expanding to that successor
     """
     util.raiseNotDefined()

  def getCostOfActions(self, actions):
     """
          actions: A list of actions to take

     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     util.raiseNotDefined()


def tinyMazeSearch(problem):
  """
      Returns a sequence of moves that solves tinyMaze.  For any other
  maze, the sequence of moves will be incorrect, so only use this for tinyMaze
  """
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  return  [s,s,w,s,w,w,s,w]

def depthFirstSearch(problem):

  """
  Search the deepest nodes in the search tree first [p 74].

  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm [Fig. 3.18].

  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:

  print 'Start:', problem.getStartState()
  print 'Is the start a goal?', problem.isGoalState(problem.getStartState())
  print 'Start's successors:', problem.getSuccessors(problem.getStartState())

  """

  # *** YOUR CODE HERE ***


  start = [problem.getStartState()]
  for item in start:
      Open=[item]
  State=[]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) is True:
      return State
  else:
       while Open:
                visit= Open.pop()
                Closed.append(visit)
                if State: 
                  Path.append(State.pop())

                if problem.isGoalState(visit) is True:
                    print Closed
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            it=iter(index)
                            data=it.next()

                            if data not in Closed :
                              Open.append(data)
                              State.append(it.next())
                            else:
                              print Path

Теперь, если вы прочтете мой код в разделе dfs, вы увидите, что открытый список содержит все пункты, которые я посещал и расширил.

Файл Path содержит направление, заданное для pacman. Проблема возникает, когда я сталкиваюсь с условием, что оба преемника, которых я получаю, не посещаются, мой pacman выбирает путь, который ведет в тупик, поэтому он должен вернуться. Мой Open делает это и находит решение, но я не могу найти способ, как указать направления возврата в моем списке путей. Если вы перейдете на http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html, скачаете zip и вставите мой код в search.py в разделе dfs search, вы поймете мою проблему.

Answer 1

Некоторые подсказки:

• Каждый проверяемый узел должен инкапсулировать данные о том, как вы туда попали.
• DFS похож на стек;Вы начинаете, нажимая стартовое состояние.Вы вытаскиваете стек и отталкиваете узлы, которые могут следовать от узла, который вы открыли.
• Поскольку в конечном итоге вы пытаетесь найти путь, данные узла должны содержать ваше местоположение и путь, по которому вы его выбрали.

Answer 2

Как вы храните свой путь, это ОЧЕНЬ важная тема, если учесть, что некоторые из ваших поисков могут привести к путям длиной более 200 шагов. Итерация по списку, который много раз .... O (2 ^ N) или O (3 ^ N) ? списки для любого вида поиска как механизма хранения пути - неправильный ответ, особенно когда вы входите в BFS и в любое время, когда у вас есть несколько целей (то есть, могут существовать несколько путей через один и тот же узел). Сложность списков и хранение данных просто смешны.

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

Если частью вашего состояния является узел, в котором это состояние было на одном шаге ранее, то у вас есть путь к началу; конечный узел связывается с тем, что позади него, который связывается с тем, что позади него, и т. д. Использование такой уникальной системы ключей позволяет несколько путей через одну и ту же точку при ЧРЕЗВЫЧАЙНО низкой стоимости данных; Вы все еще должны быть рациональными в отношении того, какие пути вы используете. Однако каждый раз, когда вы вытаскиваете что-либо с края, вы вытягиваете весь путь, только с 1 номером.

Answer 3

Я все заработал, убедившись, что каждое движение составляет только 1 расстояние.Одной из проблем с вашим кодом была попытка перепрыгнуть 5 или 6 мест.Удостоверьтесь, что каждое движение, которое он делает, является одним и обратным, пока расстояние перемещения не станет 1 до вашего следующего пункта назначения.Подсказка manhattanDistance ().

Answer 4

 start = [problem.getStartState()]
  for item in start:
      Open=[item]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) is True:
      return 
  else:
       count=0
       while Open:
                if count==0:
                  visit=Open.pop()
                else:
                  temp=Open.pop()
                  visit=temp[0]

                Closed.append(visit)                            
                if problem.isGoalState(visit) is True:
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            if index[0] not in Closed :
                              Open.append((index[0],index[1]))
                print Open
                count=count+1

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

откроется после нахождения решения - (1,1 - решение)

[((5, 4), 'South'), ((4, 5), 'West')]
[((5, 4), 'South'), ((3, 5), 'West')]
[((5, 4), 'South'), ((2, 5), 'West')]
[((5, 4), 'South'), ((1, 5), 'West')]
[((5, 4), 'South'), ((1, 4), 'South')]
[((5, 4), 'South'), ((1, 3), 'South')]
[((5, 4), 'South'), ((2, 3), 'East')]
[((5, 4), 'South'), ((2, 2), 'South')]
[((5, 4), 'South'), ((2, 1), 'South'), ((3, 2), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((4, 2), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((4, 3), 'North')]
[((5, 4), 'South'), ((2, 1), 'South'), ((5, 3), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((5, 4), 'North')]
[((5, 4), 'South'), ((2, 1), 'South')]
[((5, 4), 'South'), ((1, 1), 'West')]

сейчас, если вы заметите, когда он получит три спискачлены, он принимает путь, который был тупиком, теперь Open может вернуться и найти правильный путь, но мне нужен способ как-то указать направление возврата в переменной Path, например

, например, Path = ['юг, запад, запад .................] и т. д.