Labyrinth ohne Rückgabefähigkeit lösen

Ich muss ein Programm schreiben, das das Labyrinth löst. Das Labyrinth hat eine Diagrammstruktur, bei der jeder Knoten - ein Raum und Kanten - in andere Räume austritt:

Spezifikation:

• Wir beginnen in einem zufälligen Raum.
• Labyrinth hat Sackgassen, 0 oder wenige Ausgänge.
• Wir wissen nichts über alles Labyrinth, nur die Anzahl der aktuellen Räume und die Liste der Türen.
• Wenn wir einen neuen Raum betreten, wissen wir nicht, woher wir kommen (welche Tür vom aktuellen Raum führt uns zurück zum vorherigen Raum).
• Wir können erkennen, wann wir den Ausgang erreichen.
• Bei jedem Schritt bewegen wir uns vom aktuellen Raum zu einer verfügbaren Tür.
• Wenn wir zum Beispiel in Raum 6 sind, können wir nicht einfach springen, um zu beginnen. Es ist wie eine Roboterbewegung.
• Wir kennen die ID des aktuellen Zimmers genau. Wir kennen den Ausweis jeder Tür im aktuellen Raum (nicht in jedem Labyrinth).
• Wir steuern Roboter.

Ich habe alle bekannten Algorithmen untersucht, aber alle erfordern zumindest zusätzliche Fähigkeiten, um zum vorherigen Raum zurückzukehren. Laut Spezifikation können wir keine Algorithmen verwenden, die nach dem kürzesten Weg suchen (eigentlich brauche ich den kürzesten nicht), da wir nur über den aktuellen Raum Bescheid wissen. Wir können keine Links- (Rechts-) Folgealgorithmen verwenden, da wir die Richtung der Ausgänge nicht kennen. Wahrscheinlich besteht die einzige Lösung, die den Spezifikationen entspricht, darin, in jedem Raum einen zufälligen Ausgang zu wählen, in der Hoffnung, dass ein zeitlicher Ausgang gefunden wird ...

Irgendwelche Vorschläge, wie man ein solches Labyrinth klüger lösen kann?

Hmm, Sie kennen die Nummer des tatsächlichen Raums. So können Sie eine Datenstruktur erstellen. Ich denke, die Liste der Ausgänge enthält nicht die Zimmernummern. Aber nachdem Sie zufällig eine ausgewählt haben, wissen Sie zumindest, dass es eine Verbindung gibt.

Angenommen, Sie befinden sich in Raum 4 und wählen einen von drei zufälligen Ausgängen. Jetzt teilt Ihnen das System mit, dass Sie sich in Raum 6 befinden und nur noch einen Ausgang haben. Sie wählen das und sind wieder in Raum 4. An diesem Punkt haben Sie einige Informationen über die Struktur des Labyrinths gesammelt. Sie wählen nun einen anderen Ausgang und enden in Raum 5. Weitere Informationen zu Raum 4 (ein Ausgang zu 6, ein Ausgang zu 5)

Können Sie einen bestimmten Ausgang wählen? Sind sie nummeriert, sagen wir, wenn Sie in Raum 4 den Ausgang 1 wählen, enden Sie immer in 6? Ansonsten können Sie sich zumindest über mögliche Routen informieren.

Ok, lies einfach deinen Kommentar. Wenn die Ausgänge IDs haben und diese statisch mit einem Raum verknüpft sind (auch wenn Sie zunächst nicht wissen, welcher), wählen Sie einfach einen neuen aus und merken Sie sich die Ausgangs- / Raumverbindungen und merken Sie sich, welcher Ausgang bereits versucht wurde. Versuchen Sie es mit nicht erprobten Ausgängen, bis Sie jeden einzelnen Raum durchsucht haben.

Auf diese Weise ist es eigentlich einfach. Nach einigen Schritten sollten Sie eine mehr oder weniger vollständige Liste der Verbindungen haben. Nur wenn Sie einen neuen Raum betreten, können Sie (für ein paar Schritte) zufällig herumlaufen. Aber mit jedem Schritt erhalten Sie mehr Informationen und wenn Sie einen zuvor besuchten Raum betreten, können Sie eine klügere Entscheidung treffen (Sie können den Sackgassenraum 6 nicht erneut testen, wenn Sie beispielsweise auf 4 zurückfinden, da er keine nicht getesteten Ausgänge hat).

Bearbeiten Die Idee ist, zuerst zufällige Schritte auszuführen und die Informationen, die Sie finden, wie beschrieben zu protokollieren (Dans Beschreibung ist prägnanter). Wenn Sie sich in einem Raum ohne unbekannte Ausgänge befinden, können Sie mit jedem bekannten Pfadfinder den kürzesten Weg zu einem Raum mit Ausgängen finden, die Sie noch nicht erkundet haben.

