Résoudre un labyrinthe sans possibilité de retour

J'ai besoin d'écrire un programme qui résoudra le labyrinthe. Maze a une structure graphique, où chaque nœud - une pièce et des bords - sort vers d'autres pièces:

Spécification:

• Nous partons d'une pièce au hasard.
• Maze a des impasses, 0 ou quelques sorties.
• Nous ne savons rien de tout le labyrinthe, seulement le nombre de pièces actuelles et la liste des portes.
• Lorsque nous entrons dans une nouvelle pièce, nous ne savons pas d'où nous venons (quelle porte de la pièce actuelle nous ramène à la pièce précédente).
• Nous pouvons reconnaître quand nous atteignons la sortie.
• À chaque étape, nous passons de la pièce actuelle à une porte disponible.
• Si nous sommes à la salle 6 par exemple, nous ne pouvons pas simplement sauter pour commencer. C'est comme un mouvement de robot.
• Nous savons exactement l'ID de la pièce actuelle. Nous connaissons l'ID de chaque porte de la pièce actuelle (pas dans tous les labyrinthes).
• Nous contrôlons le robot.

J'ai regardé tous les algorithmes connus, mais ils nécessitent tous au moins une capacité supplémentaire pour revenir à la pièce précédente. Selon les spécifications, nous ne pouvons utiliser aucun algorithme qui recherche le chemin le plus court (en fait, je n'ai pas besoin du plus court), car nous ne connaissons que la salle actuelle. Nous ne pouvons pas utiliser les algorithmes suivants à gauche (droite), car nous ne connaissons pas la direction des sorties. Probablement, la seule solution qui répond aux spécifications est de choisir une sortie aléatoire dans chaque pièce en espérant qu'une sortie de temps sera trouvée ...

Une suggestion sur la façon de résoudre un tel labyrinthe de manière plus intelligente?

Hmm, vous connaissez le numéro de la pièce réelle. Vous pouvez donc créer une structure de données. Je suppose que la liste des sorties n'a pas de numéro de chambre. Mais après en avoir choisi un au hasard, vous savez au moins qu'il existe une connexion.

Dites que vous êtes dans la salle 4 et choisissez l'une des trois sorties aléatoires. Le système vous indique maintenant que vous êtes dans la salle 6 et qu'il ne vous reste qu'une seule sortie. Vous choisissez cela et vous êtes de retour dans la salle 4. À ce stade, vous avez rassemblé des informations sur la structure du labyrinthe. Vous choisissez maintenant une autre sortie et vous terminez dans la salle 5. Informations Moe sur la salle 4 (une sortie vers 6, une sortie vers 5)

Pouvez-vous choisir une sortie spécifique? sont-ils numérotés, disons que si dans la salle 4 vous choisissez la sortie une, vous finissez toujours par 6? Sinon, vous pouvez au moins vous renseigner sur les itinéraires possibles.

Ok, lisez simplement votre commentaire. Donc, si les sorties ont des identifiants et que ceux-ci sont liés statiquement à une pièce (même si vous ne savez pas laquelle pour commencer), vous en choisissez simplement une nouvelle et vous souvenez des connexions sortie / chambre et rappelez-vous quelle sortie a déjà été essayée. Essayez des sorties non essayées jusqu'à ce que vous ayez fouillé chaque pièce.

De cette façon, c'est en fait simple. Après quelques étapes, vous devriez avoir une liste plus ou moins complète de connexions. Ce n'est que lorsque vous entrez dans une nouvelle pièce que vous pouvez (pour quelques étapes) courir au hasard. Mais à chaque étape, vous obtenez plus d'informations et chaque fois que vous entrez dans une pièce visitée auparavant, vous pouvez prendre une décision plus intelligente (ne pas tester à nouveau la salle sans issue 6 par exemple lorsque vous retrouvez à 4, car il n'y a pas de sorties non testées).

Modifier L'idée est de faire des étapes aléatoires en premier et de consigner les informations que vous trouvez comme je l'ai décrit (la description de Dan est plus concise). Si vous vous trouvez dans une pièce sans sortie inconnue, vous pouvez utiliser n'importe quel éclaireur connu pour trouver le chemin le plus court vers une pièce qui a des sorties que vous n'avez pas encore explorées.

