Rush Hour - la Résolution du jeu
L'Heure De Pointe
si vous n'êtes pas familier avec elle, le jeu se compose d'une collection de voitures de différentes tailles, soit horizontalement ou verticalement, sur un NxM grille qui a une seule sortie.
Chaque voiture peut se déplacer vers l'avant/vers l'arrière dans les directions de l'ensemble, aussi longtemps que l'autre voiture n'est pas bloquant. Vous pouvez jamais changer la direction d'une voiture.
Il y en a un spécial voiture, habituellement, c'est le rouge. C'est dans la même ligne que la sortie est dans, et l'objectif du jeu est de trouver une série de mouvements (un mouvement de déplacement de la voiture N pas en arrière ou en avant) qui permettra à la voiture rouge pour sortir du labyrinthe.
J'ai essayé de réfléchir à la façon de résoudre ce problème par le calcul, et je peux vraiment pas penser à une bonne solution.
Je suis venu avec quelques-uns:
- De retours en arrière. C'est assez simple, Récursivité et un peu plus de la récursivité jusqu'à ce que vous trouver la réponse. Cependant, chaque voiture peut être déplacé un peu de façons différentes, et dans chaque état de jeu un peu de voitures peuvent être déplacés, et l'arborescence du jeu va être ÉNORME.
- Une sorte de contrainte algorithme qui permettra de prendre en compte ce qui doit être déplacé, et de travailler de manière récursive en quelque sorte. C'est une idée très approximative, mais c'est une idée.
- Graphiques? Le modèle du jeu des états sous forme de graphique et d'appliquer une sorte de variation sur un algorithme de coloration, à résoudre des dépendances? Encore une fois, c'est une idée très approximative.
- Un ami a proposé des algorithmes génétiques. C'est possible, mais pas facilement. Je ne peux pas penser à une bonne façon de faire une fonction d'évaluation, et sans que nous l'ayons rien.
Donc la question est - Comment créer un programme qui prend une grille et le véhicule de la disposition, et les sorties d'une série d'étapes nécessaires pour obtenir le rouge voiture?
Sous-questions:
- Trouver certains solution.
- Trouver un optimale solution minimale (nombre de coups)
- L'évaluation de la qualité d'un état actuel est
Exemple: Comment pouvez-vous déplacer les voitures dans ce cadre, de sorte que la voiture rouge peut "sortir" le labyrinthe jusqu'à la sortie sur la droite?
(source: scienceblogs.com)
while(!win){selectRandomCar().moveRandomWay()};
- C'est
bogosolve
! - J'ai adoré ce jeu quand j'étais gamin. Mon algorithme: Pousser les voitures de PLUS de la frontière ou de jeter des voitures qui bloquent la sortie du conseil. Je gagne.
- Également un problème connexe est la preuve qu'généré de façon aléatoire une configuration de voitures est réellement solvables.
- N'est-ce pas ce genre de problème adapté pour être exprimé dans le Prologue? Je ne suis pas expert dans le présent, donc c'est juste une supposition.
- quel est le langage que l'API et est-il open source? 🙂
- Ah bon temps bon temps....
Vous devez vous connecter pour publier un commentaire.
Classique de l'Heure de pointe, ce problème est très souple avec un simple largeur de recherche. Le prétendu plus dur connu configuration initiale nécessite 93 se déplace à résoudre, avec un total de seulement 24132 accessible configurations. Même un naïvement mis en œuvre en largeur d'abord l'algorithme de recherche peut étudier l'ensemble de l'espace de recherche en moins de 1 seconde sur la même modeste de la machine.
Références
La Java solveur
Voici le code source complet de la largeur de la première recherche exhaustive solveur, écrit en C-style.
Il y a deux note digne de lignes dans le code source:
break;
lorsqu'une solution est trouvéecurrent = sb.toString();
dansslide
Vue d'ensemble de l'algorithme
L'algorithme est essentiellement une largeur de recherche, mis en œuvre avec une file d'attente comme il est typique. Un prédécesseur de la carte est maintenue afin que tout état peut être retracée à l'état initial. Une clé ne sera jamais reconfiguré, et que les inscriptions sont insérés dans la largeur-premier ordre de recherche de plus court chemin d'accès est garanti.
Un état est représenté comme un
NxM
-longueurString
. Chaquechar
représente une entité sur la carte, stockées en ligne ordre majeur.Les états voisins sont trouvés par le contrôle tous les 4 directions à partir d'un espace vide, à la recherche d'une voiture de type, glissant comme type de chambre peut accueillir.
Il y a beaucoup de travail inutile (par exemple le long de la "ruelles" sont analysés à plusieurs reprises), mais comme mentionné précédemment, bien que la version généralisée est PSPACE-complet, le classique de l'Heure de pointe variante est très traitable par la force brute.
Wikipedia références
nU = 3
, devrait êtrenU = 2
. Sera corrigé sur la prochaine révision, ainsi que tous les autres ajouts/corrections d'autres suggèrent.Voici ma réponse. Sa résout le grand maître de puzzle en moins de 6 secondes.
- Il une largeur de recherche (BFS). L'astuce est de trouver un schéma de la carte que vous avez vu avant dans les recherches antérieures et abandonner cette séquence. En raison de la BFS si vous avez vu que la mise en page avant de vous avez déjà eu il y a un moyen plus court donc laissez cette squence de continuer à essayer de le résoudre plutôt que ce serait plus un.
Il y a en fait un papier du MIT qui expressément référence à l'Heure de pointe (J'ai utilisé le terme de recherche "glisser le bloc puzzles")
Vous devriez recurse (votre "retour en arrière" de la solution). C'est probablement la seule façon de résoudre les énigmes de ce genre; la question est de savoir comment le faire vite.
Comme vous l'avez remarqué, l'espace de recherche sera grande, mais pas trop grand, si vous avez une taille raisonnable conseil d'administration. Par exemple, vous avez établi une grille de 6x6 avec 12 voitures sur elle. En supposant que chacun est un montant de 2 voiture, ce qui donne 5 places/p, donc au plus 5^12 = 244,140,625 postes potentiels. Cette place même dans un entier de 32 bits. Donc, une possibilité consiste à allouer un tableau énorme, un emplacement par le potentiel de position, et l'utilisation memoization pour vous assurer de ne pas répéter une position.
La prochaine chose à noter est que la plupart de ces "potentiel" les positions ne sont pas, en fait, possible (ils avaient impliquer les voitures qui se chevauchent). Donc, au lieu de cela, utiliser une table de hachage pour garder une trace de chaque position que vous avez visités. Cela aura une petite surcharge de la mémoire par l'entrée, mais il sera probablement plus efficace que la "panoplie" de la solution. Il sera, cependant, prendre un peu plus de temps pour chaque point d'accès.
Comme le MIT le papier dans @Daniel réponse dit, le problème est PSPACE-complet, ce qui signifie beaucoup d'astuces utilisées pour réduire la complexité des problèmes NP probablement ne peut pas être utilisé.
Cela dit, l'une des deux solutions ci-dessus à la répétition de position est un problème qui doit travailler pour de petits réseaux. Tout sera déterminé par la taille de la problème est, et la quantité de mémoire de votre ordinateur; mais l'exemple que vous avez affichée doit être pas mal du tout, même pour un pc ordinaire.
Juste de finir d'écrire mon de la mise en œuvre et expérimenter avec elle. Je suis d'accord avec polygenelubricants que l'espace d'état est vraiment petit pour le jeu classique (6x6 conseil d'administration). Cependant, j'ai essayé un savant de recherche, de mise en œuvre (Un* recherche). J'ai été curieux au sujet de la réduction de la exploré espace d'état par rapport à un simple BFS.
Algorithme A* peut être considérée comme une généralisation de la SECTION de recherche. La décision de chemin à explorer suivante est déterminée par un score qui combine à la fois la longueur du chemin (c'est à dire le nombre de coups) et une borne inférieure sur les mouvements restants comptent.
La façon dont j'ai choisi de calculer cette dernière, est d'obtenir la distance de la voiture rouge de la sortie, puis ajouter 1 pour chaque véhicule dans le chemin, il doit être déplacé au moins une fois afin de dégager la voie. Lorsque je remplace la limite inférieure de calcul avec une constante 0, je reçois régulièrement des BFS comportement.
Après l'inspection de quatre puzzles de cette liste, j'ai trouvé que* recherche explore en moyenne 16% moins d'états que régulièrement BFS.
Je pense que la récursivité est une mauvaise idée, sauf si vous gardez une trace de ce que vous avez déjà visité; vous pourriez vous retrouver recursing à l'infini par le déplacement d'une voiture d'avant en arrière.
Peut-être que c'est un bon début: Représenter et stocker chaque conseil d'etat comme un graphe non-dirigé. Ensuite, pour chaque déplacement, vérifiez contre passé pour vous en assurer, vous n'êtes pas tout simplement de frapper le même état nouveau.
Maintenant faire un autre graphe non orienté où les nœuds représentent les états et les arêtes représentent la capacité à passer d'un état à un autre par le déplacement d'une voiture. Explorer les états jusqu'à ce que l'un d'eux est une solution. Suivez ensuite les bords du début à trouver une trajectoire déplacer.
J'ai écrit un solveur de sudoku. Bien que les détails sont complètement différents, je pense que le problème est similaire. Pour une chose, essayer de faire des smart heuristiques dans un solveur de sudoku est beaucoup plus lent que la force brutale de la solution. En essayant à chaque mouvement, avec quelques heuristiques simples et pas de doublons est le chemin à parcourir. Il est un peu plus difficile à vérifier pour dupliquer le conseil des etats en heure de pointe, mais pas beaucoup.
Si vous regardez la carte de l'échantillonnage, il y a seulement 4 valide se déplace. À un moment donné, il y aura seulement quelques valide se déplace.
À chaque niveau de récursivité, copiez le conseil d'état et à essayer toutes les valides se déplacer sur la carte. Pour chaque case vide, déplacer chaque voiture sur place. Si le nouveau conseil d'administration de l'etat n'est pas dans la liste de l'historique, puis, de manière récursive un autre niveau. Par la liste de l'historique, je veux dire de donner à chaque niveau de récursion d'accès à chaque conseil qui a conduit à cet état, probablement dans une liste chaînée. L'utilisation de hachages rapidement jeter l'inégalité des états.
La clé c'est d'avoir un simple conseil d'état qui peuvent être facilement copiés et modifiés. Probablement un tableau avec un int par carré de dire quelle voiture couvre que le carré, le cas échéant. Ensuite vous avez juste besoin de faire une itération sur les places et figure juridique de mouvements. Un coup légal signifie cases vides entre les carrés et une voiture orientée vers elle.
Comme avec le sudoku, le pire option possible serait de l'algorithme génétique.