能够使用DFS找到路径，但无法为吃豆人指定正确方向 _ 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）部分的代码，你会发现开放列表里包含了我访问过和扩展过的所有点。

路径文件里包含了吃豆人的移动方向。问题出现在我遇到的情况是，当我得到的两个后继点都是未访问过的时，吃豆人会选择一条通往死胡同的路，这样就需要回溯。我的开放列表可以做到这一点并找到解决方案，但我不知道怎么把回溯的方向添加到我的路径列表里。如果你去http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html下载压缩包，然后把我的代码粘贴到search.py的深度优先搜索部分，你就能理解我的问题了。

游戏开发算法设计人工智能深度优先搜索路径规划回溯算法状态空间搜索吃豆人

能够使用DFS找到路径，但无法为吃豆人指定正确方向 _ Python

4 个回答

撰写回答