Pas sûr à 100%, mais je pense que Peter Norvig a écrit sur un problème similaire (le labyrinthe de Wumpus) dans son livre "Intelligence artificielle: une approche moderne". Mais si je me souviens bien, il s'agissait moins de trouver un chemin et plus de prendre des décisions concernant certaines informations que le système pourrait obtenir sur les pièces voisines.

Éditer:

Non, ce n'est pas seulement aléatoire. En gardant une trace des sorties déjà essayées, vous supprimez la redondance inutile. En fait, vous n'avez même pas besoin de choisir au hasard.

Supposons que vous commenciez dans la salle 4. Info que vous obtenez: 3 sorties A, B, C Vous choisissez toujours la première sortie maintenant inutilisée. Commencez donc par A. Vous terminez dans la salle 6. Maintenant, vous vous souvenez de 4A => 6 (et utilisé) dans la salle 6, vous obtenez l'info 1 sortie A. Encore une fois, vous choisissez la première sortie inutilisée (et dans ce cas uniquement la sortie) Retour dans la salle pour connaître 6A => 4 (et aucune autre sortie dans la salle 6) Maintenant, vous choisissez la prochaine sortie B et atteignez la salle 5 ...

Tôt ou tard, vous aurez fouillé toutes les pièces de cette façon. Mais de manière systématique.

La seule raison pour laquelle vous auriez besoin d'une recherche de chemin est lorsque vous vous trouvez dans une pièce où toutes les sorties sont déjà explorées. Ensuite, vous voudrez trouver un chemin direct vers la pièce suivante avec des sorties inexplorées pour aller de l'avant avec votre recherche. Donc, l'astuce principale est moins de savoir quelle sortie mène à quelle pièce (bien que cela puisse être utile) mais de garder une trace des sorties non encore essayées.

De cette façon, par exemple, vous pouvez éviter de tourner en rond tout le temps, ce qui serait un risque pour une approche purement aléatoire.

Dans votre exemple de labyrinthe, cela n'aurait probablement pas beaucoup d'importance. Mais dans un grand labyrinthe avec de nombreuses pièces et connexions et peut-être des pièces disposées de façon circulaire et délicate, ce système garantit que vous trouverez la sortie avec le moins d'essais possible.

(Je pense que c'est probablement le même système que Byte56 avec Gamers)

Je reconnais que vous avez probablement compris l'essentiel des autres réponses, mais c'était une question amusante et j'avais envie de faire un peu de codage Python. Ceci est mon approche orientée objet. L'indentation définit la portée.

Représentation graphique

Le graphique peut facilement être stocké sous forme de clé, dictionnaire de valeurs où la clé est l'identifiant de la pièce et la valeur est un tableau des pièces vers lesquelles elle mène.

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

Interface de l'agent

Nous devons d'abord réfléchir aux informations que l'agent devrait être en mesure d'apprendre de l'environnement et aux opérations qu'il devrait être en mesure d'effectuer. Cela simplifiera la réflexion sur l'algorithme.

Dans ce cas, l'agent devrait pouvoir interroger l'environnement pour l'identifiant de la pièce dans laquelle il se trouve, il devrait être en mesure d'obtenir un compte des portes de la pièce dans laquelle il se trouve ( notez qu'il ne s'agit pas de l'identifiant des pièces dans lesquelles il se trouve). portes mènent à! ) et il doit pouvoir se déplacer à travers une porte en spécifiant un index de porte. Tout ce qu'un agent sait doit être déterminé par l'agent lui-même.

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

Connaissance des agents

Lorsque l'agent entre pour la première fois sur la carte, il ne connaît que le nombre de portes dans la pièce et l'identifiant de la pièce dans laquelle il se trouve actuellement. à travers, et où les portes mènent à cela était passé.

Cette classe représente les informations sur une seule pièce. J'ai choisi de stocker les portes non visitées comme un setet les portes visitées comme un dictionary, où la clé est l'identifiant de la porte et la valeur est l'identifiant de la pièce vers laquelle elle mène.

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

Algorithme d'agent

• Chaque fois que l'agent pénètre dans une pièce, il recherche dans son dictionnaire de connaissances des informations sur la pièce. S'il n'y a pas d'entrées pour cette salle, il en crée une nouvelle RoomKnowledgeet l'ajoute à son dictionnaire de connaissances.

• Il vérifie si la pièce actuelle est la pièce cible, si c'est le cas, il revient.

• S'il y a des portes dans cette pièce que nous n'avons pas visitées, nous passons par la porte et stockons où elles mènent. Nous continuons ensuite la boucle.

• S'il n'y avait pas de portes non visitées, nous revenons en arrière dans les pièces que nous avons visitées pour en trouver une avec des portes non visitées.

La Agentclasse hérite de la AgentInterfaceclasse.

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)

Fonctions de support

J'ai dû écrire une fonction qui trouverait une clé dans un dictionnaire étant donné une valeur, car lors du retour en arrière, nous connaissons l'identifiant de la pièce que nous essayons d'accéder, mais pas la porte à utiliser pour y accéder.

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

Essai

J'ai testé toutes les combinaisons de position de début / fin dans la carte ci-dessus. Pour chaque combinaison, il imprime les pièces visitées.

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))

