Comment résoudre de manière optimale le puzzle flood fill?

comme heuristique, vous pourriez construire un graphe où chaque noeud représente un ensemble de carrés contigus, de même couleur, et chaque noeud est connecté à ceux qu'il touche. (Chaque bord étant pondéré par 1). Vous pouvez alors utiliser un algorithme de recherche de chemin pour calculer la "distance" du haut à gauche à tous les autres noeuds. Ensuite, en regardant les résultats de remplissage de crue en utilisant chacun des 5 autres couleurs, déterminez laquelle minimise la distance au noeud" le plus éloigné", puisque ce sera probablement votre étranglement.

ajoutez le résultat de ce calcul au nombre de remplissages effectués jusqu'à présent, et utilisez-le comme heuristique.

après avoir joué au jeu à quelques reprises, j'ai remarqué qu'une bonne stratégie est de toujours aller" en profondeur", d'Aller vers la couleur qui va le plus loin dans le territoire non-couvert.

un algorithme naïf "cupide" est de choisir l'étape suivante qui maximise le périmètre global de la région principale.

(un couple d'amis intelligents de moi ont pensé à ce sujet l'autre jour et ont décidé que l'optimium peut être NP-dur (par exemple, vous devez la force brute) - Je ne sais pas s'ils sont corrects (n'était pas là pour entendre le raisonnement et n'ont pas pensé à travers elle moi-même).)

notez que pour calculer les étapes, je présume l'union-trouver algorithme est votre ami, il rend le calcul 'un pas' très rapide (Voir par exemple ce billet de blog ).

A* est juste un ordre de priorité graphe de recherche. Chaque noeud est un État de jeu, vous classez les noeuds sur la base d'une certaine heuristique, et développez toujours le noeud le plus bas-prévu-final-cost. Tant que votre heuristique ne sous-estime pas les coûts, la première solution que vous trouvez est garantie d'être optimale.