Nicht 100% sicher, aber ich denke, Peter Norvig hat in seinem Buch "Künstliche Intelligenz: Ein moderner Ansatz" über ein ähnliches Problem (Das Wumpus-Labyrinth) geschrieben. Wenn ich mich recht erinnere, ging es weniger um die Wegfindung als vielmehr um die Entscheidungsfindung in Bezug auf einige Informationen, die das System über benachbarte Räume erhalten konnte.

Bearbeiten:

Nein, es ist nicht nur zufällig. Indem Sie bereits versuchte Exits verfolgen, entfernen Sie unnötige Redundanz. Eigentlich müssen Sie nicht einmal zufällig auswählen.

Angenommen, Sie beginnen in Raum 4. Informationen erhalten Sie: 3 Ausgänge A, B, C Sie wählen immer den ersten, noch nicht verwendeten Ausgang. Beginnen Sie also mit A. Sie enden in Raum 6. Jetzt erinnern Sie sich an 4A => 6 (und verwendet) in Raum 6 und erhalten die Info 1 Ausgang A. Wieder wählen Sie den ersten unbenutzten (und in diesem Fall nur Ausgang) Zurück in Raum um 6A zu kennen => 4 (und keine weiteren Ausgänge in Raum 6) Nun wählen Sie den nächsten Ausgang B und erreichen Raum 5 ...

Früher oder später haben Sie alle Räume auf diese Weise durchsucht. Aber in einer systematischen Angelegenheit.

Der einzige Grund für die Suche nach einem Pfad ist, wenn Sie sich in einem Raum befinden, in dem bereits alle Ausgänge erkundet sind. Dann möchten Sie einen direkten Weg zum nächsten Raum mit unerforschten Ausgängen finden, um sich Ihrer Suche zu widmen. Der Haupttrick besteht also weniger darin, zu wissen, welcher Ausgang zu welchem ​​Raum führt (obwohl dies hilfreich sein kann), sondern darin, noch nicht erprobte Ausgänge im Auge zu behalten.

Auf diese Weise können Sie beispielsweise vermeiden, ständig im Kreis zu laufen, was ein Risiko für einen rein zufälligen Ansatz darstellen würde.

In Ihrem Beispiellabyrinth würde dies höchstwahrscheinlich nicht viel ausmachen. Aber in einem großen Labyrinth mit vielen Räumen und Verbindungen und möglicherweise kniffligen, kreisförmig angeordneten Räumen garantiert dieses System, dass Sie den Ausgang mit so wenig Versuchen wie möglich finden.

(Ich denke, das ist wahrscheinlich das gleiche System, das Byte56 in Gamers entwickelt hat.)

Ich erkenne, dass Sie wahrscheinlich das Wesentliche aus anderen Antworten erhalten haben, aber es war eine lustige Frage und ich hatte Lust, ein wenig Python-Codierung zu machen. Dies ist mein objektorientierter Ansatz. Einrückung definiert den Umfang.

Diagrammdarstellung

Das Diagramm kann einfach als Schlüssel- und Wertewörterbuch gespeichert werden, wobei der Schlüssel die Raum-ID und der Wert ein Array der Räume ist, zu denen er führt.

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

Agentenschnittstelle

Zuerst sollten wir uns überlegen, welche Informationen der Agent aus der Umgebung lernen kann und welche Vorgänge er ausführen kann. Dies vereinfacht das Nachdenken über den Algorithmus.

In diesem Fall sollte der Agent in der Lage sein, die Umgebung nach der ID des Raums abzufragen, in dem er sich befindet. Er sollte in der Lage sein, die Anzahl der Türen in dem Raum zu ermitteln, in dem er sich befindet ( beachten Sie, dass dies nicht die ID der Räume ist, in denen er sich befindet Türen führen zu! ) und er sollte sich durch Angabe eines Türindex durch eine Tür bewegen können. Alles andere, was ein Agent weiß, muss vom Agenten selbst herausgefunden werden.

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

Agentenwissen

Wenn der Agent die Karte zum ersten Mal betritt, kennt er nur die Anzahl der Türen im Raum und die ID des Raums, in dem er sich gerade befindet. Ich musste eine Struktur erstellen, in der Informationen gespeichert werden, die der Agent gelernt hat, z. B. welche Türen er nicht war durch, und wohin die Türen dazu führen, war durch gewesen.

Diese Klasse repräsentiert die Informationen zu einem einzelnen Raum. Ich habe mich dafür entschieden, die nicht besuchten Türen als setund die besuchten Türen als zu speichern dictionary, wobei der Schlüssel die Tür-ID und der Wert die ID des Raums ist, zu dem er führt.

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

Agentenalgorithmus