Remarques

Le retour arrière n'est pas très efficace - dans le pire des cas, il pourrait traverser chaque pièce pour se rendre dans une pièce adjacente, mais le retour arrière est assez rare - dans les tests ci-dessus, il ne fait que revenir en arrière trois fois. J'ai évité de mettre la gestion des exceptions pour garder le code concis. Tout commentaire sur mon Python apprécié :)

Essentiellement, vous avez un graphique directionnel, où chaque pièce connectée est reliée par deux passages inconnus - un dans l'une ou l'autre direction. Disons que vous commencez dans le nœud 1, les portes Aet Bsortez. Vous ne savez pas ce qui se cache au-delà de chaque porte, vous choisissez donc simplement la porte A. Vous obtenez à la chambre 2, qui a des portes C, Det E. Vous savez maintenant que la porte Amène de pièce 1en pièce 2, mais vous ne savez pas comment revenir, vous choisissez donc la porte au hasard C. Vous rentrez dans la chambre 1! Vous savez maintenant comment vous déplacer entre les chambres 1et 2. Continuez à explorer par la porte inconnue la plus proche jusqu'à ce que vous trouviez la sortie!

Étant donné que les chambres sont toujours dans le même ordre dans les listes de sorties, nous pouvons faire un plan rapide des chambres tout en recherchant une sortie.

Mon pseudo code est un peu Javaish, désolé, je l'utilise beaucoup ces derniers temps.

Unvisited_Rooms est une table de hachage contenant un ID de salle et une liste d'index des salles non mappées Ou un tableau 2D, tout ce qui fonctionne.

J'imagine que l'algorithme pourrait ressembler à ceci:

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)

Vous devrez utiliser l'un des moteurs de recherche de chemin de nœud communs aux salles PathTo () dans "la carte". J'espère que c'est assez clair pour vous aider à démarrer.

Je ne suis pas trop clair sur vos besoins, mais si ce qui suit est autorisé, il peut s'agir d'un algorithme simple à suivre. Probablement un bogue là-dedans, d'autant plus qu'il utilise une fonction récursive. De plus, il vérifie si une porte mène à la pièce d'où vous venez, mais je ne sais pas comment un chemin circulaire à trois pièces pourrait gérer, il peut simplement continuer à boucler pour toujours dans ces trois pièces. Vous devrez peut-être ajouter un historique pour vous assurer qu'aucune chambre n'est vérifiée deux fois. Mais en lisant votre description, cela peut ne pas être autorisé.

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

[Modifier] Ajouté 'id' à la vérification précédente et mis à jour pour rendre plus orienté objet.

La réponse courte est une recherche en profondeur avec retour en arrière. Vous pouvez faire de l'ampleur en premier si vous préférez, mais votre petit robot fera alors beaucoup plus de va-et-vient.

Plus concrètement, supposons qu'on nous donne:

// 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();

Pour trouver la sortie, nous avons juste besoin de:

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());
  }
}

Appelez escape()avec l'ID de la salle de départ et il déplacera le robot vers la sortie (en appelant moveTo()).