Estoy trabajando en una tarea que se encuentra en la página de un curso de IA en el sitio web de berkley por diversión. Necesito escribir una búsqueda profunda del juego pacman para que pueda encontrar su camino. El problema es que el pacman se atasca. Pegaré el código primero para aclarar lo que digo:

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

Ahora, si lee mi código en dfs, verá que la lista abierta contiene todos los puntos que visito y expandí.

El archivo Path contiene la dirección establecida para el pacman. El problema surge cuando me enfrento a la condición de que ambos sucesores que tengo no son visitados, mi pacman toma un camino que conduce a un callejón sin salida, por lo que debe retroceder. My Open lo hace y encuentra la solución, pero no puedo encontrar una manera de proporcionar las direcciones de retroceso en mi lista de rutas. Si va a http: //inst.eecs.berkeley .edu / ~ cs188 / sp09 / projects / search / search.html y descargue el zip y pegue mi código en search.py bajo dfs search comprenderá mi problema.

1
trailblazer 16 sep. 2011 a las 01:10

4 respuestas

La mejor respuesta

Algunos consejos:

  • Cada nodo que verifique debe encapsular los datos de cómo llegó allí.
  • DFS es como una pila; comienzas presionando el estado de inicio. Hace estallar la pila y empuja hacia atrás los nodos que pueden seguir desde el nodo que hizo estallar.
  • Como finalmente está tratando de encontrar una ruta, los datos del nodo deben contener su ubicación y la ruta que tomó para llegar allí.
3
VMDX 15 sep. 2011 a las 22:15

La forma en que almacena su ruta es un tema MUY importante, cuando considera que algunas de sus búsquedas pueden generar rutas de más de 200 pasos. Iterando una lista muchas veces ... ¿ O (2 ^ N) u O (3 ^ N) ? Las listas para cualquier tipo de búsqueda como mecanismo de almacenamiento de rutas son la respuesta incorrecta, especialmente cuando ingresa a BFS y cada vez que tiene múltiples objetivos (es decir, pueden existir múltiples rutas a través del mismo nodo). Lista de la complejidad y el almacenamiento de datos es ridículo.

Recomiendo la lista de enlaces como un mecanismo de almacenamiento de ruta. Cuando empuje sus nodos hacia la periferia, simplemente introdúzcalos en un diccionario con una clave única y presione la tecla. Luego, cuando extrae un nodo de la periferia, puede obtener todo el estado, tal como está, del diccionario.

Si parte de su estado es el nodo en el que ese estado estaba en un paso anteriormente, entonces tiene una ruta al inicio; el nodo final enlaza con el que está detrás, que enlaza con el que está detrás, etc. El uso de un sistema de clave único como este permite múltiples rutas a través del mismo punto, a un costo de datos EXTREMADAMENTE bajo; aún debe ser racional acerca de qué caminos extrae de la periferia. Sin embargo, cada vez que saca algo de la periferia, tira de todo su camino, con solo 1 número.

2
Nikana Reklawyks 9 oct. 2012 a las 05:35

Lo hice funcionar asegurándome de que cada movimiento sea solo 1 distancia. Uno de los problemas con su código fue al final intentar saltar 5 o 6 lugares. Asegúrese de que cada movimiento que realice sea uno e invierta hasta que la distancia de movimiento se convierta en 1 a su próximo destino. Sugerencia manhattanDistance ().

1
guruge w 16 oct. 2011 a las 03:45
 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

Cambié el código como dijiste. En este momento no tengo nada en el camino.

Esta abierta después de encontrar la solución - (1,1 es la solución)

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

Ahora, si se da cuenta de que cuando obtiene tres miembros de la lista, toma una ruta que era un callejón sin salida, ahora el Open puede retroceder y encontrar la ruta correcta, pero necesito una forma de especificar de alguna manera la dirección de retorno en la variable Ruta como

Por ejemplo, Path = ['sur', oeste 'oeste' .................] etc.

0
trailblazer 16 sep. 2011 a las 16:53