Résoudre tous les labyrinthes 4x4 simultanément avec le moins de mouvements
je suis tombé sur ce problème assez intéressant, où nous avons un labyrinthe 4x4 et un robot à l'intérieur pour essayer d'atteindre le but. Le truc, c'est qu'il faut trouver une séquence de commandes prédéfinies qui permettra toujours au robot d'atteindre le but.
disons que nous avons un labyrinthe comme ceci:
x . . .
. # # .
. # # .
. . . g
Ce labyrinthe peut être résolu avec, par exemple, les séquences de commande DDDRRR ou RRRDDD, où R= droite, L= gauche, U = haut et D = bas (duh).
aucune de ces séquences ne résoudrait cependant ce labyrinthe:
x . # .
. . . .
# . . .
. . . g
Le robot commence toujours en haut à gauche, le but est toujours en bas à droite, et le labyrinthe est toujours un 2D matrice de 4x4.
j'ai déjà implémenté un algorithme qui m'a permis d'obtenir une séquence gagnante de 78 commandes. Je sais à coup sûr qu'il existe au moins une solution pour 29 commandes (quelqu'un d'autre l'a fait).
Ce problème est en fait de quelques années et donc j'ai perdu l'algorithme que j'ai utilisé à l'époque, mais l'idée de base était d'exécuter une recherche à travers tous les labyrinthes que j'ai généré, et toujours choisir la route qui résulte dans les labyrinthes les plus résolus. Cela m'a permis d'obtenir une séquence d'une longueur légèrement supérieure à 78; j'ai réduit certaines commandes à la main que j'ai remarquées redondantes.
Oui, le forçage Brutal prendra des années comme d'habitude.
si ma mémoire est bonne, il y en a moins que 4000 labyrinthes possibles (labyrinthe possible étant qu'il existe un sentier entre le haut à gauche et le bas à droite).
OH! il suffit que le robot visite simplement le but au moins une fois pendant l'exécution des commandes. Qui est, il n'a pas à être assis sur le but, après la dernière commande.
ai-je capté l'intérêt de quelqu'un? Comment aborder ce problème pour une réponse plus efficace? Merci de songer à :)
Quelque Chose D'Amusant: Pastebin
C'est un morceau (très) hâtivement assemblé de Java. Il devrait compiler et exécuter :) Le programme joue un peu ~4000 labyrinthes en même temps. Le programme prend un input (w, A, s, D) Pour UP, LEFT, DOWN et RIGHT, puis simule le mouvement, montrant quelques statistiques. Ce que vous pouvez voir sur l'écran, vous devriez essayer, c'est le montant total des obstacles dans chaque labyrinthe dans chaque poste, et le montant total de poste de chaque labyrinthe. C'est difficile à expliquer :) Demandez moi si vous avez des questions.
encore... ne faites pas attention à l'horrible code. Il a été écrit en 20 minutes..ish
progrès
j'ai eu cette idée indirectement de l' cet utilisateur answer (qui a été supprimé par la suite, pour une raison ou une autre), et l'a ensuite modelé avec Canard Maussade dans une conversation. L'idée est de trouver une séquence qui résout le droite du labyrinthe. C'est une solution qui permet de résoudre au moins la moitié de tous les labyrinthes, et lorsque miroir et de courir à nouveau à partir du début résout les labyrinthes restants.
Illustration:
d'abord trouver une séquence, dont la première commande est correcte, qui résout, par exemple, ce labyrinthe:
0 1 0 0
0 1 0 0
0 0 0 0
0 1 0 0
une telle séquence est RDDRRRD. La contrepartie miroir de cette séquence est un tel que
R -> D
D -> R
L -> U
U -> L
ce qui signifie RDDRRRD -> DRRDDDR
est-ce que cette séquence en miroir résout le labyrinthe? Non, ça coince. Par conséquent, il n'est pas une séquence valide même pour ce un labyrinthe. Nous devons trouver une telle séquence qu'elle résout au moins la moitié de tous les labyrinthes, et c'est la contrepartie en miroir résout le reste lors de la course à nouveau dès le début.
après avoir simplement forcé toutes les permutations possibles de R, D et L, j'ai obtenu quelques possibles séquence.
Une telle séquence est RRDRRRDRLDRDR
le problème suivant est qu'après avoir exécuté cette séquence, les labyrinthes restants sont dans un chaos aléatoire. Nous devons obtenir la séquence la plus courte (optimale) possible qui ramènera tous les labyrinthes restants à la position de départ (0, 0). Cette partie j'ai fait simplement à la main (pour l'instant). Ma réponse à cette question n'est nullement optimale, mais elle ramène tous les labyrinthes au début.
Cette séquence LDLUULURUUULULL
après cela, nous exécutons simplement la séquence miroir,DDRDDDRDURDRD, et nous avons résolu tous les labyrinthes.
Cette séquence dans son intégralité:
RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD - 41 déplace
Tout cela est prometteur, et l'attribution d'étape, c'est toujours 12 se déplace loin le meilleur avéré la solution. Toute idée est la bienvenue! Aussi, merci à tous ceux qui m'ont aidé jusqu'à présent :)
La séquence rétrécit
j'ai été jusqu'à présent incapable d'obtenir une meilleure réponse programmatique qu'une longue séquence de 58 mouvements. Cependant, avec la méthode décrite ci-dessus et en rectifiant les caractères à la main, j'ai pu réduire la séquence à seulement 33 caractères. Cette séquence est la suivante:
RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR - 33 se déplace
alors que la séquence est maintenant très proche de l'objectif 29, je suis toujours à la recherche d'une solution programmée du même calibre. Il n'y a pas de logique que j'ai utilisée pour enlever les caractères de la séquence - j'ai simplement enlevé un caractère et vérifié s'il résout tous les labyrinthes, rincer et répéter.
6 réponses
en utilisant un algorithme meta A* et C#, j'ai trouvé les 32 et 31 séquences de caractères suivantes (jusqu'à présent):
RRDRRDRLDRDLDLULLLDDRDDRDRURRDRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 characters)
RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 characters)
I fourche Olavi de ideone avec la séquence de 31 caractères pour s'assurer que je n'ai pas fait d'erreurs.
en ce qui concerne le nombre de labyrinthes, j'obtiens 3828 labyrinthes valides en utilisant un algorithme de remplissage par inondation.
projet C# code source et compilé version binaire (bin\release dossier)Google Drive.
vous pouvez entrer une chaîne de démarrage pour la recherche A* IL et une longueur de recherche maximale.
Il y a eu quelques optimisations de vitesse au code, mais il y a encore de la place pour plus. Par exemple, pour chaque extension, il crée 4 instances de Candidate classe, créant de nouveaux labyrinthes qui exécutent chaque mouvement de l'ancien candidat, suivi par les 4 directions différentes (Gauche, Droite, Haut, Bas). Avec un Candidate.Clone() méthode, la performance pourrait être améliorée beaucoup, le profileur montre le hotspot actuel exactement là. De plus, il n'y a pas de multithreading jusqu'à présent et le programme utilise de plus en plus de mémoire pour la liste visitée (environ 2 Go après 10 minutes sur mon PC). Notez qu'exécuter le programme à l'intérieur de L'IDE le ralentit un peu même en mode release, donc mieux vaut le lancer à l'extérieur.
La base méta-algorithme qui conduisent à les séquences ci-dessus est:
a* rechercher une chaîne connue de longueur N avec longueur maximale M, en enlevant de plus en plus de caractères de l'extrémité, par ex.
A* recherche de RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD (32 caractères), M = 33
a* Recherche de RRDRRDRLDRDLDLDLLLDDRDDRDRURRRD (31 caractères), M = 33
a* Recherche de RRDRRDRLDRDLDLULLLDDRDRDRURRR (30 caractères), M = 33
a* Recherche de RRDRRDRLDRDLDLDLLLDDRDRDRURR (29 caractères), M = 33
...
une fois qu'une chaîne plus courte que N est trouvée, utilisez ceci comme nouvelle longueur maximale pour la recherche A* pour la rendre plus rapide et prendre moins de temps mémoire.
les combinaisons réelles que j'ai essayées peuvent être vues dans le code source, voir l'extrait de code ci-dessous. Les timings sont d'une ancienne version non optimisée et la version actuelle devrait être environ 6 fois plus rapide.
//// 33 char solution
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR", 33); // 33 chars, 00:00:00.0032911 Finished, 1 solution, best 33, visitedList length 0
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD", 33); // 32 chars, 00:00:00.0308543 Finished, 1 solution, best 33, visitedList length 3
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRD", 33); // 31 chars, 00:00:00.0871429 Finished, 2 solutions, best 33, visitedList length 14
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRR", 33); // 30 chars, 00:00:00.2536057 Finished, 2 solutions, best 33, visitedList length 49
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 33); // 29 chars, 00:00:01.0540762 Finished, 8 solutions, best 32, visitedList length 205
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 33); // 28 chars, 00:00:03.8993877 Finished, 7 solutions, best 32, visitedList length 771
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 33); // 27 chars, 00:00:10.4225150 Finished, 7 solutions, best 32, visitedList length 2069
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 33); // 26 chars, 00:00:24.2552908 Finished, 7 solutions, best 32 visitedList length 4484
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 33); // 25 chars, 00:01:44.3295165 Finished, 14 solutions, best 32, visitedList length 16600
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 33); // 24 chars, 00:16:18.6666045 Finished, 14 solutions, best 32, visitedList length 77106
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 32); // 29 chars, 00:00:00.3134699 Finished, 1 solution, best 32, visitedList length 66
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 32); // 28 chars, 00:00:01.1053798 Finished, 1 solution, best 32, visitedList length 238
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 32); // 27 chars, 00:00:03.5172143 Finished, 1 solution, best 32, visitedList length 730
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 32); // 26 chars, 00:00:07.1336796 Finished, 1 solution, best 32, visitedList length 1413
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 32); // 25 chars, 00:00:26.4906874 Finished, 2 solutions, best 32, visitedList length 5084
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 32); // 24 chars, 00:02:52.8134463 Finished, 2 solutions, best 32, visitedList length 24623
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 32); // 23 chars, cancelled after 6 seconds, finds RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 chars)
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 31); // 23 chars, 00:01:58.4861802 Finished, 1 solution, best 31, visitedList length 18835
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRD", 30); // 22 chars, 00:00:34.6602434 Finished, 0 solution, best distance 44, visitedList length 21084
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDR", 30); // 21 chars, 00:04:32.2439241 Finished, 0 solution, best distance 44, visitedList length 78500
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDD", 30); // 20 chars, cancelled after 10 minutes, found no solution, best distance 44
//var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLD", 30); // 19 chars, cancelled after 10 minutes, found no solution, best distance 44
//var aStarSearch = new AStarSearch("R", 29); // Complete search, would take waaay too long and consume much memory
Il semble que vous pourriez utiliser Un* recherche ici, en prenant comme heuristique le maximum heuristique de tous les labyrinthes. Cela donne une approximation prudente de la distance par rapport à la solution et donnerait probablement une première approche raisonnable.
puisque tous les labyrinthes sont petits, vous pouvez construire un heuristique parfait pour chacun en exécutant BFS à l'envers à partir de la fin de chaque labyrinthe pour précalculer la distance de chaque point au but de chaque labyrinthe. Si vous l'avez caché dans les tables de recherche, vous pouvez avoir un heuristique per-maze qui vous a parfaitement dit le nombre minimum de mouvements restants.
Je n'ai pas vraiment essayé cela, donc cela reste à valider expérimentalement, mais je pense que ce serait un excellent point de départ pour une solution.
EDIT je viens de lire la note qui dit que chaque robot doit visiter le but au moins une fois et pas nécessairement finir sur le but. Dans ce cas, modifier l'heuristique pour être la distance maximale de tout robot qui n'a pas encore atteint le objectif l'objectif.
Espérons que cette aide!
quelques idées:
- aucun des substrats RLR, LRL, UDU ou DUD ne peut apparaître dans une solution optimale, car tous les labyrinthe ils quittent le robot soit dans la même position (si le premier mouvement est bloqué par un mur) soit un pas dans la direction du premier mouvement (sinon), ce qui dans chaque cas est le même que le résultat de l'exécution du premier mouvement dans la séquence. Il en va de même pour RRLLRR, LLRLLL, etc. (et probablement pour tous des modèles plus longs, bien que je ne l'ai pas vérifié, et ils produisent des rendements décroissants en termes d'élagage de la recherche). [EDIT: Ce n'est pas tout à fait le droit-il ne s'applique que si pas de robot qui n'a pas encore atteint
gportéegsur le second des trois coups. Délicat!] - dans n'importe quelle solution valide, si tous les Ds et Rs sont échangés, et tous les Ls et nous sont échangés, nous obtenons une autre solution valide, puisque cette solution "inversée" résoudra tous les labyrinthes qui ont été "renversé" autour de la diagonale principale, qui est simplement l'ensemble de tous les labyrinthes. Le résultat est que nous n'avons besoin que de considérer des solutions dans lesquelles le premier pas est, disons, R.
- une façon de procéder avec une* recherche (ou branche et liée, ou énumération complète) est d'enregistrer, à chaque noeud dans l'arbre de recherche, l'état du robot dans tous ~4000 labels valides. Mais nous pouvons économiser beaucoup de temps et d'espace par combinant les états de tous les labyrinthes qui n'auraient pas pu être distingués par nos se déplace jusqu'à présent. Nous pouvons le faire en enregistrant un troisième état cellulaire "inconnu",
*. Chaque fois que nous essayons de faire un déménagement dans un*cellule, cet état se divise en 2 sous-états: l'état dans lequel elle devient une cellule vide (et notre mouvement se termine avec succès), et l'état dans lequel elle devient un mur (et nous restons dans la même position). Si révéler cette cellule pour être un mur signifie qu'il n'est plus possible d'atteindre la cellule de but, alors ce sous-état n'est pas générer.
ainsi, par exemple, après avoir essayé le tout premier mouvement (R), l'information complète de l'état dans le noeud de l'arbre de recherche se compose des deux labyrinthes partielles suivantes:
x # * * . x * *
* * * * * * * *
* * * * * * * *
* * * g * * * g
Si nous nous efforçons D un déménagement, nous avons le vent avec:
. # * * . x * * . . * *
x * * * * # * * * x * *
* * * * * * * * * * * *
* * * g * * * g * * * g
Notez que le passage de l'état sur la gauche avait réussir, parce que sinon le robot aurait été enfermé dans la cellule (1, 1).
pour un autre exemple, le suivant le labyrinthe partiel représente 32 labyrinthes complets différents (correspondant aux 32 différentes façons que le * cellules pourraient être résolues), dont chacune a la même solution optimale:
x # * *
. # * *
. # # *
. . . g
alors qu'il est encore possible d'utiliser la heuristique BFS de templatetypedef pour A*, le fait que chaque cellule puisse maintenant être dans l'un des 3 états augmente le nombre total de distances prédéfinies à 16*3^14 = 76527504, ce qui est encore gérable. Nous avons besoin de représenter des ensembles d'éléments qui peuvent supposer 3 états comme des sommes de pouvoirs de 3 pour former des index dans des tables de recherche, et ce n'est pas aussi rapide ou pratique que de travailler avec des articles à 2 états, mais ce n'est pas trop hard: la seule opération coûteuse est la division par 3, qui peut être faite en multipliant par 0x555556 et en gardant les 32 premiers bits du résultat 64 bits.
j'ai rapidement lancé une implémentation ensemble (voir ici si vous êtes intéressé, c'est un peu un gâchis). Je ne suis pas sûr que ce soit une approche similaire à ce que @templatetypedef a décrit. En gros, je fais le code suivant:
- générer tous les labyrinthes et calculer la distance de chaque cellule à la cellule finale (filtrer tous les labyrinthes qui ont des zones inaccessibles, parce que ceux-ci sont équivalents aux labyrinthes qui ont des murs dans ces endroits).
- commencez à marcher à travers tous les labyrinthes simultanément. Le score actuel est la distance totale jusqu'à la cellule finale sur tous les labyrinthes qui n'ont pas encore atteint la cellule finale.
- Calculer le score pour chacune des quatre directions possibles. Se déplacer avec gourmandise vers la direction qui a le meilleur (le plus bas) score.
cette approche converge, mais elle prend 103 pas. J'ai alors essayé d'avoir un regard plus grand-à l'avance, donc au lieu de choisir avidement la meilleure étape suivante, avidement choisir la meilleure séquence de k les prochaines étapes.
j'ai couru cette approche jusqu'à k = 10, avec les résultats suivants:
k | length | sequence
--------------------
1 | 103 | RDRDRDRDRLDDRRDRURRDLLDDRURURRDDLLLDDRRDRURRUURRRDDDULLLDDDRRRDLLDDRRLURRLLUDRRDDRRRLUUURRRDDDULLDDRDRR
2 | 86 | RDRDRDRDRLDDRRDRURRDLLDDRUURRDRDLLLDDRDRURRUURRDRDDULLLDDDRRDRRLULLDDRDRURRLUURURRDDRD
3 | 79 | RDRDRDRDRLDDRRDRURURDRDLLDDLDRDRRDRURURURRDDDULLLDDRDRRRLULLDDRDRRLURURDRURRDDD
4 | 70 | RDRDRDRDRLDDRRDRUURRDLLDLDDRDRURUURRDRDDLULLLDDRDRRRDLLDDRRRLUURURRDDD
5 | 73 | RDRDRDRDRLLDDRRDRURRURRDDDULLLDDRDRDRUURURRDDRDLULLDDRDRRLUURURRDLLLDDRRR
6 | 70 | RDRDRDRLDRDRDUURRDLLLDDRDRDRURUURRDDULLLDDRDRRRLUUURRRDRLLDDULLDDRDRRR
7 | 64 | RDRDRDRLDDRRDRLLDDRURUURDRDDULLLDDRDRRDRLURURURRDLDULLDDLLDRDRRR
8 | 67 | RDRDRDRDLLDDRRDRURUURRDDULLLDDRDDRUURRDRURRDLLLDULLDDRDRRLUURURRDDD
9 | 64 | RDRDRDRDRLLDDRURRDDRUUURRDDULLLDDRDRDRRLUUURRRDLDULLDDLLDRDRURRD
10 | 58 | RDRDRDRDRLLLDDRURDRDRUUURRDDDLULLLDRDDRRURRDRRLDDUURURRDDD
bien sûr, cette approche devient irréalisable pour de grandes k. Comme L'OP affirme que le problème peut être résolu avec seulement 29 mouvements, cette approche avide ne semble pas la meilleure façon de procéder...
j'ai pris la longue corde 41 du poteau original et j'ai essayé de la minimiser.
J'ai trouvé que 4 caractères peuvent être supprimés. Pas beaucoup, mais je pense qu'il vaut la peine de remarquer.
Donc, à partir de ce RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD je suis arrivé à ce RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD. Il dépasse chaque labyrinthe généré par la méthode de @Vincent.
j'ai aussi vérifié d'autres résultats de ce thread, mais il n'y avait pas de différence significative.
j'ai utilisé un peu du code de @Vincent pour générer des labyrinthes.
Voici un lien vers le code et exemple. http://ideone.com/9OFr5E
s'il vous plaît faites-moi savoir si j'ai fait une erreur quelque part.
ce n'est pas exactement une réponse, mais d'autres pourraient la trouver utile pour trouver une réponse.
semble que la meilleure approche globale est de se déplacer en diagonale. Cependant, j'ai rencontré un certain nombre de situations délicates, que j'énumère ci-dessous, qui semblent faire trébucher les approches que je propose à la main.
1 0 0 0 1 0 0 0 1 0 0 0 1 0 # Z 1 0 # Z
0 # X # 0 # # X 0 # # X # 0 X 0 # 0 # Z
0 Z # Z 0 Z Z # 0 0 0 # Z Z # 0 Z 0 X 0
0 0 0 1 0 0 0 1 X # 0 1 Z Z # 1 Z Z # 1
Où: 1 est le début/la fin. 0 est une place vide, # c'est un mur, Z est soit un mur ou un vide et X est le gênants spots, de soit coincé ou de la difficulté à arriver à eux.
une approche qui peut résoudre les labyrinthes ci-dessus avec le plus petit nombre de commandes devrait être assez proche de résoudre n'importe quel labyrinthe.