能够使用DFS查找路径，但无法指定前往Pacman _ Python的正确方向 [英] Able to find path using DFS but not able specify the right directions to Pacman _ Python

问题描述

我正在做一个有趣的任务，该任务位于伯克利网站上的AI课程页面上.我需要为吃豆人游戏写一个深度优先搜索，以便它可以找到它的路径.问题是吃豆人被卡住了.我将首先粘贴代码以使我的发言更加清楚:

I am working on an assignment found on an AI course page at berkley website for fun. I need to write a depth-first search for the pacman game so that it can find its path.The problem is the pacman gets stuck. I'll paste the code first to make what I am saying more clear :

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下阅读我的代码，您将看到打开的列表包含我访问和扩展的所有点.

Now if you will read my code under dfs you will see that open list contains all the points I visit and expanded.

路径文件包含为pacman设置的方向.当我遇到两个继承人都未被访问的情况时，问题就出现了，我的吃豆人走了一条通往死胡同的道路，因此需要回溯.我的公开赛做到了并找到了解决方案，但我无法找到有关如何在路径列表中提供回溯方向的方法.如果您要访问 http://inst.eecs.berkeley .edu/〜cs188/sp09/projects/search/search.html 并下载zip并将我的代码粘贴到dfs搜索下的search.py中，您将了解我的问题.

The Path file contains the direction set for the pacman. The problem arises when I face the condition that both successors I get are unvisited, my pacman takes a path which leads to a dead end so it needs to backtrace. My Open does it and finds the solution but I am not able to find a way on how to provide the directions of backtracing in my path list. If you will go to http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html and download the zip and paste my code in search.py under dfs search you will understand my problem.

推荐答案

一些提示:

• 您检查的每个节点都应封装到达目的地的数据.
• DFS就像一个堆栈；您可以通过按开始状态开始.您弹出堆栈，然后从弹出节点中推回可以跟随的节点.
• 由于您最终要尝试查找路径，因此节点数据必须包含您的位置以及到达该位置的路径.

这篇关于能够使用DFS查找路径，但无法指定前往Pacman _ Python的正确方向的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！