能够使用 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 设置的方向。当我面临两个后继者都未被访问过的情况时，问题就出现了，我的吃豆人走了一条通向死胡同的路径，所以它需要回溯。我的 Open 做到了这一点并找到了解决方案，但我无法找到如何在我的路径列表中提供回溯方向的方法。如果您要访问 http://inst.eecs.berkeley .edu/~cs188/sp09/projects/search/search.html 并下载 zip 并将我的代码粘贴到 dfs search 下的 search.py​​ 中你就会明白我的问题。

Answer 1

一些提示：

• 您检查的每个节点都应该封装您如何到达那里的数据。
• DFS就像一个栈；您首先按下启动状态。您弹出堆栈，然后推回您弹出的节点之后的节点。
• 由于您最终试图找到一条路径，因此节点数据必须保存您的位置以及您到达那里所采取的路径。

Answer 2

当您考虑到某些搜索可能会产生超过 200 步长的路径时，如何存储路径是一个非常重要的主题。迭代列表多次...O(2^N) 还是O(3^N)？将任何类型的搜索列表作为路径存储机制都是错误的答案，尤其是当您进入 BFS 且任何时候您有多个目标时（意味着可以存在通过同一节点的多条路径）。列表的复杂性和数据存储是荒谬的。

我推荐链接列表作为路径存储机制。当您将节点推入边缘时，只需将它们键入具有唯一键的字典中并按下该键即可。然后，当您从边缘拉出一个节点时，您可以从字典中按原样获取整个状态。

如果你的状态的一部分是该状态之前在一个步骤中所处的节点，那么你就有了一条通往起点的路径；终端节点链接到它后面的节点，终端节点链接到它后面的节点，等等。使用像这样的唯一密钥系统允许通过同一点的多条路径，且数据成本极低；你仍然必须对自己走出边缘的道路保持理性。然而，任何时候你从边缘拉出任何东西，你都会拉动它的整个路径，只有 1 个数字。

Answer 3

我确实通过确保每次移动只有 1 距离来实现它。您的代码的问题之一是最后它尝试跳转 5 或 6 个位置。确保它的每一次移动都是 1，然后反向移动，直到移动距离变为 1 到达下一个目的地。提示曼哈顿距离()。

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')]

现在，如果您会注意到，当它获得三个列表成员时，它会采用一条死胡同的路径，现在打开能够回溯并找到正确的路径，但我需要一种以某种方式在 Path 变量中指定返回方向的方法，例如

Path = ['south',west' west'.................] 等