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