english - day to day algorithms
¿Pueden dos grupos de N personas encontrarse entre sí alrededor de un círculo? (11)
Este es un problema algorítmico y no estoy seguro de que tenga una solución. Creo que es un caso específico de un problema informático más genérico que no tiene solución, pero prefiero no revelar cuál para evitar sesgos de plantación. Surgió de una situación de la vida real en la que los teléfonos móviles no tenían crédito y, por lo tanto, no teníamos comunicaciones de largo alcance.
Dos grupos de personas, cada uno con 2 personas (pero podría ser cierto para N personas) se reunieron en el centro de un parque, pero al momento de la reunión, el parque está cerrado. Ahora, tendrán que encontrarse en algún otro lugar alrededor del parque. ¿Existe un algoritmo que todos y cada uno de los individuos puedan seguir para converger en un solo punto?
Por ejemplo, si cada grupo se divide en dos y da la vuelta y cuando encuentran a otra persona que sigue con esa persona, todos convergen en el otro lado del parque. Pero si el otro grupo hace lo mismo, entonces, no podrían llevar a los miembros encontrados del otro grupo con ellos. Esta no es una solución posible.
No estoy seguro si expliqué lo suficientemente bien. Puedo intentar dibujar un diagrama.
Solución determinista para N > 1, K > 1
Para N grupos de K personas cada uno.
Dado que el problema se basa en personas cuyos teléfonos móviles no tienen crédito, supongamos que cada persona en cada grupo tiene su propio teléfono. Si eso no es aceptable, entonces sustituya el teléfono con una tarjeta de crédito, seguridad social, licencia de conducir o cualquier otro elemento con identificación numérica que se garantiza que sea única.
En cada grupo, cada persona debe recordar el número más alto entre ese grupo, y la persona con el número más alto ( leader etiquetado) debe viajar en el sentido de las agujas del reloj alrededor del perímetro mientras el resto del grupo se queda quieto.
Después de que el leader de cada grupo se encuentra con el siguiente grupo, comparan su número con el número de leader anterior del grupo.
Si el número del líder es más alto que el número del líder anterior del grupo, entonces el líder y el grupo continúan a lo largo del perímetro del parque. Si el número del líder anterior del grupo es más alto, entonces todos se quedan quietos.
Finalmente, el leader con el número más alto continuará alrededor de todo el perímetro exactamente 1 rotación, reuniendo a todo el grupo.
Solución determinista para N > 1, K = 1 (con un supuesto razonable de conocimiento anticipado)
En este caso, cada grupo solo contiene una persona. Supongamos que el número utilizado es un número de teléfono, porque entonces es razonable suponer que al menos un par de personas sabrán los números de cada uno y, por lo tanto, uno de ellos se quedará.
Para N = 2 , esto se reduce trivialmente a una persona que se queda donde está y la otra persona que gira en el sentido de las agujas del reloj.
Para otros casos, el hecho de que al menos dos personas se conozcan inicialmente los números de cada uno aumentará efectivamente el máximo de K a al menos 2 (porque la persona o las personas que se quedan se mantendrán si la persona que conocen tiene un número más alto que el leader que aparece para reunirse con ellos), pero todavía tenemos que introducir un paso más en el algoritmo para asegurarnos de que termine.
El paso adicional es que si un leader ha continuado alrededor del perímetro durante exactamente una rotación sin agregar a nadie al grupo, entonces el leader debe dejar atrás a su grupo y comenzar de nuevo para una rotación más alrededor del perímetro. Esto significa que un leader sin grupo continuará indefinidamente hasta que encuentre a alguien más, lo que es bueno.
Con este paso adicional, es fácil ver por qué tenemos que asumir que al menos un par de personas necesitan saber los números de teléfono de cada uno de antemano, porque entonces podemos garantizar que la persona que se quede en el lugar acumulará todo el grupo. .
Siéntase libre de dejar comentarios o sugerencias para mejorar el algoritmo que he presentado o desafíeme si cree que me he perdido un caso de ventaja. Si no, espero que te haya gustado mi respuesta.
Actualizar
Por diversión, decidí escribir una demostración visual de mis soluciones al problema usando d3 . Siéntase libre de jugar con los parámetros y reinicie la simulación con cualquier estado inicial. Aquí está el enlace:
https://jsfiddle.net/patrob10114/c3d478ty/show/
Llave
- negro - líder
- blanco - seguidor
- cuando se hace clic
- azul - persona seleccionada
- verde - conocido por la persona seleccionada
- rojo - desconocido por persona seleccionada
Tenga en cuenta que la collaboration produce al comienzo de cada step , por lo que si dos grupos se combinan en el paso actual, la mayoría de las personas no conocerán a las personas del grupo opuesto hasta después de que se invoque el siguiente step .
Aquí hay algunas soluciones que para mí no son satisfactorias, ya que requieren que los dos equipos acuerden una estrategia por adelantado y todos siguen las mismas reglas deterministas o probabilísticas. Si tuvo la oportunidad de acordar de antemano las reglas que todos seguirán, entonces, como señala Flyx, podría haber acordado un punto de encuentro de respaldo. Las restricciones que impiden la elección anticipada de un lugar en particular o de un líder en particular son estándar en el contexto de algunos problemas con las redes de computadoras pero claramente poco natural para cuatro amigos que planean reunirse. Por lo tanto, enmarcaré una estrategia desde el punto de vista de un solo equipo, suponiendo que no haya habido una discusión previa del escenario entre los dos equipos.
Tenga en cuenta que no es posible ser sólido ante ninguna estrategia del otro equipo. El otro equipo siempre puede forzar un estancamiento simplemente adoptando algún patrón de movimiento que garantice que esos dos nunca volverán a encontrarse.
Uno de ustedes se pasea por el parque. El otro se detiene, digamos en la posición X. Esto garantiza que: (a) se encontrarán periódicamente en X, digamos cada T segundos; y (b) para cada miembro del otro equipo, sin importar cómo se muevan alrededor del perímetro del parque, deben encontrar al menos uno de su equipo al menos cada T segundos.
Ahora tiene comunicación entre todos los miembros de ambos grupos y (dado el tiempo suficiente y la transmisión de mensajes de una persona a otra), el problema se resuelve con el mismo problema como si sus teléfonos móviles estuvieran funcionando. Elegir un líder por número aleatorio es una forma de resolverlo como otros lo han sugerido. Tenga en cuenta que todavía hay dos problemas: el primero es un problema de dos generales con la comunicación, y supongo que puede sentir que una conversación de teléfono móvil permite la generación de conocimiento común, mientras que estas notas transmitidas no lo hacen. La segunda es la posibilidad de que el otro equipo se niegue a cooperar y usted no puede acordar un punto de reunión sin importar qué.
A pesar de los problemas anteriores, la pregunta supone que si tuvieran comunicación, los grupos podrían acordar un punto de reunión. Tienes comunicación: acuerda un punto de encuentro!
En cuanto a cómo acordar un punto de encuentro, creo que requiere cierta apelación a la razón o buena intención por parte del otro equipo. Si deben volver a reunirse, entonces serán muy reacios a tomar cualquier acción que les permita romper su compromiso con su pareja. Por lo tanto, sugiérales que después de su próxima reunión , cuando todos los compromisos puedan ser perdonados, procedan juntos a X por la ruta más corta. Escuche su contrapropuesta y trate de encontrar alguna solución común.
Para ayudar a llegar a una solución, podría acordar previamente con su compañero de equipo algunas variaciones que estaría dispuesto a hacer a su plan, siempre que se mantengan dentro de algunas restricciones que aseguren que volverá a encontrarse con su compañero de equipo. Por ejemplo, si el compañero de equipo estacionario está de acuerdo en que puede ser persuadido para que salga en el sentido de las agujas del reloj, y el compañero de equipo en movimiento lo hace en contra de las manecillas del reloj y está de acuerdo en que puede ser persuadido para hacer algo diferente pero no para cruzar el punto X en el sentido de las agujas del reloj, entonces tiene la garantía de volver a reunirse y, por lo tanto, puede aceptar ciertas sugerencias del otro equipo.
A modo de ejemplo, si un equipo que sigue esta estrategia se encuentra con un equipo (imprudentemente) que sigue su estrategia, entonces uno de mi equipo estará de acuerdo con el de su equipo con el que se encuentre, y el otro se negará (ya que sería necesario para hacer el movimiento prohibido arriba). Esto significa que cuando su equipo se reúna, tendrán a uno de mi equipo con ellos para un grupo de tres. El miembro suelto de mi equipo está en un curso de colisión con ese grupo de tres siempre que su equipo no haga nada perverso.
Creo que formar un grupo de tres es una victoria, por lo que cada miembro debe hacer todo lo posible para asistir a una reunión del otro equipo, sujeto a las limitaciones que acordaron para garantizar que se reunirán con su propio miembro del equipo nuevamente. Un grupo de 3, una vez formado, debe seguir cualquier acuerdo que exista para cumplir con el miembro suelto (y si el equipo de dos que figura dentro de esos 3 se niega a hacer esto, entonces son saboteadores, no hay una buena razón para que se nieguen ). Dentro de estas restricciones, cualquier tipo de ruptura de simetría permitirá al equipo que sigue estos principios persuadir / seguir al otro equipo a una reunión de tres vías y luego a una de cuatro.
En general, se requiere cierta ruptura de simetría, aunque solo sea porque ambos equipos podrían estar siguiendo mi estrategia y, por lo tanto, ambos tienen un miembro estacionario en diferentes puntos.
Cada grupo envía un explorador con los miembros restantes del grupo que permanecen inmóviles. Cada grupo recuerda el nombre de su explorador. Los exploradores dan vueltas en el sentido de las agujas del reloj y, cuando se encuentra con un grupo, comparan los nombres de sus exploradores:
- Si el nombre del explorador es anterior alfabéticamente: el grupo lo sigue.
- Si el nombre del explorador es más tarde: se une al grupo y abandona su identidad de grupo inicial.
Para cuando el explorador con el nombre más bajo vuelva a su ubicación inicial, todos los que no se hayan detenido en su ubicación inicial deberían seguirlo.
Cada grupo se dividirá en dos partes, y cada parte girará alrededor del círculo en la dirección opuesta (en sentido horario y antihorario).
Antes de comenzar, eligen algún tipo de número aleatorio (en un rango lo suficientemente grande como para que no haya posibilidad de que dos grupos tengan el mismo número ... o un Guid en informática: identificador único global). Así que un número único por grupo.
Si las personas del mismo grupo se reúnen primero (las dos partes se encuentran), están solos, por lo que probablemente los otros grupos (si los hubiera) se dieron por vencidos.
Si dos grupos se reúnen: siguen la regla que dice que el número más grande marca el camino. Entonces, cuando se encuentran, continúan en la dirección que tenían las personas con el mayor número.
Al final, la dirección del número más grande los llevará a todos a un punto.
Si no tienen computadora para elegir este número, cada grupo podría usar los nombres completos de las personas del grupo fusionadas.
Edit : perdón, acabo de ver que esto está muy cerca de la solución de Patrick Roberts
Otra edición : ¿y si cada grupo tiene su propia estrategia determinista? En la solución anterior, todo funciona bien si todos los grupos tienen la misma estrategia. Pero en un problema de la vida real, este no es el caso (ya que no se pueden comunicar).
Si un grupo tiene una estrategia determinista y los otros no, pueden aceptar el enfoque determinista y todo está bien.
Pero si dos grupos tienen enfoques deterministas (simplemente, por ejemplo, lo mismo que antes, pero un grupo usa el número más grande y el otro grupo sigue el número más bajo).
¿Hay una solución para eso?
Deben moverse hacia el punto más al norte del parque.
Enviaría a ambos grupos en una dirección aleatoria. Si dieron media vuelta sin reunirse con el otro grupo, vuelva a aleatorizar las instrucciones. Esto hará que se reúnan en algunas rondas la mayor parte del tiempo, sin embargo, hay una posibilidad infinitamente pequeña de que nunca se encuentren.
Esta pregunta depende en gran medida del tipo de operaciones que tengamos y de cómo considere que se ve su entorno. Le hice estas preguntas sin respuesta, así que aquí está mi interpretación:
El parque es un espacio 2d, 2 grupos se ubican al azar, cada grupo tiene la misma derecha / izquierda (ambos están mirando hacia el parque). Ambos tienen las mismas operaciones, están programadas para hacer absolutamente las mismas cosas (nada como lo hago a la derecha y tú vas a la izquierda, porque esto hace que el problema sea obvio). Así que las operaciones son: Ir a la derecha / izquierda / parar por x unidades de tiempo. También pueden darse cuenta de que pasaron por su posición original (aquella en la que comenzaron). Y se pueden programar en un bucle.
Si tienes la habilidad de usar la aleatoriedad, todo es simple. Puedes llegar a muchas soluciones. Por ejemplo: con una probabilidad de 0.5, cada uno de ellos decide que harán 3 pasos correctamente y esperarán. O un paso a la derecha y espera. Si va a realizar esta operación en un bucle y seleccionarán diferentes opciones, entonces claramente se encontrarán (una es más rápida que la otra, por lo que llegará a una persona más lenta). Si ambos seleccionan la misma operación, formarán un círculo y ambos alcanzarán sus posiciones iniciales. En este caso tira los dados una vez más. Después de N círculos, la probabilidad de que se encuentren será de 1 a 0.5 ^ n (que se acerca a 1 muy rápido)
No es posible con un algoritmo determinista si
- • Tenemos que encontrarnos en algún punto del perímetro,
- • no podemos distinguir los puntos en el perímetro (o el algoritmo no está autorizado a usar dicha distinción),
- • no podemos distinguir a los individuos en los grupos (o el algoritmo no está autorizado a usar tal distinción),
- • el perímetro es circular ( ver más abajo para un caso más general ),
- • todos seguimos el mismo algoritmo, y
- • los puntos iniciales pueden estar en cualquier parte del perímetro.
Prueba : con un algoritmo determinista podemos deducir las posiciones finales a partir de las posiciones iniciales, pero los grupos podrían comenzar uniformemente espaciados alrededor del perímetro, en cuyo caso el problema tiene simetría rotacional, por lo que la solución no se modificará con una rotación de 1 / n. que sin embargo no tiene punto fijo en el perímetro.
Estado de los supuestos Abandonar varios supuestos potenciales, como otros han observado varias soluciones:
- No determinista : como han observado otros, varios algoritmos no deterministas proporcionan una solución cuya probabilidad de terminación tiende a ser cierta a medida que el tiempo tiende a infinito; Sospecho que casi cualquier caminata aleatoria haría. ( Muchas respuestas )
- Puntos indistinguibles : acuerde un punto fijo en el cual se reunirá si es necesario: la respuesta de flyx .
- Individuos indistinguibles : si existe un algoritmo hash perfecto, elija aquellos con el hash más bajo para recolectar otros: la solución de Patrick Roberts .
- Mismo algoritmo : elija uno por adelantado para recolectar los otros (adaptando la solución de Patrick Roberts ).
Otras suposiciones pueden ser debilitadas:
- Perímetro no circular : la condición de que el perímetro sea circular es bastante artificial, pero si el perímetro es topológicamente equivalente a un círculo, esta equivalencia se puede usar para convertir cualquier solución en una solución al problema del círculo.
- Puntos iniciales no restringidos : incluso si los puntos iniciales no pueden estar espaciados uniformemente, siempre que algunos puntos sean distintos, una equivalencia topológica (como en un perímetro no circular) reduce la solución de una solución al caso circular, lo que demuestra que no hay solución. existe.
Creo que esta pregunta realmente pertenece a Computer Science Stack Exchange .
Sorprendentemente, hay una manera de hacerlo! Pero primero tenemos que definir nuestros términos y suposiciones.
Tenemos N = 2 "equipos" de K = 2 "agentes" cada uno. Cada "agente" está ejecutando el mismo programa. No pueden distinguir el norte desde el sur, pero sí pueden distinguirlo en el sentido de las agujas del reloj. Agentes en el mismo lugar pueden hablar entre ellos; Los agentes en diferentes lugares no pueden.
Su respuesta parcial sugerida fue: "Si cada grupo se divide en dos y da la vuelta y cuando encuentran a otra persona que sigue con esa persona, todos convergerían al otro lado del parque ..." Esto implica que nuestros agentes tienen algún protocolo de decisión cara a cara (mágico, axiomático), de manera que si Alice y Bob están en el mismo equipo y se despiertan en el mismo punto del círculo, pueden (mágicamente, axiomáticamente) decidir entre ellos que Alice se dirigirá en el sentido de las agujas del reloj y Bob se dirigirá en sentido contrario a las agujas del reloj (a diferencia de Alicia y Bob que siempre van exactamente en la misma dirección porque, por definición, reaccionan exactamente de la misma manera en la situación en la que se encuentran).
Una forma de implementar este protocolo de decisión mágica es dar a cada agente un generador personal de números aleatorios . Cada vez que se reúnen 2 o más agentes en un cierto punto, todos tiran un dado de un millón de caras, y el que salga más alto se reconoce como el líder. Entonces, en su solución parcial, Alice y Bob podrían rodar: quien gane más (el "líder") va en el sentido de las agujas del reloj y envía al otro agente (el "seguidor") en el sentido contrario a las agujas del reloj.
De acuerdo, después de haber resuelto el problema de "cómo toman decisiones nuestros agentes", ¡resolvamos el enigma real!
Supongamos que nuestros equipos son (Alice y Bob) y (Carl y Dave). Alice y Carl son los líderes elegidos inicialmente.
Paso 1: Cada equipo tira un dado de un millón de caras para generar un número aleatorio. La semántica de este número es "El equipo con el número más alto es el Equipo Maestro", pero por supuesto, ningún equipo sabe ahora quién tiene el número más alto. Pero Alice y Bob saben que su número es, digamos 424202, y Carl y Dave, ambos saben que su número es 373287.
Paso 2: Cada equipo envía a su líder alrededor del círculo en el sentido de las agujas del reloj, mientras que el seguidor permanece inmóvil. Cada líder deja de moverse cuando llega a donde el seguidor del otro equipo está esperando. Así que ahora en un punto del círculo tenemos a Alice y Dave, y en el otro punto tenemos a Carl y Bob.
Paso 3: Alice y Dave comparan números y se dan cuenta de que el equipo de Alice es el Equipo Maestro. Del mismo modo, Bob y Carl comparan los números y se dan cuenta de que el equipo de Bob es el Equipo Maestro.
Paso 4: Alice es la líder del Equipo Maestro, lleva a Dave con ella en el sentido de las agujas del reloj alrededor del círculo. Bob y Carl (siendo seguidor y líder de un equipo no maestro respectivamente) simplemente se quedan quietos. Cuando Alice y Dave llegan a Bob y Carl, ¡el problema está resuelto!
Tenga en cuenta que el Paso 1 requiere que ambos equipos tiren un dado de un millón de caras de forma aislada ; si durante el Paso 3 todos se dan cuenta de que hubo un empate, solo tendrán que retroceder y volver a intentarlo. Por lo tanto, esta solución aún es probabilística ... pero puede hacer que el tiempo esperado sea arbitrariamente pequeño simplemente reemplazando los dados de millones de caras de todos con los dados de billones de caras, de quinientos lados, de bazillones.
La estrategia general aquí es imponer un orden jerárquico en todos los agentes N × K, y luego hacerlos rebotar alrededor del círculo hasta que todos estén conscientes del orden jerárquico; luego el picoteador superior puede barrer alrededor del círculo y recoger a todos.
Se puede imponer un orden jerárquico usando los generadores personales de números aleatorios de los agentes.
El protocolo para K> 2 agentes por equipo es idéntico al caso K = 2: simplemente se reúnen todos los seguidores en el Paso 1. Alice (el líder) va en el sentido de las agujas del reloj mientras que Bob neric (los seguidores) se queda quieto; y así.
El protocolo para K = 1 agentes por equipo es ... bueno, es imposible, porque no importa lo que hagas, no puedes asegurarte de manera determinista de que alguien se encontrará con otro agente. Usted necesita una forma para que los agentes se aseguren, sin comunicarse en absoluto , de que no todos girarán en sentido horario alrededor del parque para siempre.
Una cosa que ayudaría con (pero no resolver técnicamente) el caso K = 1 sería considerar las velocidades relativas de los agentes. Puede estar familiarizado con el algoritmo de "Tortuga y liebre" de Floyd para encontrar un bucle en una lista vinculada . Bueno, si se permite que los agentes se muevan a velocidades no idénticas, entonces ciertamente podría hacer una versión "continua, de múltiples hare" de ese algoritmo:
Paso 1: Cada agente tira un dado de un millón de caras para generar un número aleatorio S , y comienza a correr en sentido horario alrededor del parque a la velocidad S.
Paso 2: Cada vez que un agente alcanza a otro, ambos agentes se juntan y comienzan a correr en sentido horario a una nueva velocidad aleatoria.
Paso 3: Eventualmente, asumiendo que nadie eligió exactamente las mismas velocidades aleatorias , todos se habrán reunido.
Este protocolo requiere que Alice y Carl no lancen números idénticos en sus dados de millones de caras, incluso cuando están cruzando el parque entre sí . En mi humilde opinión, esta es una suposición muy diferente de la del otro protocolo, asumiendo que Alice y Bob podrían tirar números diferentes en sus dados de un millón de lados cuando estaban en el mismo lugar . Con K = 1, nunca se nos garantiza que dos agentes estarán en el mismo lugar.
De todos modos, espero que esto ayude. La solución para N> 2 equipos se deja como un ejercicio para el lector, pero mi intuición es que será fácil reducir el caso N> 2 al caso N = 2.
Supongamos que el parque es un círculo. (por el bien de la claridad)
Grupo A
- Persona A.1
- Persona A.2
Grupo b
- Persona B.1
- Persona B.2
Nosotros (grupo A) estamos actualmente en la parte inferior del círculo (90 grados). Acordamos ir hacia 0 grados en direcciones opuestas . Soy la persona A.1 y voy en el sentido de las agujas del reloj. Yo envío la persona A.2. sinistrórsum.
En cualquier escenario posible (B se divide, B no se divide, B tiene el mismo esquema, B tiene un esquema detallado), cada grupo puede tener información conflictiva. Entonces, a menos que el Grupo A tenga un arma para obligar al Grupo B a someterse, los nuevos grupos podrían tomar decisiones conflictivas al reunirse.
Digamos por ejemplo, A.1. cumple B.1, y A.2. cumple con B.2. ¿Qué hacemos (A.1 y B.1) si B tiene el mismo esquema? Dado que los nuevos grupos no pueden saber lo que decide el otro grupo (si ir con el esquema de A, o el esquema de B), cada grupo puede tomar una decisión diferente.
Y terminaremos donde empezamos ... (es decir, dos personas a 0 grados y dos personas a 90 grados). Llamemos a este punto de control "Primera iteración".
Podríamos explicar esto y decir que crearemos un esquema para la "Segunda Iteración". Pero entonces vuelve a pasar lo mismo. Y para la tercera iteración, cuarta iteración, ad infinitum.
Cada iteración tiene un 50% de probabilidad de no funcionar.
Lo que significa que después de x iteraciones, sus posibilidades de no encontrarse en un punto común son a lo sumo 1- (0.5 ^ x)
NB: Pensé en un montón de escenarios, como que el Grupo A aceptara regresar a su punto inicial y se comunicaran entre sí lo que el Grupo B planea hacer. Pero ningún cigarro, incluso con esquemas muy inteligentes, siempre surge el problema de la información conflictiva.
Un problema interesante por cierto. Me gustaría sugerir mi versión de la solución:
0 Cada grupo elige un líder.
1: Líder y seguidores van en direcciones opuestas
2: Se encuentran con otros líderes de grupo o seguidores.
3: Siguen yendo en la misma dirección que antes, 90 grados de magnitud.
4: Para este momento, todos los grupos han hecho un semicírculo alrededor del perímetro, e invariablemente se han vuelto a encontrar con líderes, los suyos u otros.
5: Todos los líderes cambian la dirección del siguiente paso a la de los seguidores y ordenan que sigan.
6: Unidades de todos los grupos se reúnen en un punto.
Consulte el archivo adjunto para una explicación detallada. Necesitará MS Office Powerpoint 2007 o más reciente para verlo. En caso de que no tengas uno, usa pptx. visor (visor de Powerpoint) como una alternativa gratuita.
EDITAR: hice un error tipográfico en la primera diapositiva. Se lee "Amarillo y rojo están seleccionados", mientras que debe ser "Azul y rojo" en su lugar.