能够使用DFS找到路径，但不能指定正确的Pacman _ Python方向

Question

我正在做一个作业，在伯克利网站的人工智能课程页面上找到了一个有趣的任务。我需要为吃豆人游戏编写一个深度优先搜索，这样它才能找到自己的路径。问题是吃豆人卡住了。为了让我说的更清楚，我先粘贴代码:

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的方向集。当我面对两个继承者都未访问的情况时，问题就出现了，我的吃豆人走了一条通向死胡同的路，所以它需要回溯。我的开放做到了这一点，并找到了解决方案，但我无法找到如何在我的路径列表中提供反向追踪方向的方法。如果你去http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html下载zip并粘贴我的代码在search.py下的dfs搜索你会理解我的问题。

Answer 1

一些提示:

• 您检查的每个节点都应该封装如何到达那里的数据。
• DFS就像一个堆栈;从推起始态开始。您弹出堆栈，并推回可以跟随您弹出的节点的节点。
• 由于你最终试图找到一个路径，节点数据必须包含你的位置和你到达那里的路径。

Answer 2

如何存储路径是一个非常重要的主题，当你考虑到你的一些搜索可能会导致路径200多步长。对列表进行多次迭代....O(2^N)还是O(3^N)?将任何类型的搜索列表作为路径存储机制都是错误的答案，特别是当您进入BFS时，以及当您有多个目标时(即通过同一节点的多条路径可能存在)。列表的复杂性和数据存储是荒谬的。

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

如果你的状态的一部分是该状态在前一步中所在的节点，那么你有一条通往起点的路径;结束节点链接到它后面的节点，它链接到它后面的节点，以此类推。使用像这样的唯一密钥系统允许多个路径通过同一点，以极低的数据成本;你仍然必须理性地选择走哪条路。然而，当你从边缘取下任何东西时，你取的是它的整个路径，只有一个数字。

Answer 3

我确实通过确保每次移动只有1个距离来实现它。你的代码的一个问题是在最后它试图跳5或6个地方。确保它做的每一个动作都是1，然后反向移动，直到移动距离你的下一个目的地变成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

我按你说的改了代码。现在我的path中没有任何东西

这个打开后找到解-(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变量中指定返回方向，比如

为如路径

=("南方",西方西方 '.................div)等