Esto parecía un problema muy interesante, así que seguí adelante y lo probé:
Resumen del problema (para personas que no han analizado el problema):
- Hay N <= 100 hormigas en pista circular
- La pista tiene 1000 metros de largo
- Se da la posición inicial de las hormigas (son distintas)
- La hormiga viaja 0.1 metros por segundo
- Algunas hormigas caminan en sentido horario, otras hormigas caminan en sentido antihorario alrededor de la pista
- Cuando dos hormigas se encuentran en un punto, cambian de dirección (el costo de cambiar de dirección es de 0 segundos)
- Encuentre el número máximo de colisiones (hormigas que se encuentran en el mismo punto), si se le permite elegir la dirección inicial de las hormigas
- Las hormigas corren durante 10 ^ 9 + 6 segundos alrededor de la pista.
Aquí hay algunas observaciones que lo ayudarán a resolver el problema:
- ¿Cómo predicen las señales de tráfico en las autopistas cuánto tiempo llevará llegar desde su posición actual a un destino más adelante?
- ¿Qué algoritmos de programación de procesos usa Android?
- ¿Qué algoritmo se debe usar para encontrar que hay una conexión en cada dos vértices en un gráfico dirigido?
- ¿Puedes compartir tu algoritmo de encontrar la longitud del AP más largo en una matriz dada?
- ¿Qué tan útil es el algoritmo genético?
1) Puede ignorar los cambios de dirección debido a que las hormigas chocan:
¿Por qué? Supongamos que dos hormigas estaban a punto de chocar:
Antes de la colisión:
(ant1)> <(ant2)
Después de que dos hormigas chocan y cambian de dirección, se vería algo así:
Sin embargo, tenga en cuenta que no distinguimos entre hormigas diferentes, por lo que podría tratarlo como si dos hormigas se “pasaran”:
Las dos situaciones anteriores son equivalentes, ya que todas las hormigas son idénticas (hubiera sido un problema mucho más difícil si este no fuera el caso). Esto significa que puedes tratar la dirección de todas las hormigas para que se arreglen.
2) En el caso óptimo, N / 2 de la hormiga viaja en la dirección opuesta:
Esto no es difícil de ver, una vez que ignoras el cambio de dirección. Si dos hormigas viajan en la misma dirección, nunca chocarán, por lo que sería óptimo hacer que la mitad de ellas viajen en la dirección opuesta.
3) La dirección inicial de las hormigas no importa (a excepción de un caso muy especial discutido en 4):
¿Por qué? Considere el caso cuando la hormiga está en la posición 500 y 502. ¿Cuántas veces chocarán? Si viajaron uno frente al otro (distancia más corta), se encontrarán después de 10 segundos (1 metro cada uno) y colisionarán cada 5000 segundos, encontrándose por última vez a 999995010 segundos. Si viajaron uno frente al otro (mayor distancia), se encontrarán después de 4990 segundos, por última vez en 999999990 segundos. (999999990-999995010) = 4980 <5000, por lo que se encontraron con la misma cantidad de tiempo independientemente de la dirección en que viajaron.
4) Que importan 6 segundos adicionales:
¿Qué pueden hacer esos 6 segundos adicionales por ti? En 6 segundos, la hormiga puede viajar 0.6 metros, lo que significa que si dos hormigas están dentro de la distancia 1, si caminan una hacia la otra chocarán. Esto significa que si hay dos hormigas con una distancia inicial entre ellas de 1 metro, querrás hacer que se enfrenten para que puedan chocar una vez más usando los primeros 5 segundos.
Eso debería ser suficiente para resolver el problema. Como el tamaño del problema es pequeño, no hay necesidad de optimizarlo.
