Rozwiązywanie labiryntu bez możliwości powrotu

Muszę napisać program, który rozwiąże labirynt. Labirynt ma strukturę graficzną, w której każdy węzeł - niektóre pomieszczenia i krawędzie - wychodzi do innych pomieszczeń:

Specyfikacja:

• Zaczynamy od przypadkowego pokoju.
• Labirynt ma ślepe zaułki, 0 lub kilka wyjść.
• Nic nie wiemy o całym labiryncie, tylko liczba bieżącego pokoju i lista drzwi z niego.
• Kiedy wchodzimy do nowego pokoju, nie wiemy, skąd przyszliśmy (jakie drzwi z obecnego pokoju prowadzą nas z powrotem do poprzedniego pokoju).
• Możemy rozpoznać, kiedy dotrzemy do wyjścia.
• Z każdego kroku przechodzimy z bieżącego pokoju do dostępnych drzwi.
• Jeśli na przykład jesteśmy w pokoju 6, nie możemy po prostu przejść do początku. To jak ruch robota.
• Znamy dokładnie identyfikator aktualnego pokoju. Znamy identyfikator każdego drzwi w bieżącym pokoju (nie we wszystkich labiryncie).
• Kontrolujemy robota.

Przejrzałem wszystkie znane algorytmy, ale wszystkie one wymagają co najmniej dodatkowej umiejętności powrotu do poprzedniego pokoju. Zgodnie ze specyfikacją nie możemy używać żadnych algorytmów, które szukają najkrótszej ścieżki (właściwie nie potrzebuję najkrótszej), ponieważ wiemy tylko o bieżącym pokoju. Nie możemy używać algorytmów śledzących lewą (prawą) rękę, ponieważ nie znamy kierunku wyjścia. Prawdopodobnie jedynym rozwiązaniem spełniającym specyfikację jest wybranie losowego wyjścia w każdym pokoju w nadziei, że znajdzie się jakieś wyjście czasowe ...

Wszelkie sugestie, jak rozwiązać taki labirynt w bardziej inteligentny sposób?

Hmm, znasz numer rzeczywistego pokoju. Możesz więc zbudować strukturę danych. Wydaje mi się, że lista wyjść nie ma dołączonych numerów pokoi. Ale po wybraniu jednego losowo wiesz przynajmniej, że istnieje połączenie.

Powiedz, że jesteś w pokoju 4 i wybierz jedno z trzech losowych wyjść. Teraz system mówi ci, że jesteś w pokoju 6 i masz tylko jedno wyjście. Wybierasz to i wracasz do pokoju 4. W tym momencie zebrałeś trochę informacji o strukturze labiryntu. Teraz wybierasz inne wyjście i kończysz w pokoju 5. Informacje o pokoju 4 (jedno wyjście do 6, jedno wyjście do 5)

Czy możesz wybrać konkretne wyjście? czy są one ponumerowane, powiedzmy, że jeśli w pokoju 4 wybierzesz wyjście, zawsze kończysz na 6? W przeciwnym razie możesz przynajmniej dowiedzieć się o możliwych trasach.

Ok, po prostu przeczytaj swój komentarz. Więc jeśli wyjścia mają identyfikatory, a te są statycznie powiązane z pokojem (nawet jeśli nie wiesz, który z nich na początek), po prostu wybierz nowy i zapamiętaj połączenia wyjścia / pokoju i pamiętaj, które wyjście zostało już wypróbowane. Wypróbuj nieosiągalne wyjścia, dopóki nie przeszukasz każdego pokoju.

W ten sposób jest to naprawdę proste. Po kilku krokach powinieneś mieć mniej lub bardziej kompletną listę połączeń. Dopiero po wejściu do nowego pokoju możesz (kilka kroków) biegać losowo. Ale z każdym krokiem dostajesz więcej informacji i za każdym razem, gdy wchodzisz do odwiedzonego pokoju, możesz podjąć mądrzejszą decyzję (nie testować ślepego zaułka w pokoju 6, na przykład, gdy wrócisz do 4, ponieważ nie ma żadnych wyjść, które nie zostały przetestowane).

Edytuj Pomysł polega na tym, aby najpierw wykonać losowe kroki i zapisać informacje, które znajdziesz, tak jak to opisałem (opis Dana jest bardziej zwięzły). Jeśli znajdziesz się w pokoju bez nieznanych wyjść, możesz użyć dowolnego znanego pathfindera, aby znaleźć najkrótszą drogę do pokoju z wyjściami, których jeszcze nie eksplorowałeś.

