Wenn sich zwei Personen in einem Labyrinth verirren, gibt es dann einen Algorithmus, mit dem beide sich finden können, ohne vorher vereinbart zu haben, welchen Algorithmus sie verwenden werden?
Ich denke, dass es einige Eigenschaften gibt, die dieser Algorithmus haben wird:
- Jede Person muss in der Lage sein , um es Logik ableiten verwenden , die keine macht Annahmen über das, was die andere Person zu entscheiden, aber wie jede Person die andere in der gleichen Position kennt kann sie machen Abzüge über das, was der andere muss entscheiden werden.
- Ein identischer Algorithmus muss von beiden Personen abgeleitet werden, da in ihren Situationen eine vollständige Symmetrie besteht (keine hat Kenntnisse über die Startposition der anderen und das Labyrinth hat eine feste Größe und wird von beiden vollständig abgebildet). Beachten Sie, dass der Algorithmus nicht deterministisch sein muss: Er darf randomisiert werden.
Antworten:
Dies wird als Rendezvous-Problem bezeichnet .
Wie im Artikel: Mobile Agent Rendezvous: Eine Umfrage erwähnt, ist dieses Problem ursprünglich von Alpern vorgeschlagen worden : Das Rendezvous-Suchproblem :
In der Umfrage oben,
Es behandelt sowohl "Asymmetrisches Rendezvous" (in Abschnitt 4) als auch "Symmetrisches Rendezvous" (in Abschnitt 5).
Für ein symmetrisches Rendezvous zeigt das Papier von Alpern:
quelle
Tatsächlich reicht jedes im Voraus festgelegte Schema aus.
Beispielsweise:
Oder noch einfacher
Dieses Schema garantiert, dass die Leute sich irgendwann treffen (aber es kann einige Zeit dauern)
Warum? Denn das Schema ist für beide gleich und führt auch nicht zu einer Sackgasse. Da das Labyrinth endlich ist und verbunden ist, werden sie sich nach einer endlichen Zeit treffen.
Wenn das Schema nicht konsistent ist, gibt es keine Garantie dafür, dass es erfüllt wird, da dies zu geschlossenen Kreisläufen führen kann.
Wenn sie die gleiche Geschwindigkeit haben, ist es abhängig von der Architektur des Labyrinths, z. B. eines zyklischen Labyrinths, möglich, dass sie sich immer an antidiametrischen Punkten des Labyrinths befinden und sich daher niemals treffen, obwohl das Schema konsistent ist.
Aus dem oben Gesagten geht klar hervor, dass das Schema vorab festgelegt werden muss, aber jedes konsistente vorab festgelegte Schema reicht aus.
Ansonsten kann man sich auf probabilistische Analysen verlassen und daraus schließen, dass sie mit großer Wahrscheinlichkeit aufeinandertreffen werden, aber diese Wahrscheinlichkeit ist nicht eine (dh unter allen Umständen).
Man kann auch die Umkehrung des Rendezvous-Problems betrachten , das Vermeidungsproblem, bei dem es das Ziel ist, dass sich die Agenten immer gegenseitig meiden .
Die Lösung für das Vermeidungsproblem besteht darin, dass sich die Agenten genau widerspiegeln. Das heißt, dass das, was ein Agent dem anderen antut, die Reflexion dessen tun sollte. Da das Vermeidungsproblem auch eine Lösung hat , ist klar, dass Strategien für das Rendezvous-Problem, die zum Reflexionsverhalten der Agenten führen können, keine Lösung garantieren können.
Man kann sagen, dass die Strategie für das Vermeidungsproblem Parallelisierung (dh maximaler Divergenzpunkt) ist, während die Strategie für das Rendezvous-Problem Orthogonalität (dh am wenigsten konvergenter Punkt) ist.
Die obige Analyse kann in einen zufälligen Algorithmus umgewandelt werden, der keine vorher festgelegten Rollen für die Agenten übernimmt, wie z.
Dies führt im Durchschnitt zu Treffen, ist jedoch nicht in allen Fällen garantiert.
Wenn wir davon ausgehen, dass die Agenten Spuren hinterlassen können , zB Beschriftungen ihrer (aktuellen) Richtung und Geschwindigkeit. Der andere Agent kann diese Traces dann als Information verwenden, um sowohl seine eigene Richtung als auch seine eigene Geschwindigkeit anzupassen (siehe unten).
Diese Art von Problem ist ein Beispiel für eine globale Optimierung, bei der nur lokale Informationen verwendet werden . Oder mit anderen Worten, eine Möglichkeit, globale Einschränkungen auf lokale Einschränkungen abzubilden . Dieses allgemeinere Problem (das das Rendezvous-Problem zusammenfasst) wird in diesem math.se-Beitrag (und den darin enthaltenen Verweisen) "Methoden zum Übersetzen globaler Einschränkungen in lokale Einschränkungen" behandelt.
quelle