Shortest Path sur un graphique non dirigé?

Question

Alors je pensais que cette question (quoique un peu de base) appartenait ici:

dire que j'ai un graphique de la taille 100 noeuds disposés selon un motif 10x10 (penser échiquier). Le graphique est plus guidées, et non pondérée. Se déplaçant à travers le graphe consiste à déplacer trois espaces avant et un espace à gauche ou à droite (analogue à la façon dont un chevalier d'échecs se déplace sur une carte).

Étant donné un nœud commençant fixe, comment peut-on trouver le plus court chemin vers un autre noeud sur la carte?

I imaginé qu'il y aurait seulement un bord entre des noeuds qui sont viables se déplace. Donc, compte tenu de ces informations, je voudrais trouver le chemin le plus court d'un noeud de départ à un nœud de fin.

Ma première pensée a été que chaque bord est pondéré avec le poids 1. Cependant, le graphique est plus guidées, donc Djikstras ne serait pas un ajustement idéal. Par conséquent, j'ai décidé de le faire en utilisant une forme modifiée d'une profondeur première recherche.

Cependant, je ne pouvais pas pour la vie de me visualiser comment obtenir le chemin le plus court en utilisant la recherche.

Une autre chose que j'ai essayé était de mettre le graphique sous forme d'arbre avec le noeud de départ comme la racine, puis en sélectionnant le moins profond (le plus bas numéro de ligne) résultat qui m'a donné le noeud final souhaité ... cela a fonctionné, mais était incroyablement inefficace et ne serait donc pas travailler pour un graphique plus grand.

Est-ce que quelqu'un a des idées qui pourraient me diriger dans la bonne direction sur celui-ci?

Merci beaucoup.

(j'ai essayé de mettre dans une visualisation du graphique, mais a été incapable de raison de mon faible réputation)

Answer 1

Si seulement les bords du graphique représentent valides se déplace entre certaines positions, en utilisant Dijkstra fonctionnerait très bien. Cependant, comme le graphique est non pondéré, il serait exagéré. Une simple largeur-première recherche donnera la réponse optimale.

Answer 2

Nicholas déjà fourni une réponse parfaite. Cependant, permettez-moi de répondre à votre première tentative d'utiliser la recherche en profondeur d'abord.

Tout d'abord, que ce soit Dijkstra (qui fonctionne très bien avec des noeuds non pondérés constatés par Nicholas Mancuso) ou en largeur de recherche encourent des déchets exponentielle de votre mémoire. Leur avantage, cependant, est qu'ils ne reprennent plus les nœuds alors qu'ils sont assurés de trouver des solutions optimales. Malheureusement, leur limitation est assez importante et ils ne devraient pas s'attendre à grande échelle raisonnable.

Si vous voulez résoudre les grandes instances de votre utilisation de problème itératives-Approfondissement de profondeur Première recherche (IDSF). Il suffit de publier une recherche à partir de votre état de démarrage première profondeur avec un ensemble à un seuil spécifique de profondeur maximale, $ d_ {max} $. Si vous ne trouvez pas la solution, puis augmenter la profondeur de la dernière itération par un $ k constante fixe $. Ainsi, dans le $ i $ itération -ème, une profondeur première recherche est lancée à d_ profondeur de $ {max} + i \ times k $ (avec la première itération étant numérotées de 0). Si $ d_ {max} = k = 1 $, alors vous êtes assuré de trouver la solution optimale en utilisant linéaire mémoire dans la profondeur de la solution.

Eh bien, vous pourriez penser que les noeuds ré-expansion est une idée plutôt mauvaise. Pas du tout! C'est ce qui garantit une consommation linéaire de mémoire pendant l'itération qui domine le temps global en cours d'exécution est juste le dernier afin qu'il puisse être prouvé que cet algorithme engage dans le une surcharge de $ \ frac {b} {b-1} $ avec $ b $ étant le facteur de ramification efficace, ce qui est clairement une valeur de pénalité très faible prise en compte face à des problèmes difficiles.

Cheers,