Des étapes qui garantissent la sortie d'un labyrinthe

14

Étant donné un labyrinthe à 2 dimensions où vous pouvez donner 4 commandes "monter / descendre / droite / gauche". Connaître le labyrinthe mais pas où se trouve la personne, comment trouver la séquence minimale de commandes qui garantit la sortie du labyrinthe? Je recherche une seule séquence de commandes qui fonctionnera, peu importe où dans le labyrinthe vous commencez.

Supposons que si notre partenaire reçoit la commande "déplacer à droite" quand il y a un mur à droite, il restera simplement là où il est.

En d'autres termes, on nous donne un labyrinthe et nous devons choisir une séquence de commandes. Ensuite, notre partenaire sera placé quelque part dans le labyrinthe et suivra la séquence de commandes que nous avons choisie à l'avance. Nous voulons que cette séquence garantisse que notre partenaire s'échappera, peu importe où notre partenaire a été initialement placé. Notez que les commandes autorisées n'ont pas d'instructions conditionnelles, elles ne peuvent donc pas suivre une séquence différente selon votre partenaire.

Existe-t-il un algorithme polynomial pour construire une telle séquence, étant donné une description du labyrinthe?

Yuval Filmus mentionne qu'il s'agit d'un cas particulier d'un problème de synchronisation de mots , et pourrait être lié à des séquences de parcours universelles. J'ai également trouvé un article qui semble pertinent:

Le problème de résolution de labyrinthe simultané . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Malheureusement pour les graphiques généraux, cela semble être un problème non résolu, mais je me demande s'il pourrait y avoir un bon algorithme pour ce cas spécifique. J'ai proposé une approche candidate: étiquetez chaque poste avec le nombre d'étapes minimales nécessaires pour quitter, et gardez une trace de chaque agent dans le labyrinthe. Il pourrait être possible de faire une recherche A * de cette façon.

algorithms graphs graph-traversal seilgu
la source
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
Lézard discret
La stratégie d'Eppstein pour les automates monotones consiste à regrouper les états de sorte qu'au lieu de rechercher un chemin dans l'ensemble des états à pleine puissance, il cherche un chemin dans un graphe avec seulement plusieurs sommets polynomiaux. La généralisation la plus naturelle des intervalles en 2D à laquelle je peux penser est la coque convexe, mais malheureusement, il n'est pas clair que leur nombre augmente de façon polynomiale .
Peter Taylor

Réponses:

-1

Un algorithme qui fonctionne toujours est le suivant: posez la main gauche sur le mur et continuez jusqu'à la sortie. Je ne peux pas garantir le chemin le plus court (pour ce faire, vous devez connaître le labyrinthe, au moins partiellement, et être en mesure d'anticiper. Consultez leUNE∗(A-star) algorithme , il a été initialement conçu pour de telles tâches).

vonbrand
la source
Vous ne pouvez pas coder le suivi de mur comme une séquence fixe de directions cardinales. Les choix dépendent des murs autour de vous, ce qui est spécifiquement interdit par la question.
Curtis F
Si vous connaissez le chemin le plus court, vous pouvez le coder comme "aller à gauche, puis tout droit, puis ...". Si vous ne connaissez pas le chemin le plus court, vous ne pouvez pas donner de telles directions pour le chemin le plus court. Si vous ne connaissez pas de chemin, vous ne pouvez pas donner de directions pour sortir.
vonbrand