Biorąc pod uwagę dwuwymiarowy labirynt, w którym możesz wydać 4 polecenia „ruch w górę / dół / prawo / lewo”. Znając labirynt, ale nie wiedząc, gdzie jest człowiek, jak znaleźć minimalną sekwencję poleceń, która gwarantuje wyjście z labiryntu? Szukam pojedynczej sekwencji poleceń, która zadziała bez względu na to, od którego miejsca w labiryncie zaczniesz.
Załóż, że jeśli nasz partner otrzyma polecenie „przesuń w prawo”, gdy po prawej stronie jest ściana, po prostu pozostanie tam, gdzie jest.
Innymi słowy, otrzymaliśmy labirynt i musimy wybrać sekwencję poleceń. Następnie nasz partner zostanie umieszczony gdzieś w labiryncie i będzie postępował zgodnie z sekwencją poleceń, które wcześniej wybraliśmy. Chcemy, aby ta sekwencja sprawiła, że nasz partner ucieknie, bez względu na to, gdzie początkowo został umieszczony nasz partner. Zauważ, że dozwolone komendy nie mają żadnych instrukcji warunkowych, więc nie mogą one zachowywać innej sekwencji w zależności od partnera.
Czy istnieje algorytm wielomianowy do konstruowania takiej sekwencji, biorąc pod uwagę opis labiryntu?
Yuval Filmus wspomina, że jest to szczególny przypadek synchronicznego zadania tekstowego i może być związany z uniwersalnymi sekwencjami przechodzenia. Znalazłem również artykuł, który wydaje się istotny:
Problem równoczesnego rozwiązywania labiryntu . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.
Niestety dla ogólnych wykresów wydaje się to nierozwiązanym problemem, ale zastanawiam się, czy może istnieć dobry algorytm dla tego konkretnego przypadku. Wymyśliłem podejście kandydujące: Oznacz każdą pozycję liczbą minimalnych kroków wymaganych do wyjścia i śledź każdego agenta w labiryncie. Możliwe jest wykonanie wyszukiwania A * w ten sposób.
źródło
Odpowiedzi:
źródło