• Jedes Mal, wenn der Agent einen Raum betritt, durchsucht er sein Wissenswörterbuch nach Informationen über den Raum. Wenn für diesen Raum keine Einträge vorhanden sind, wird ein neuer erstellt RoomKnowledgeund dieser dem Wissenswörterbuch hinzugefügt.

• Es wird geprüft, ob der aktuelle Raum der Zielraum ist. Wenn ja, wird es zurückgegeben.

• Wenn es Türen in diesem Raum gibt, die wir nicht besucht haben, gehen wir durch die Tür und lagern, wohin sie führen. Wir setzen dann die Schleife fort.

• Wenn es keine nicht besuchten Türen gab, gehen wir zurück durch die Räume, die wir besucht haben, um eine mit nicht besuchten Türen zu finden.

Die AgentKlasse erbt von der AgentInterfaceKlasse.

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)

Unterstützende Funktionen

Ich musste eine Funktion schreiben, die einen Schlüssel in einem Wörterbuch mit einem bestimmten Wert findet, da wir beim Zurückverfolgen die ID des Raums kennen, zu dem wir gelangen möchten, aber nicht, welche Tür wir verwenden müssen, um dorthin zu gelangen.

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

Testen

Ich habe alle Kombinationen der Start- / Endposition in der oben angegebenen Karte getestet. Für jede Kombination werden die besuchten Räume ausgedruckt.

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

Anmerkungen

Das Backtracking ist nicht sehr effizient - im schlimmsten Fall könnte es durch jeden Raum gehen, um zu einem angrenzenden Raum zu gelangen, aber das Backtracking ist ziemlich selten - in den obigen Tests wird es nur dreimal zurückverfolgt. Ich habe es vermieden, Ausnahmebehandlungen einzufügen, um den Code kurz zu halten. Kommentare zu meinem Python sind willkommen :)

Im Wesentlichen haben Sie ein Richtungsdiagramm, in dem jeder verbundene Raum durch zwei unbekannte Passagen verbunden ist - eine in beide Richtungen. Angenommen, Sie beginnen im Knoten 1und in den Türen Aund Bführen hinaus. Sie wissen nicht, was sich hinter jeder Tür befindet, also wählen Sie einfach die Tür aus A. Sie erhalten auf Raum 2, die Türen hat C, Dund E. Sie wissen jetzt, dass die Tür Avon Raum 1zu Raum führt 2, aber Sie wissen nicht, wie Sie zurückkommen sollen, also wählen Sie zufällig die Tür aus C. Du kommst zurück ins Zimmer 1! Jetzt wissen Sie, wie Sie zwischen Zimmern 1und 2. Erforschen Sie weiter durch die nächste unbekannte Tür, bis Sie den Ausgang finden!

Da die Räume in den Ausgangslisten immer in der gleichen Reihenfolge sind, können wir eine schnelle Karte der Räume erstellen, während wir nach einem Ausgang suchen.

Mein Pseudocode ist etwas Javaisch, sorry, ich habe ihn in letzter Zeit oft benutzt.

Unvisited_Rooms ist eine Hashmap mit einer Raum-ID und einer Liste von Indizes der nicht zugeordneten Räume oder eines 2D-Arrays, je nachdem, was funktioniert.

Ich stelle mir vor, der Algorithmus könnte ungefähr so ​​aussehen:

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)

Sie müssen einen der allgemeinen Knotenpfadfinder für PathTo () - Räume auf der "Karte" verwenden. Hoffentlich ist das klar genug, um Ihnen den Einstieg zu erleichtern.

Ich bin mir Ihrer Anforderungen nicht ganz klar, aber wenn Folgendes zulässig ist, kann es ein einfach zu befolgender Algorithmus sein. Wahrscheinlich ein Fehler, zumal es eine rekursive Funktion verwendet. Außerdem wird geprüft, ob eine Tür zu dem Raum führt, aus dem Sie gekommen sind, aber ich weiß nicht, wie ein Rundweg mit drei Räumen funktionieren würde. In diesen drei Räumen wird möglicherweise eine ewige Schleife durchgeführt. Möglicherweise müssen Sie einen Verlauf hinzufügen, um sicherzustellen, dass kein Raum zweimal überprüft wird. Aber indem Sie Ihre Beschreibung lesen, ist dies möglicherweise nicht zulässig.

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

[Bearbeiten] 'ID' zur vorherigen Prüfung hinzugefügt und aktualisiert, um die Objektorientierung zu verbessern.

Die kurze Antwort lautet Tiefensuche mit Backtracking. Sie können zuerst die Breite machen, wenn Sie es vorziehen, aber Ihr kleiner Roboter wird dann viel mehr hin und her laufen.

Genauer gesagt, nehmen wir an, wir haben gegeben:

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

Um den Ausgang zu finden, brauchen wir nur:

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

Rufen Sie escape()mit der ID des Startraums an und der Roboter wird zum Ausgang gebracht (durch Anrufen moveTo()).