algorithm - a star implementation
¿Cómo resolver de manera óptima el rompecabezas de inundación? (10)
Me gusta jugar al juego de rompecabezas Flood-It, que se puede jugar en línea en:
https://www.lemoda.net/javascript/flood-it/game.html
También está disponible como un gadget de iGoogle. El objetivo es llenar todo el tablero con el menor número de inundaciones sucesivas.
Intento escribir un programa que pueda resolver este rompecabezas de manera óptima. ¿Cuál es la mejor manera de abordar este problema? Idealmente, quiero usar el algoritmo A * , pero no tengo idea de cuál debería ser la función que calcula el número de pasos que quedan. Escribí un programa que realizó una búsqueda de fuerza bruta en profundidad 4 para maximizar el área llena. Funcionó razonablemente bien y me ganó para resolver el acertijo, pero no estoy completamente satisfecho con ese algoritmo.
¿Alguna sugerencia? Gracias por adelantado.
A * es solo una búsqueda de gráficos priorizados. Cada nodo es un estado de juego, clasifica los nodos según alguna heurística y siempre expande el nodo de menor costo esperado final. Siempre que su heurística no subestime los costos, la primera solución que encuentre tendrá la garantía de ser óptima.
Después de jugar los juegos unas cuantas veces, descubrí que al intentar perforar en la esquina opuesta, todas las curvas tendían a dar como resultado una victoria. Por lo tanto, una buena estimación del costo de inicio sería (costo hasta el momento) + un número suficiente de rellenos para llegar a la esquina opuesta [nota: no es mínimo, solo es suficiente. Solo ávidamente llene hacia la esquina para calcular la heurística].
Aquí hay una idea para implementar el gráfico para apoyar la heurística de Smashery .
Represente cada grupo de cuadrados contiguos del mismo color en un conjunto disjunto y una lista de grupos de cuadrados adyacentes. Un relleno de inundación combina un conjunto con todos sus conjuntos adyacentes y fusiona las listas de adyacencia. Esta estructura gráfica implícita te permitirá encontrar la distancia desde la esquina superior izquierda hasta el nodo más lejano.
Como heurística, podría construir un gráfico donde cada nodo represente un conjunto de cuadrados contiguos del mismo color y cada nodo esté conectado a los que toca. (Cada borde ponderado como 1). A continuación, puede usar un algoritmo de búsqueda de ruta para calcular la "distancia" desde la parte superior izquierda a todos los otros nodos. Luego, al observar los resultados del llenado de inundaciones usando cada uno de los otros 5 colores, determine cuál minimiza la distancia al nodo "más alejado", ya que ese será probablemente su cuello de botella.
Agregue el resultado de ese cálculo a la cantidad de rellenos realizados hasta el momento y úselo como su heurística A *.
Creo que podrías considerar el número de cuadrados que coinciden o no coinciden con el color actual. Entonces, su medida heurística de "distancia" sería la cantidad de cuadrados en el tablero que no son del mismo color que el color elegido, en lugar del número de pasos.
Después de jugar un par de veces, noté que una buena estrategia es ir siempre "profundo", ir por el color que va más lejos en el territorio no inundado.
He estado trabajando en esto, y luego de que mi solucionador funcionara, eché un vistazo a los enfoques que otros habían tomado.
La mayoría de los solucionadores que existen son heurísticos y no garantizan la optimalidad. La heurística observa la cantidad de cuadrados y la distribución de los colores que no se han elegido, o la distancia al cuadrado "más alejado". La combinación de una buena heurística con DFS limitado (o BFS con lookahead) da como resultado soluciones que son bastante rápidas para la grilla estándar de 14x14.
Tomé un enfoque un poco diferente porque estaba interesado en encontrar el camino probadamente óptimo, no solo uno "bueno". Observé que el espacio de búsqueda en realidad crece mucho más lento que el factor de bifurcación del árbol de búsqueda, porque hay bastantes posiciones duplicadas. (Con una estrategia de profundidad primero, es importante mantener un historial para evitar un trabajo redundante.) El factor de ramificación efectivo parece más cercano a 3 que a 5.
La estrategia de búsqueda que tomé fue realizar BFS hasta una profundidad de "punto medio" donde el número de estados se volvería inviable, en algún lugar entre 11 y 13 movimientos funciona mejor. Luego, examino cada estado en la profundidad del punto medio y realizo un nuevo BFS comenzando con eso como la raíz. Ambas búsquedas de BFS se pueden eliminar eliminando estados encontrados en profundidades anteriores, y la última búsqueda puede estar limitada por la profundidad de la solución más conocida. (Una heurística aplicada al orden de los subárboles examinados en el segundo paso probablemente también ayude a algunos).
La otra técnica de poda que demostró ser clave para un solucionador rápido es simplemente verificar si quedan más de N colores, si está a pocos pasos de la mejor solución actual.
Una vez que sabemos qué estado del punto medio está en el camino hacia una solución óptima, el programa puede realizar el DFS usando ese estado del punto medio como objetivo (y podando cualquier camino que seleccione un cuadrado que no esté en el punto medio). O podría ser factible construye los caminos en los pasos de BFS, a costa de algo de memoria adicional.
Mi solucionador no es muy rápido, pero puede encontrar una solución óptima garantizada en no más de un par de minutos. (Consulte http://markgritter.livejournal.com/673948.html o el código en http://pastebin.com/ZcrS286b ).
No estoy seguro, pero estoy bastante seguro de que esto podría resolverse con avidez. Está intentando reducir el número de campos de color a 1, por lo que reducir más campos de color antes no debería ser menos eficiente que reducir menos antes.
1) Defina una colección de grupos de colores similares existentes.
2) Para cada colección, cuente el número de colecciones vecinas por color. El mayor recuento de colecciones vecinas con un solo color es el peso de esta colección.
3) Tome la colección con el recuento más alto de vecinos con un solo color y llénela a ese color. Combine las colecciones y actualice la clasificación para todas las colecciones afectadas por la combinación (todos los nuevos vecinos de la colección fusionada).
En general, creo que esto debería calcularse en tiempo O (n log n), donde n es el número de píxeles y el registro (n) solo proviene de mantener la lista ordenada de ponderaciones.
No estoy seguro de si debe haber un desempate para cuando varios campos tienen el mismo peso. Tal vez el desempate va al color que es común para la mayoría de los grupos en el mapa.
De todos modos, tenga en cuenta que el objetivo del juego es reducir el número de campos de color distintos y no maximizar el perímetro, ya que los diferentes esquemas de color ocasionalmente pueden hacer que un campo más grande sea una opción subóptima. Considera el campo:
3 3 3 3 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
El color 1 tiene el perímetro más grande en cualquier medida, pero el color 2 es la elección óptima.
EDITAR>
Rasca eso. El ejemplo:
3 1 3 1 3
1 1 1 1 1
1 1 1 1 1
2 2 2 2 2
1 2 2 2 2
Invalida mi propio algoritmo codicioso. Pero no estoy convencido de que se trata de un cruce de gráficos simple, ya que el cambio a un color compartido por 2 vecinos visita 2 nodos, y no 1.
La eliminación del color probablemente debería tener algún papel en la heurística.
1) Nunca es correcto rellenar con un color que no está ya en el gráfico.
2) Si hay un campo de color con un color único, se requerirá al menos un relleno para él. No se puede combinar con ningún otro relleno. Creo que esto significa que es seguro llenarlo más temprano que tarde.
3) El algoritmo codicioso para conteo de campo vecino tiene sentido para un mapa de 2 colores.
Un algoritmo "codicioso" ingenuo es elegir el siguiente paso que maximice el perímetro general de la región principal.
(Un par de inteligentes amigos míos estaban pensando en esto el otro día y decidieron que el optimium puede ser NP-hard (por ejemplo, debes usar fuerza bruta) - No sé si son correctos (no estaba cerca para escuchar el razonamiento y no lo he pensado yo mismo).)
Tenga en cuenta que para los pasos de cálculo, supongo que el algoritmo de unión-encuentro es su amigo, hace que la informática sea ''un paso'' muy rápida (consulte, por ejemplo, esta publicación de blog ).
Una heurística ingenua podría ser utilizar la cantidad de colores que quedan (menos 1); esto es admisible porque tomará al menos tantos clics despejar el tablero.
La respuesta de Smashery puede ser ligeramente ajustada. Para el número total de movimientos estimados, si hay ''k'' colores a la distancia máxima, agregue ''k-1'' al número de movimientos estimados.
En general, para cada color, tenga en cuenta la distancia máxima a la que se puede borrar el color. Esto nos da un diccionario que mapea algunas distancias máximas a un número distinto de cero de colores que se pueden borrar a esa distancia. Sume el valor-1 a través de las teclas y agréguelo a la distancia máxima para obtener una estimación de varios movimientos.
Además, hay ciertos casos gratuitos. Si en algún punto podemos borrar un color en un movimiento, podemos tomar ese movimiento sin considerar los otros movimientos.