Si dos personas se pierden en un laberinto, ¿hay algún algoritmo que ambos puedan usar para encontrarse sin haber acordado previamente qué algoritmo usarán?
Creo que hay algunas características que tendrá este algoritmo:
- Cada persona debe poder derivarlo utilizando una lógica que no haga suposiciones sobre lo que la otra persona está decidiendo, pero como cada persona sabe que la otra está en la misma posición, puede hacer deducciones sobre lo que la otra persona debe decidir.
- Ambas personas deben derivar un algoritmo idéntico, ya que existe una simetría total en sus situaciones (ninguno de los dos tiene ningún conocimiento sobre la posición inicial del otro, y el laberinto es de un tamaño fijo y ambos están completamente mapeados). Tenga en cuenta que no se requiere que el algoritmo sea determinista: se le permite ser aleatorizado.
Respuestas:
Esto se llama problema de encuentro .
Como el documento: Mobile Agent Rendezvous: una encuesta mencionada, este problema es original propuesto por Alpern: The Rendezvous Search Problem :
En la encuesta anterior,
Cubre tanto "Cita asimétrica" (en la Sección 4) como "Cita simétrica" (en la Sección 5).
Para una cita simétrica, el artículo de Alpern muestra:
fuente
En realidad, cualquier esquema preestablecido consistente servirá.
Por ejemplo:
O incluso más simple
Este esquema garantizará que las personas se reúnan eventualmente (pero puede llevar algún tiempo)
¿Por qué? Porque el esquema es consistente para ambos y tampoco conduce a un callejón sin salida. Entonces, dado que el laberinto es finito y está conectado, después de un tiempo finito se encontrarán.
Si el esquema no es consistente, no hay garantía de que se cumplirán, ya que pueden dar lugar a lazos cerrados.
Si tienen la misma velocidad, entonces, dependiendo de la arquitectura del laberinto, por ejemplo, un laberinto cíclico, entonces es posible que siempre puedan estar en puntos antidiaméticos del laberinto, por lo tanto, nunca se encontrarán, aunque el esquema sea consistente.
Está claro a partir de lo anterior que el esquema necesita ser arreglado previamente, pero cualquier esquema consistente previamente arreglado servirá.
De lo contrario, se puede confiar en el análisis probabilístico e inferir que con una gran probabilidad se encontrarán, pero esta probabilidad no es una (es decir, en todos los casos).
También se puede considerar lo contrario del problema de la cita , el problema de evitación donde el objetivo es que los agentes siempre se eviten mutuamente .
La solución al problema de la evitación es que los agentes se reflejen entre sí exactamente. Lo que significa que lo que un agente hace al otro debe reflejar eso. Dado que el problema de evitación también tiene una solución , está claro que las estrategias para el problema de la cita que pueden conducir al comportamiento de reflexión de los agentes no pueden garantizar la solución.
Se puede decir que la estrategia para el problema de evitación es la paralelización (es decir, el punto de divergencia máxima), mientras que la estrategia para el problema de encuentro es la ortogonalidad (es decir, el punto de menor convergencia)
El análisis anterior se puede convertir en un algoritmo aleatorio que no asume roles preestablecidos para los agentes, como los siguientes:
En promedio, esto llevará a que las personas se reúnan eventualmente, pero no está garantizado en todos los casos.
Si suponemos que los agentes pueden dejar rastros , por ejemplo, etiquetas de su dirección y velocidad (actual). Luego, el otro agente puede usar estos rastros como información para ajustar tanto su propia dirección como su velocidad (ver más abajo).
Este tipo de problema es un ejemplo de optimización global utilizando solo información local . O, en otras palabras, una forma de asignar restricciones globales a restricciones locales . Este problema, más general (que subsume el problema de la cita) se aborda en esta publicación de math.se (y sus referencias) "Métodos para traducir restricciones globales a restricciones locales"
fuente