Je recherche un algorithme de chemin le plus court où l'agent (la chose qui doit se déplacer du début à la fin) n'a qu'une vue limitée sur le champ de marche. Disons que nous avons un labyrinthe avec un début et un objectif basé sur des tuiles. Quelque chose comme ça: L'agent peut alors ne pouvoir en voir qu'un dans chaque direction (haut, bas, gauche, droite) mais dispose d' une mémoire illimitée . En tant que mesure, je veux aussi peu d'étapes que possible pour atteindre l'objectif. Existe-t-il un algorithme pour cela?
Et si oui, existe-t-il un algorithme pour un problème plus général. Disons: un graphe, plusieurs buts et démarrages et une fonction qui renvoie les nœuds vus, et une mémoire limitée?
3 Réponses :
Après un certain temps, certaines idées et similitudes me sont venues à l'esprit.
Il est proche du problème qu'une Micromouse doit résoudre la plupart des utilisations Flood Fill
Flood-fill (node, target-color, replacement-color): 1. If target-color is equal to replacement-color, return. 2. ElseIf the color of node is not equal to target-color, return. 3. Else Set the color of node to replacement-color. 4. Perform Flood-fill (one step to the south of node, target-color, replacement-color). Perform Flood-fill (one step to the north of node, target-color, replacement-color). Perform Flood-fill (one step to the west of node, target-color, replacement-color). Perform Flood-fill (one step to the east of node, target-color, replacement-color). 5. Return.
Avec une visibilité limitée, vous ne pouvez pas vraiment vous attendre à trouver le chemin le plus court, car soit vous pouvez voir un chemin vers l'objectif, soit vous ne pouvez pas, à moins que vous ne soyez assez chanceux pour voir plusieurs chemins.
Cependant, vous pouvez utiliser une heuristique pour améliorer votre recherche. Par exemple, vous voudrez explorer les tuiles inexplorées, en priorisant celles qui sont autour de votre objectif, en commençant par celles qui sont les plus proches. Avec une visibilité de seulement 1, vous êtes fondamentalement aveugle, mais si vous aviez une visibilité légèrement plus élevée, vous pourriez donner la priorité à l'exploration autour de l'objectif jusqu'à ce que vous trouviez un chemin qui se connecte à quelque chose que vous avez déjà exploré.
Cela me rappelle le tracé de chemin bidirectionnel, une technique de rendu où vous tracez des chemins à la fois depuis la caméra et la lumière jusqu'à ce qu'ils se connectent. http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html
Certes, vous pouvez trouver le chemin le plus court, comme je l'ai montré. Mais vous ne pouvez pas trouver les étapes minimales, oui, du moins pas en général. Nous pourrions néanmoins utiliser la notation en.wikipedia.org/wiki/Big_O_notation O pour voir quel algorithme fonctionnait le mieux. De plus, je pense que ce que vous avez suggéré est essentiellement A-Star? Je pense que cela aide, mais cela ne résout pas le problème que vous devez calculer combien d'étapes sont nécessaires. Dernier à votre lien: j'ai peut-être manqué quelque chose, mais n'est-ce pas un algorithme bidirectionnel d'essaim? Je ne vois pas en quoi cela aide ici?
Vous ne pouvez pas savoir que vous avez le chemin le plus court à moins d'avoir une connaissance totale du labyrinthe. Pour les éléments bidirectionnels, vous recherchez essentiellement un chemin qui relie l'objectif à l'un des chemins que vous pouvez actuellement voir, afin que vous puissiez prioriser en commençant par la fin, ou là où vous êtes maintenant.
Vous vous trompez, je n'ai pas à voir l'ensemble uniquement les parties qui pourraient offrir un chemin plus court. En tant que tel, A * nécessite une heuristique appropriée, c'est-à-dire une distance hamilton pour un tel labyrinthe. Et le premier chemin trouvé sera aussi le chemin le plus court qui soit. Regardez de plus près ce en.wikipedia.org/wiki/A * _search_algorithm. Ce que vous ne pouvez pas faire facilement, c'est de trouver le chemin avec le moins d'étapes. C'est ce que je recherche de toute façon.
Je vois, vous avez raison de prouver le chemin le plus court si vous pouvez voir toutes les parties qui l'entourent.
vous ne pouvez pas vraiment vous attendre à trouver le chemin le plus court, une simple recherche de premier chemin en largeur peut trouver le chemin le plus court sans avoir une connaissance totale du labyrinthe. A * le fait plus efficacement.
@ c0der Vous manquez le point. Vous ne pouvez pas faire une première recherche large car c'est un agent ambulant et le but est de réduire le nombre de pas effectués.
Ce serait bien d'utiliser BFS pour trouver "une" solution mais, en général, il n'utilisera pas d'étapes minimales. Peut-être sauf que le laboratoire est un seul chemin, mais pourquoi devrions-nous nous préoccuper de ce cas? DFS a de meilleures chances de trouver l'objectif en étapes minimales car il peut être chanceux dans n'importe quel laboratoire d'étendre d'abord le chemin minimal.Dans ce cas, les étapes utilisées par l'agent seraient également minimes, mais il est très peu probable que cela se produise.
Une approche alternative très simple est:
walk to an undiscovered tile using a star if it is the goal stop if not repeat if there aren't any undiscovered tiles stop and fail