après avoir joué aux jeux à quelques reprises, j'ai constaté que d'essayer de percer au coin opposé puis tous les coins tendaient à entraîner une victoire. Ainsi, une bonne estimation du coût de départ serait far) + un nombre suffisant de remplissages pour atteindre le coin opposé [note: Pas minimum, juste suffisant. Juste goulûment de remplissage vers le coin pour calculer l'heuristique].

j'ai travaillé là-dessus, et après avoir fait travailler mon solveur, j'ai regardé les approches des autres.

la Plupart des solveurs sont heuristique et ne garantissent pas l'optimalité. Heuristiques regarder le nombre de carrés et la répartition des couleurs laissées non choisi, ou la distance à la place "le plus loin". La combinaison d'une bonne heuristique avec DFS borné (ou BFS avec lookahead) donne des solutions qui sont assez rapides pour la norme 14x14 grille.

j'ai adopté une approche légèrement différente parce que j'étais intéressé à trouver la voie optimale prouvable, pas seulement une "bonne". J'ai observé que l'espace de recherche croît en fait beaucoup plus lentement que le facteur de ramification de l'arbre de recherche, parce qu'il y a beaucoup de positions dupliquées. (Avec une stratégie de priorité à la profondeur, il est donc important de maintenir un historique pour éviter un travail redondant.) Le facteur effectif de ramification semble plus proche de 3 que de 5.

la stratégie de recherche que j'ai prise est d'effectuer des BFS jusqu'à une profondeur" médiane " où le nombre d'États deviendrait infaisable, quelque part entre 11 et 13 coups fonctionne le mieux. Ensuite, j'examine chaque État à mi-profondeur et j'exécute un nouveau BFS en commençant par celui de la racine. Ces deux recherches peuvent être effectuées en éliminant les États trouvés dans les profondeurs précédentes, et cette dernière recherche peut être limitée par la profondeur de la solution la plus connue. (Un heuristique appliqué à l'ordre de la les sous-arbres examinés à la deuxième étape aideraient probablement certains aussi.)

l'autre technique d'élagage qui s'est avéré être la clé d'un solveur rapide est simplement de vérifier s'il reste plus de n couleurs, si vous êtes à N ou moins de pas de la meilleure solution actuelle.

une fois que nous savons quel est l'état de mi-chemin sur la voie d'une solution optimale, le programme peut effectuer DFS en utilisant cet état de mi-chemin comme un objectif (et la taille de toute voie qui sélectionne un place pas dans le milieu.) Ou, il pourrait être possible de construire les chemins dans la SECTION étapes, au prix de la mémoire supplémentaire.

mon solveur n'est pas ultra-rapide, mais il peut trouver une solution optimale garantie en quelques minutes. (Voir http://markgritter.livejournal.com/673948.html , ou le code à http://pastebin.com/ZcrS286b .)

la réponse de Smashery peut être légèrement modifiée. Pour l'estimation du nombre total de mouvements, s'il y a des couleurs " k "à la distance maximale, ajouter" k-1 " à l'estimation du nombre de mouvements.

plus généralement, pour chaque couleur, considérer la distance maximale à laquelle la couleur peut être nettoyée. Cela nous donne un dictionnaire cartographiant certaines distances maximales à un nombre non-zéro de couleurs qui peuvent être dégagées à cette distance. Somme valeur - 1 entre les touches et ajouter à la distance maximale pour obtenir un nombre de coups estimation.

il y a aussi certains cas gratuits. Si à tout moment nous pouvons effacer une couleur dans un mouvement, nous pouvons prendre ce mouvement sans considérer les autres mouvements.

Voici une idée pour mettre en œuvre le graphe pour soutenir heuristique de Smashery .

représente chaque groupe de carrés contigus de même couleur dans un ensemble disjoint et une liste de groupes de carrés adjacents. Un flood fill fusionne un ensemble à tous ses ensembles adjacents, et fusionne les listes de contiguïté. Cette structure graphique implicite vous permettra de trouver la distance entre le coin supérieur gauche et le noeud le plus éloigné.

je pense que vous pourriez considérer le nombre de carrés qui correspondent ou ne correspondent pas à la couleur actuelle. Ainsi, votre mesure heuristique de "distance" serait le nombre de carrés sur le Conseil qui ne sont-pas - la même couleur que votre couleur choisie, plutôt que le nombre de pas.

un heuristique naïf pourrait être d'utiliser le nombre de couleurs laissées (moins 1) - Ceci est admissible parce qu'il faudra au moins autant de clics pour enlever la planche.

Je n'en suis pas certain, mais je suis assez sûr que cela pourrait être résolu avec avidité. Vous essayez de réduire le nombre de champs de couleur à 1, donc réduire plus de champs de couleur plus tôt ne devrait pas être moins efficace que réduire moins plus tôt.

1) Définir une collection de groupes de couleur similaires existants.

2) pour chaque collection, compter le nombre de collections voisines par couleur. Le plus grand nombre de collections voisines avec une seule couleur est le poids de cette collection.

3) Prenez la collection avec le plus grand nombre de voisins avec une seule couleur, et le remplir à cette couleur. Fusionner les collections, et mettre à jour le tri pour toutes les collections affectées par la fusion (tous les nouveaux voisins de la collection fusionnée).

dans L'ensemble, je pense que cela devrait en fait calculer en O(N log n) temps, où n est le nombre de pixels et le log (n) vient seulement de maintenir la liste triée de poids.

Je ne suis pas sûr s'il doit y avoir un tie-breaker pour quand plusieurs champs ont le même poids cependant. Peut-être que le disjoncteur va à la couleur qui est commune à la plupart des groupes sur la carte.

quoi qu'il en soit, notez que le but du jeu est de réduire le nombre de champs de couleurs distincts et non de maximiser le périmètre, car différents schémas de couleurs peuvent occasionnellement faire un plus grand champ un choix sous-optimal. Considérons le domaine:

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

la couleur 1 a le périmètre le plus grand par n'importe quelle mesure, mais la couleur 2 est le choix optimal.

EDIT>

efface ça. L'exemple:

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

invalide mon propre algorithme. Mais je ne suis pas convaincu qu'il s'agisse d'un simple graphique transversal, puisque le changement à une couleur partagée par 2 voisins visite 2 noeuds, et non 1.

l'élimination de la couleur devrait probablement jouer un certain rôle dans l'heuristique.

1) Il n'est jamais correct pour remplir avec une couleur qui n'est pas déjà sur le graphique.

2) S'il est un champ de couleur avec une couleur unique, au moins un remplissage sera nécessaire pour cela. Il ne peut pas être livré avec d'autres remplissages. Je pense que cela signifie qu'il est prudent de le remplir le plus tôt possible.

3) l'algorithme cupide pour le comptage de terrain de voisin fait du sens pour une carte de 2 couleurs.