Resolver laberinto sin capacidad de retorno

Necesito escribir un programa que resuelva el laberinto. Laberinto tiene una estructura gráfica, donde cada nodo, una habitación y bordes, sale a otras habitaciones:

Especificación:

• Partimos de una habitación al azar.
• Laberinto tiene callejones sin salida, 0 o pocas salidas.
• No sabemos nada acerca de todo el laberinto, solo el número de habitaciones actuales y la lista de puertas.
• Cuando entramos en una habitación nueva, no sabemos de dónde venimos (qué puerta de la habitación actual nos lleva de regreso a la habitación anterior).
• Podemos reconocer cuando llegamos a la salida.
• Cada paso nos movemos de la habitación actual a alguna puerta disponible.
• Si estamos en la sala 6, por ejemplo, no podemos simplemente saltar para comenzar. Es como un movimiento de robot.
• Sabemos exactamente la identificación de la habitación actual. Conocemos la identificación de cada puerta en la habitación actual (no en todos los laberintos).
• Nosotros controlamos el robot.

Miré todos los algoritmos conocidos, pero todos requieren al menos una capacidad adicional para volver a la habitación anterior. De acuerdo con las especificaciones, no podemos usar ningún algoritmo que busque la ruta más corta (en realidad, no necesito la más corta), porque solo conocemos la sala actual. No podemos usar los algoritmos de seguimiento de la mano izquierda (derecha), porque no sabemos la dirección de las salidas. Probablemente, la única solución que cumple con las especificaciones es elegir una salida aleatoria en cada habitación con la esperanza de encontrar alguna salida de tiempo ...

¿Alguna sugerencia de cómo resolver tal laberinto de una manera más inteligente?

Hmm, sabes el número de la habitación real. Para que pueda construir una estructura de datos. Supongo que la lista de salidas no tiene los números de habitación adjuntos. Pero después de elegir uno al azar, al menos sabes que hay una conexión.

Digamos que está en la habitación 4 y elija una de las tres salidas aleatorias. Ahora el sistema te dice que estás en la habitación 6 y solo te queda una salida. Eliges eso y vuelves a la habitación 4. En este punto, has reunido información sobre la estructura del laberinto. Ahora elige otra salida y termina en la habitación 5. Información de Moe sobre la habitación 4 (una salida a 6, una salida a 5)

¿Puedes elegir una salida específica? ¿están numerados, digamos que si en la habitación 4 eliges la salida uno siempre terminas en 6? De lo contrario, al menos puede averiguar sobre posibles rutas.

Ok, solo lee tu comentario. Entonces, si las salidas tienen ID y están vinculadas estáticamente a una habitación (incluso si no sabe cuál para empezar), simplemente elija una nueva y recuerde las conexiones de salida / habitación y recuerde qué salida ya se intentó. Intente salidas no probadas hasta que haya buscado en cada habitación individual.

De esa manera es realmente simple. Después de unos pocos pasos, debería tener una lista de conexiones más o menos completa. Solo cuando ingresas a una nueva habitación puedes (por unos pocos pasos) correr al azar. Pero con cada paso obtienes más información y cada vez que ingresas a una habitación visitada anteriormente, puedes tomar una decisión más inteligente (no probar la sala sin salida 6 nuevamente, por ejemplo, cuando vuelves a 4, ya que no tiene salidas que no hayan sido probadas).

Editar La idea es hacer primero pasos aleatorios y registrar la información que encuentre tal como la describí (la descripción de Dan es más concisa). Si se encuentra en una habitación sin salidas desconocidas, puede usar cualquier buscador de ruta conocido para encontrar el camino más corto a una habitación que tenga salidas que aún no haya explorado.

No estoy 100% seguro, pero creo que Peter Norvig escribió sobre un problema similar (El laberinto de Wumpus) en su libro "Inteligencia artificial: un enfoque moderno". Aunque si recuerdo bien, se trataba menos de encontrar el camino y más sobre la toma de decisiones con respecto a cierta información que el sistema podría obtener sobre las habitaciones vecinas.