Nie jestem w 100% pewien, ale myślę, że Peter Norvig napisał o podobnym problemie (labirynt Wumpus) w swojej książce „Artificial Intelligence: A Modern Approach”. Chociaż, jeśli dobrze pamiętam, chodziło nie tyle o wyszukiwanie ścieżek, co o podejmowanie decyzji dotyczących niektórych informacji, które system mógłby uzyskać na temat sąsiednich pokoi.

Edytować:

Nie, to nie tylko losowe. Śledząc już wypróbowane wyjścia, usuwasz niepotrzebną redundancję. W rzeczywistości nie musisz nawet wybierać losowo.

Załóżmy, że zaczynasz w pokoju 4. Otrzymane informacje: 3 wyjścia A, B, C Zawsze wybierasz pierwsze nieużywane wyjście. Więc zacznij od A. Skończyłeś w pokoju 6. Teraz pamiętasz 4A => 6 (i użyłeś) w pokoju 6, otrzymujesz info 1 wyjście A. Ponownie wybierasz pierwsze nieużywane (aw tym przypadku tylko wyjście) Powrót do pokoju za znajomość 6A => 4 (i żadnych dalszych wyjść w pokoju 6) Teraz wybierasz następne wyjście B i osiągasz pokój 5 ...

Wcześniej czy później przeszukasz wszystkie pokoje w ten sposób. Ale w kwestii systemowej.

Jedynym powodem, dla którego potrzebujesz znalezienia ścieżki, jest znalezienie się w pokoju, w którym wszystkie wyjścia są już zbadane. Następnie będziesz chciał znaleźć bezpośrednią drogę do następnego pokoju z niezbadanymi wyjściami, aby przejść na własną rękę podczas wyszukiwania. Główną sztuczką jest więc mniej wiedzieć, które wyjście prowadzi do którego pokoju (choć może to być pomocne), ale śledzenie jeszcze nie wypróbowanych wyjść.

W ten sposób można na przykład uniknąć ciągłego biegania w kółko, co stanowiłoby ryzyko dla podejścia czysto losowego.

W twoim przykładzie labirynt najprawdopodobniej nie miałoby to większego znaczenia. Ale w dużym labiryncie z wieloma pokojami i połączeniami oraz być może trudnymi, okrągłymi pokojami system ten gwarantuje, że wyjdziesz z jak najmniejszą liczbą prób.

(Myślę, że to prawdopodobnie ten sam system, co Byte56 wymyślił w Gamers)

Rozumiem, że prawdopodobnie masz sedno z innych odpowiedzi, ale to było zabawne pytanie i miałem ochotę zrobić trochę programowania w języku Python. To jest moje podejście obiektowe. Wcięcie określa zakres.

Reprezentacja wykresu

Wykres można łatwo zapisać jako klucz, słownik wartości, w którym klucz jest identyfikatorem pokoju, a wartością jest tablica pokoi, do których prowadzi.

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

Interfejs agenta

Najpierw powinniśmy pomyśleć o tym, jakie informacje agent powinien móc wyciągnąć ze środowiska i jakie operacje powinien wykonać. Uprości to myślenie o algorytmie.

W takim przypadku agent powinien mieć możliwość zapytania środowiska o identyfikator pokoju, w którym się znajduje, powinien być w stanie uzyskać liczbę drzwi w pokoju, w którym się znajduje ( uwaga: nie jest to identyfikator pokoju, w którym drzwi prowadzą do! ) i powinien być w stanie przejść przez drzwi, określając indeks drzwi. Wszystko, co wie agent, musi być zrozumiane przez samego agenta.

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

Wiedza agenta

Gdy agent po raz pierwszy wchodzi na mapę, zna tylko liczbę drzwi w pokoju i identyfikator pokoju, w którym aktualnie się znajduje. Musiałem stworzyć strukturę, która przechowywałaby informacje, których agent się nauczył, takie jak drzwi, których nie było przez i tam, gdzie prowadzą do tego drzwi, już było.

Ta klasa reprezentuje informacje o jednym pokoju. Zdecydowałem się przechowywać nie odwiedzone drzwi jako a, seta odwiedzane drzwi jako dictionary, gdzie kluczem jest identyfikator drzwi, a wartością jest identyfikator pokoju, do którego prowadzi.

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

Algorytm agenta

