Dada la imagen a continuación, necesito detectar la secuencia más óptima en el tablero (la línea verde). Las líneas azules / rojas representan posibles, pero no los mejores movimientos.
Estas son las reglas:
- Puede moverse a cualquier mosaico que sea el mismo y sea su vecino (la diagonal es válida)
- Una vez que haya visitado un mosaico, no podrá volver a visitarlo.
He pensado en recorrer cada nodo y mirar a sus vecinos, luego pasar recursivamente. Una vez que encuentre un posible movimiento, puedo ponerlo en una estructura. Una vez que se encuentran todos los movimientos posibles, simplemente elijo el movimiento con el mayor conteo de nodos. Se vuelve más difícil cuando un nodo tiene más de un vecino que coincide.
Entonces, ¿hay algún algoritmo que pueda usar? Estaba pensando en algún tipo de inundación, pero eso no cumple con las reglas # 2.
Según lo solicitado, aquí hay un video de juego similar. http://youtube.com/watch?v=eumnCTG0AE8
Respuestas:
Puede considerar cada grupo de símbolos idénticos vinculados (y por vinculado quiero decir que puede viajar de un símbolo a otro) un gráfico separado . Para cada gráfico de este tipo, aplique una Búsqueda de profundidad primero (DFS) comenzando desde cada nodo en el gráfico que ya no es parte de la ruta más larga para ese gráfico . Cada vez que llegue a un callejón sin salida mientras aplica un DFS, verifique si la ruta que acaba de atravesar es más larga que el máximo global que ha encontrado hasta ahora. Si es así, guárdelo como el nuevo camino más largo.
Notarás que en el párrafo anterior mencioné la aplicación de un DFS varias veces para cada gráfico. Un solo DFS ejecutado en un gráfico no sería suficiente. Considere este caso particular:
Si por casualidad primero ejecutara un DFS en este gráfico en el nodo superior, descubriría que la ruta más larga posible es la línea vertical, pero eso no sería correcto. Esto sucedería cada vez que inicie el algoritmo DFS en un nodo que esté en algún lugar dentro de la ruta resultante o que no sea parte de ella. Lo que debe hacer en este ejemplo en particular también es iniciar un algoritmo DFS desde el nodo más a la izquierda en la segunda línea. Eso encontrará el camino correcto. En términos generales, necesitará ejecutar algoritmos DFS en cada nodo que actualmente no es parte de la ruta más larga para ese gráfico, como se indicó anteriormente.
El peor de los casos para este algoritmo sería un tablero lleno o mayormente lleno con un solo tipo de símbolo, sin embargo, es poco probable que suceda en el juego. Además, tenga cuidado de cómo almacena las rutas más largas para cada gráfico. Si no optimiza este bit, es mejor que solo llame a un DFS para cada nodo en el escenario. Suponiendo que no trabajas con tableros muy grandes y que la velocidad no es un problema tan grande, esta solución debería ser lo suficientemente rápida.
Técnicamente hablando, al dividir su tablero en gráficos separados, termina con múltiples " problemas de ruta más larga ". Como podemos ver en su ejemplo, puede tener ciclos en su gráfico (por ejemplo, tener todos los símbolos en el exterior de la etapa del mismo tipo), lo que significa que en este problema particular necesita encontrar la ruta más larga en varios gráficos cíclicos no dirigidos, que no se pueden hacer en tiempo polinómico .
Si encuentra que esto es demasiado lento, vea esta respuesta en StackOverflow para obtener más detalles sobre cómo optimizar los "Problemas de ruta más larga" individuales.
fuente