stringtranslate.com

Problema de encuentro

El dilema del encuentro es un dilema lógico, típicamente formulado de esta manera:

Dos personas tienen una cita en un parque en el que nunca han estado. Al llegar por separado al parque, ambos se sorprenden al descubrir que es un espacio enorme y, en consecuencia, no pueden encontrarse. En esta situación, cada persona tiene que elegir entre esperar en un lugar fijo con la esperanza de que la otra lo encuentre o comenzar a buscar a la otra con la esperanza de que haya elegido esperar en algún lugar.

Si ambos eligen esperar, nunca se encontrarán. Si ambos eligen caminar, hay posibilidades de que se encuentren y posibilidades de que no. Si uno elige esperar y el otro elige caminar, entonces existe una certeza teórica de que finalmente se encontrarán; sin embargo, en la práctica, puede que pase demasiado tiempo para que esto esté garantizado. La pregunta que se plantea, entonces, es: ¿qué estrategias deberían elegir para maximizar su probabilidad de encontrarse?

Ejemplos de esta clase de problemas son conocidos como problemas de encuentro . Estos problemas fueron introducidos por primera vez de manera informal por Steve Alpern en 1976, [1] y formalizó la versión continua del problema en 1995. [2] Esto ha llevado a mucha investigación reciente en búsqueda de encuentro. [3] Incluso el problema de encuentro simétrico jugado en n ubicaciones discretas (a veces llamado el Problema de Encuentro del Café de Mozart ) [4] ha resultado ser muy difícil de resolver, y en 1990 Richard Weber y Eddie Anderson conjeturaron la estrategia óptima. [5] En 2012 la conjetura fue probada para n = 3 por Richard Weber . [6] Este fue el primer problema de búsqueda de encuentro simétrico no trivial en ser completamente resuelto. El problema de encuentro asimétrico correspondiente tiene una solución óptima simple: un jugador se queda quieto y el otro jugador visita una permutación aleatoria de las ubicaciones.

Además de ser problemas de interés teórico, los problemas de encuentro incluyen problemas del mundo real con aplicaciones en los campos de sincronización , diseño de sistemas operativos , investigación de operaciones e incluso planificación de operaciones de búsqueda y rescate .

Problema de encuentro determinista

El problema de encuentro determinista es una variante del problema de encuentro en el que los jugadores, o robots , deben encontrarse entre sí siguiendo una secuencia determinista de instrucciones. Aunque cada robot sigue la misma secuencia de instrucciones, se utiliza una etiqueta única asignada a cada robot para romper la simetría . [7]

Véase también

Referencias

  1. ^ Alpern, Steve (1976), Juegos de escondite , seminario, Institut fur Hohere Studien, Viena, 26 de julio.
  2. ^ Alpern, Steve (1995), "El problema de la búsqueda de encuentros", SIAM Journal on Control and Optimization , 33 (3): 673–683, doi :10.1137/S0363012993249195, MR  1327232
  3. ^ Alpern, Steve ; Gal, Shmuel (2003), La teoría de los juegos de búsqueda y encuentro , International Series in Operations Research & Management Science, vol. 55, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-7468-1, Sr.  2005053.
  4. ^ Alpern, Steve (2011), "Juegos de búsqueda de encuentros", en Cochran, James J. (ed.), Wiley Encyclopedia of Operations Research and Management Science , Wiley, doi :10.1002/9780470400531.eorms0720.
  5. ^ Anderson, EJ; Weber, RR (1990), "El problema del encuentro en posiciones discretas", Journal of Applied Probability , 27 (4): 839–851, doi :10.2307/3214827, JSTOR  3214827, MR  1077533, S2CID  122587972.
  6. ^ Weber, Richard (2012), "Búsqueda de encuentro simétrica óptima en tres ubicaciones" (PDF) , Matemáticas de la investigación de operaciones , 37 (1): 111–122, doi :10.1287/moor.1110.0528, MR  2891149.
  7. ^ Ta-Shma, Amnon; Zwick, Uri (abril de 2014). "Encuentros deterministas, búsquedas de tesoros y secuencias de exploración fuertemente universales". ACM Transactions on Algorithms . 10 (3). 12. doi :10.1145/2601068. S2CID  10718957.