Editar:

No, no solo es aleatorio. Al realizar un seguimiento de las salidas ya probadas, elimina la redundancia innecesaria. En realidad, ni siquiera necesitas elegir al azar.

Suponga que comienza en la habitación 4. Información que obtiene: 3 salidas A, B, C Siempre elige la primera salida no utilizada. Así que comienza con A. Terminas en la habitación 6. Ahora recuerdas 4A => 6 (y usado) en la habitación 6, obtienes la información 1, salida A. Una vez más, eliges la primera no utilizada (y en este caso, solo sale) Volver a la habitación para conocer 6A => 4 (y no más salidas en la habitación 6) Ahora elige la próxima salida B y llega a la habitación 5 ...

Tarde o temprano habrá buscado en todas las habitaciones de esa manera. Pero en una cuestión sistemática.

La única razón por la que necesitarías encontrar un camino es cuando te encuentras en una habitación donde todas las salidas ya están exploradas. Luego, querrá encontrar un camino directo a la siguiente habitación con salidas inexploradas para ir con su búsqueda. Por lo tanto, el truco principal es menos saber qué salida conduce a qué habitación (aunque esto puede ser útil), pero hacer un seguimiento de las salidas aún no probadas.

De esta manera, por ejemplo, puede evitar correr en círculos todo el tiempo, lo que sería un riesgo para un enfoque puramente aleatorio.

En tu ejemplo de laberinto, lo más probable es que esto no importe mucho. Pero en un gran laberinto con muchas habitaciones y conexiones y quizás habitaciones complicadas con arreglos circulares, este sistema garantiza que encontrará la salida con la menor cantidad de pruebas posible.

(Creo que ese es probablemente el mismo sistema que ideó Byte56 en Gamers)

Reconozco que probablemente obtuviste la esencia de otras respuestas, pero fue una pregunta divertida y tuve ganas de hacer una pequeña codificación de Python. Este es mi enfoque orientado a objetos. La sangría define el alcance.

Representación Gráfica

El gráfico se puede almacenar fácilmente como una clave, un diccionario de valores donde la clave es la identificación de la sala, y el valor es una matriz de las salas a las que conduce.

map = {
1:[5, 2],
2:[1, 3, 5],
3:[2, 4],
4:[3, 5, 6],
5:[2, 4, 1],
6:[4]
}

Interfaz de agente

Primero debemos pensar qué información debería poder aprender el agente del entorno y las operaciones que debería poder realizar. Esto simplificará el pensamiento sobre el algoritmo.

En este caso, el agente debería poder consultar en el entorno la identificación de la habitación en la que se encuentra, debería poder contar las puertas de la habitación en la que se encuentra ( tenga en cuenta que esta no es la identificación de las habitaciones las puertas conducen a! ) y debería poder moverse a través de una puerta especificando un índice de puerta. Cualquier otra cosa que un agente sepa tiene que ser resuelta por el propio agente.

class AgentInterface(object):
    def __init__(self, map, starting_room):
        self.map = map
        self.current_room = starting_room

    def get_door_count(self):
        return len(self.map[self.current_room])

    def go_through_door(self, door):
        result = self.current_room = self.map[self.current_room][door]
        return result

Conocimiento del agente

Cuando el agente ingresa por primera vez al mapa, solo conoce la cantidad de puertas en la habitación y la identificación de la habitación en la que se encuentra actualmente. Necesitaba crear una estructura que almacenara la información que el agente había aprendido, como qué puertas no había sido a través, y por donde habían pasado las puertas.

Esta clase representa la información sobre una habitación individual. Elegí almacenar las puertas no visitadas como a sety las puertas visitadas como a dictionary, donde la clave es la identificación de la puerta y el valor es la identificación de la habitación a la que conduce.

class RoomKnowledge(object):
    def __init__(self, unvisited_door_count):
        self.unvisited_doors = set(range(unvisited_door_count))
        self.visited_doors = {}

