Kroki gwarantujące wyjście z labiryntu

14

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.

seilgu
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Dyskretna jaszczurka
Strategia Eppsteina dla automatów monotonicznych polega na grupowaniu stanów, aby zamiast szukać ścieżki w pełnym zestawie stanów mocy szuka ścieżki na wykresie z wielomianowo wieloma wierzchołkami. Najbardziej naturalnym uogólnieniem przedziałów na 2D, o którym myślę, jest wypukły kadłub, ale niestety nie jest jasne, czy ich liczba rośnie wielomianowo .
Peter Taylor

Odpowiedzi:

-1

A

vonbrand
źródło
Nie można zakodować podążania za ścianą jako stałej sekwencji kierunków kardynalnych. Wybory zależą od ścian wokół ciebie, co jest szczególnie niedozwolone przez pytanie.
Curtis F
Jeśli znasz najkrótszą ścieżkę, możesz ją zakodować jako „przesuń w lewo, a następnie prosto, a następnie ...”. Jeśli nie znasz najkrótszej ścieżki, nie możesz podać takich wskazówek dla najkrótszego wyjścia. Jeśli nie znasz ścieżki, nie możesz podać wskazówek, jak się wydostać.
vonbrand,