• Za każdym razem, gdy agent wchodzi do pokoju, przeszukuje słownik wiedzy w celu uzyskania informacji o pokoju. Jeśli nie ma żadnych wpisów dla tego pokoju, to tworzy nowy RoomKnowledgei dodaje go do swojego słownika wiedzy.

• Sprawdza, czy bieżący pokój jest pokojem docelowym, a jeśli tak, to wraca.

• Jeśli w tym pokoju są drzwi, których nie odwiedziliśmy, przechodzimy przez drzwi i przechowujemy je tam, gdzie prowadzą. Następnie kontynuujemy pętlę.

• Jeśli nie było żadnych nieodwiedzonych drzwi, cofamy się przez odwiedzone pokoje, aby znaleźć drzwi z niezapowiedzianymi drzwiami.

W Agentklasa dziedziczy z AgentInterfaceklasy.

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)

Funkcje pomocnicze

Musiałem napisać funkcję, która znalazłaby klucz w słowniku o podanej wartości, ponieważ podczas cofania znamy identyfikator pokoju, do którego próbujemy się dostać, ale nie wiemy, które drzwi użyć, aby się do niego dostać.

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

Testowanie

Testowałem wszystkie kombinacje pozycji początkowej / końcowej na mapie podanej powyżej. Dla każdej kombinacji drukuje odwiedzone pokoje.

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

Notatki

Cofanie nie jest bardzo wydajne - w najgorszym przypadku może przejść przez każdy pokój, aby dostać się do sąsiedniego pokoju, ale cofanie jest dość rzadkie - w powyższych testach cofa się tylko trzy razy. Unikałem wprowadzania obsługi wyjątków, aby kod był zwięzły. Doceniam wszelkie komentarze na temat mojego Pythona :)

Zasadniczo masz wykres kierunkowy, w którym każde połączone pomieszczenie jest połączone dwoma nieznanymi pasażami - jednym w obu kierunkach. Powiedz, że zaczynasz w węźle 1, drzwiach Ai Bwyprowadzasz. Nie wiesz, co kryje się za drzwiami, więc po prostu wybierasz drzwi A. Można dostać się do pokoju 2, który ma drzwi C, Di E. Teraz wiesz, że drzwi Aprowadzą z pokoju 1do pokoju 2, ale nie wiesz, jak się odzyskać, więc losowo wybierasz drzwi C. Wracasz do pokoju 1! Teraz wiesz, jak dostać się między pokojami 1i 2. Kontynuuj eksplorację najbliższych nieznanych drzwi, aż znajdziesz wyjście!

Ponieważ pokoje są zawsze w tej samej kolejności na listach wyjściowych, możemy zrobić szybką mapę pokoi, szukając wyjścia.

Mój pseudo-kod jest nieco Javaish, przepraszam, ostatnio dużo go używałem.

Unvisited_Rooms to skrót mapy z identyfikatorem pokoju i listą indeksów niezamapowanych pokoi lub tablicą 2d, cokolwiek działa.

Wyobrażam sobie, że algorytm mógłby wyglądać mniej więcej tak:

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)

Musisz użyć jednego z typowych wyszukiwarek ścieżek do pokojów PathTo () na całej „mapie”. Mam nadzieję, że to wystarczająco jasne, aby zacząć od czegoś.

Nie jestem zbyt jasny na temat twoich wymagań, ale jeśli dozwolone są następujące, algorytm może być prosty do naśladowania. Prawdopodobnie jest tam błąd, zwłaszcza, że ​​używa funkcji rekurencyjnej. Sprawdza również, czy drzwi prowadzą do pokoju, z którego przyszedłeś, ale nie wiem, jak poradziłaby sobie okrągła ścieżka z trzema pokojami, może po prostu zapętlać w nieskończoność w tych trzech pokojach. Konieczne może być dodanie historii, aby upewnić się, że pokój nie jest dwukrotnie sprawdzany. Ale po przeczytaniu opisu może to być niedozwolone.

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

[Edytuj] Dodano „id” do poprzedniej kontroli i zaktualizowano, aby bardziej zorientować obiektowo.

Krótka odpowiedź to wyszukiwanie w pierwszej kolejności z cofaniem. Jeśli wolisz, możesz zrobić pierwszy krok, ale wtedy twój mały robot będzie dużo więcej chodził tam iz powrotem.

Mówiąc konkretniej, załóżmy, że otrzymaliśmy:

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

Aby znaleźć wyjście, potrzebujemy tylko:

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

Zadzwoń escape()z identyfikatorem pokoju początkowego, a robot przeniesie się do wyjścia (dzwoniąc moveTo()).