Algoritmo de agente

• Cada vez que el agente ingresa a una sala, busca en su diccionario de conocimiento información sobre la sala. Si no hay entradas para esta sala, crea una nueva RoomKnowledgey agrega esto a su diccionario de conocimiento.

• Comprueba si la habitación actual es la habitación objetivo, si es así, vuelve.

• Si hay puertas en esta sala que no hemos visitado, atravesamos la puerta y almacenamos a donde conduce. Luego continuamos el ciclo.

• Si no había puertas sin visitar, retrocedemos por las habitaciones que hemos visitado para encontrar una con puertas sin visitar.

La Agentclase hereda de la AgentInterfaceclase.

class Agent(AgentInterface):

    def find_exit(self, exit_room_id):
        knowledge = { }
        room_history = [] # For display purposes only
        history_stack = [] # Used when we need to backtrack if we've visited all the doors in the room
        while True:
            room_knowledge = knowledge.setdefault(self.current_room, RoomKnowledge(self.get_door_count()))
            room_history.append(self.current_room)

            if self.current_room==exit_room_id:
                return room_history

            if len(room_knowledge.unvisited_doors)==0:
                # I have destination room id. I need door id:
                door = find_key(room_knowledge.visited_doors, history_stack.pop())
                self.go_through_door(door)
            else:   
                history_stack.append(self.current_room)
                # Enter the first unopened door:
                opened_door = room_knowledge.unvisited_doors.pop()
                room_knowledge.visited_doors[opened_door]=self.go_through_door(opened_door)

Funciones de apoyo

Tuve que escribir una función que encontrara una clave en un diccionario dado un valor, ya que cuando retrocedemos sabemos la identificación de la habitación a la que estamos tratando de llegar, pero no qué puerta usar para llegar a ella.

def find_key(dictionary, value):
    for key in dictionary:
        if dictionary[key]==value:
            return key

Pruebas

Probé todas las combinaciones de posición de inicio / fin en el mapa dado anteriormente. Para cada combinación imprime las habitaciones visitadas.

for start in range(1, 7):
    for exit in range(1, 7):
        print("start room: %d target room: %d"%(start,exit))
        james_bond = Agent(map, start)
        print(james_bond.find_exit(exit))

Notas

El retroceso no es muy eficiente: en el peor de los casos, podría atravesar cada habitación para llegar a una habitación adyacente, pero el retroceso es bastante raro: en las pruebas anteriores solo retrocede tres veces. He evitado poner el manejo de excepciones para mantener el código conciso. Cualquier comentario sobre mi Python apreciado :)

Esencialmente, tiene un gráfico direccional, donde cada habitación conectada está conectada por dos pasajes desconocidos, uno en cualquier dirección. Digamos que comienzas en nodo 1y puertas Ay Bsales. No sabes qué hay más allá de cada puerta, así que simplemente eliges la puerta A. Se llega a la habitación 2, que tiene las puertas C, Dy E. Ahora sabe que la puerta Aconduce de una habitación 1a otra 2, pero no sabe cómo regresar, por lo que elige la puerta al azar C. ¡Vuelves a la habitación 1! Ahora ya sabes cómo llegar entre habitaciones 1y 2. ¡Continúa explorando a través de la puerta desconocida más cercana hasta que encuentres la salida!

Dado que las habitaciones siempre están en el mismo orden en las listas de salida, podemos hacer un mapa rápido de las habitaciones mientras buscamos una salida.

Mi pseudocódigo es algo javaicano, lo siento, lo he estado usando mucho últimamente.

Unvisited_Rooms es un hashmap que contiene una ID de habitación y una lista de índices de las habitaciones no asignadas o una matriz 2D, lo que funcione.

Me imagino que el algoritmo podría ser algo como esto:

Unvisited_Rooms.add(currentRoom.ID, currentRoom.exits) //add the starting room exits
while(Unvisited_Rooms.Keys.Count > 0 && currentRoom != end) //keep going while there are unmapped exits and we're not at the end
    Room1 = currentRoom
    ExitID = Room1.get_first_unmapped_Room() //returns the index of the first unmapped room
    if(ExitID == -1) //this room didn't have any more unmapped rooms, it's totally mapped
        PathTo(Get_Next_Room_With_Unmapped_Exits) //we need to go to a room with unmapped exits
        continue //we need to start over once we're there, so we don't create false links
    GoToExit(ExitID) //goes to the room, setting current room to the room on the other side
    Room1.Exits[exitID].connection = currentRoom.ID //maps the connection for later path finding
    Unvisited_Rooms[Room1.ID].remove(exitID) //removes the index so we don't worry about it
    if(Unvisited_Rooms[Room1.ID].size < 1) //checks if all the rooms exits have been accounted for
        Unvisited_Rooms.remove(Room1.ID)  //removes the room if it's exits are all mapped
    Unvisited_Rooms.add(currentRoom.ID, currentRoom.unvisited_exits) //adds more exits to the list

If(currentRoom != end && Unvisited_Rooms.Keys.Count < 1)
   print(No exit found!)
else
   print(exit is roomID: currentRoom.ID)

Tendrá que usar uno de los buscadores de ruta de nodo comunes a las habitaciones PathTo () en "el mapa". Esperemos que sea lo suficientemente claro como para comenzar con algo.

No tengo muy claros sus requisitos, pero si se permite lo siguiente, puede ser un algoritmo simple de seguir. Probablemente un error allí, especialmente porque usa una función recursiva. Además, verifica si una puerta conduce a la habitación de la que viniste, pero no sé cómo se manejaría un camino circular de tres habitaciones, puede seguir girando para siempre en esas tres habitaciones. Es posible que deba agregar un historial para asegurarse de que no se revise ninguna habitación dos veces. Pero al leer su descripción eso puede no estar permitido.

solved = FALSE

SearchRoom(rooms[0], rooms[0])    // Start at room 1 (or any room)
IF solved THEN
  // solvable
ELSE
  // unsolvable
ENDIF
END

// Recursive function, should run until it searches every room or finds the exit
FUNCTION SearchRoom: curRoom, prevRoom
  // Is this room the 'exit' room
  IF curRoom.IsExit() THEN
    solved = TRUE
    RETURN
  ENDIF

  // Deadend?  (skip starting room)
  IF (curRoom.id <> prevRoom.id) AND (curRoom.doors <= 1) THEN RETURN

  // Search each room the current room leads to
  FOREACH door IN curRoom
    // Skip the room we just came from
    IF door.id <> prevRoom.id THEN
      SearchRoom(door, curRoom)
    ENDIF
    IF solved THEN EXIT LOOP
  NEXT

  RETURN
ENDFUNCTION

[Editar] Se agregó 'id' a la verificación anterior y se actualizó para que esté más orientado a objetos.

La respuesta corta es una búsqueda profunda con retroceso. Puede hacerlo primero si lo prefiere, pero su pequeño robot caminará mucho más adelante y atrás.

Más concretamente, suponga que se nos da:

// Moves to the given room, which must have a door between
// it and the current room.
moveTo(room);

// Returns the list of room ids directly reachable from
// the current room.
getDoors();

// Returns true if this room is the exit.
isExit();

Para encontrar la salida, solo necesitamos:

void escape(int startingRoom) {
  Stack<int> path = new Stack<int>();
  path.push(startingRoom);
  escape(path);
}

boolean escape(Stack<int> path) {
  for (int door : getDoors()) {
    // Stop if we've escaped.
    if (isExit()) return true;

    // Don't walk in circles.
    if (path.contains(door)) continue;

    moveTo(door);
    path.push(door);
    if (escape(path)) return true;

    // If we got here, the door didn't lead to an exit. Backtrack.
    path.pop();
    moveTo(path.peek());
  }
}

Llame escape()con la ID de la sala de inicio y moverá el robot a la salida (llamando moveTo()).