Jeśli w labiryncie zagubiły się dwie osoby, czy istnieje algorytm, którego oboje mogą użyć do znalezienia siebie nawzajem bez uprzedniego uzgodnienia, jakiego algorytmu będą używać?
Myślę, że ten algorytm ma pewne cechy:
- Każda osoba musi być w stanie wyprowadzić ją za pomocą logiki, która nie przyjmuje żadnych założeń na temat tego, co druga osoba decyduje, ale ponieważ każda osoba wie, że druga osoba jest w tej samej pozycji, może dokonywać dedukcji na temat tego, co druga musi decydować.
- Identyczny algorytm musi być wyprowadzony przez obie osoby, ponieważ w ich sytuacjach występuje całkowita symetria (żadna nie ma żadnej wiedzy na temat pozycji początkowej drugiej, a labirynt ma ustalony rozmiar i jest w pełni zmapowany przez obie). Należy pamiętać, że algorytm nie musi być deterministyczny: dopuszcza się losowość.
Odpowiedzi:
Nazywa się to problemem spotkania .
Jako artykuł: Mobile Agent Rendezvous: Wspomniane badanie , ten problem został pierwotnie zaproponowany przez Alpern: Problem wyszukiwania Rendezvous :
W powyższym artykule ankietowym
Obejmuje on zarówno „Asymetryczne rendez-vous” (w rozdziale 4), jak i „Symetryczne rendez-vous” (w rozdziale 5).
W przypadku symetrycznego spotkania spotkanie Alpern pokazuje:
źródło
Właściwie zrobi to każdy spójny, wstępnie ustalony schemat.
Na przykład:
Lub nawet prościej
Ten program zagwarantuje, że ludzie się spotkają (ale może to zająć trochę czasu)
Czemu? Ponieważ schemat jest spójny dla obu i nie prowadzi do ślepej uliczki. Ponieważ labirynt jest skończony i połączony, po skończonym czasie się spotkają.
Jeśli schemat nie jest spójny, nie ma gwarancji, że spełnią, ponieważ mogą doprowadzić do zamkniętych pętli.
Jeśli mają tę samą prędkość, to w zależności od architektury labiryntu, np. Labiryntu cyklicznego, możliwe jest, że zawsze znajdą się w punktach antydymetrycznych labiryntu, a zatem nigdy się nie spotkają, mimo że schemat jest spójny.
Z powyższego jasno wynika, że program musi być wstępnie ustalony, ale zrobi to każdy spójny wstępnie ustalony schemat.
W przeciwnym razie można polegać na analizie probabilistycznej i wnioskować, że z dużym prawdopodobieństwem się spełnią, ale prawdopodobieństwo to nie jest jedno (tj. We wszystkich przypadkach).
Można również rozważyć coś przeciwnego do zbornego problemu , z problemu unikania gdzie celem jest dla agentów zawsze unikać siebie .
Rozwiązaniem problemu unikania jest dokładne odzwierciedlenie siebie przez agentów. Oznacza to, że to, co robi jeden agent drugi, powinno to odzwierciedlać. Ponieważ problem unikania ma również rozwiązanie , jasne jest, że strategie dla problemu spotkania, które mogą prowadzić do refleksyjnych zachowań agentów, nie mogą zagwarantować rozwiązania.
Można powiedzieć, że strategią problemu unikania jest równoległość (tj. Maksymalny punkt rozbieżności), podczas gdy strategią problemu spotkania jest ortogonalność (tzn. Najmniej zbieżny punkt)
Powyższą analizę można przekształcić w algorytm losowy, który nie przyjmuje wstępnie ustalonych ról dla agentów, takich jak:
To średnio doprowadzi do spotkania ludzi, ale nie jest to zagwarantowane we wszystkich przypadkach.
Jeśli założymy, że agenci mogą pozostawić ślady , np. Etykiety ich (bieżącego) kierunku i prędkości. Następnie drugi agent może wykorzystać te ślady jako informacje do dostosowania zarówno własnego kierunku, jak i prędkości (patrz poniżej).
Ten rodzaj problemu jest przykładem globalnej optymalizacji wykorzystującej tylko informacje lokalne . Innymi słowy, sposób mapowania globalnych ograniczeń na lokalne . Ten bardziej ogólny problem (który obejmuje problem spotkania) jest omawiany w tym poście math.se (i odnośnikach) „Metody przełożenia globalnych ograniczeń na lokalne”
źródło