Graphique de l'algorithme de recherche

Question

Je suis à la recherche d'un algorithme graphique avec certaines propriétés inhabituelles.

Chaque arête dans le graphe est un "up" de bord ou un "bas" de bord.

Un chemin d'accès valide peut aller un nombre indéfini de "haut"s'suivi d'un nombre indéfini de "bas"'s, ou vice versa.Toutefois, il ne peut pas changer de direction plus d'une fois.

E. g., un chemin d'accès valide pourrait être Un "up" B "jusqu'à" C "vers le bas" E "" F un chemin d'accès non valide pourrait être Un "up" B "vers le bas" C "jusqu'à" D

Qu'est ce qu'un bon algorithme pour trouver le plus court chemin d'accès valide entre deux nœuds?Ce sujet de trouver tous de la même longueur des chemins les plus courts?

Answer 1

En supposant que vous n'avez pas l'heuristique, une variation de l'algorithme de dijkstra devrait suffire assez bien.Chaque fois que vous envisager un nouveau bord, stocker des informations à propos de ses "ancêtres".Ensuite, vérifier l'invariant (un seul changement de direction), et revenir en arrière si elle est violée.

Les ancêtres voici toutes les arêtes qui ont été parcourus pour accéder au noeud courant, le chemin le plus court.Un bon moyen de stocker de l'ancêtre de l'information serait que d'une paire de nombres.Si U est en place, et D est en bas, un particulier à bord des ancêtres pourraient être UUUDDDD, ce qui serait la paire 3, 4.Vous n'aurez pas besoin d'un troisième numéro, en raison de l'invariant.

Depuis, nous avons utilisé l'algorithme de dijkstra, trouver de multiples chemins les plus courts est déjà pris en charge.

Answer 2

Peut-être que vous pouvez transformer votre graphique dans un normal graphe orienté et ensuite utiliser des algorithmes existants.

Une façon de diviser le graphe en deux graphes, l'un avec tous les bords et avec tous les bas bords et avec des arêtes orientées entre tous les nœuds sur un graphique et le nœud correspondant sur le graphe en deux.

D'abord résoudre pour partir dans un graphique et se terminant dans le graphique deux et ensuite dans l'autre sens, puis vérifier la solution la plus courte.

Answer 3

On pourrait penser à votre niveau BFS devraient travailler ici.Chaque fois que vous ajoutez un nœud à la liste ouverte, vous pouvez l'envelopper dans une structure qui détient la direction qu'il utilise (en haut ou en bas) et un drapeau booléen indiquant si elle a changé de direction encore.Ceux-ci peuvent être utilisées pour déterminer les sortants de bords à partir de ce nœud sont valides.

Trouver tous les plus courts chemins de longueur égale, inclure le nombre d'arêtes parcourues jusqu'à présent dans votre structure.Lorsque vous trouvez d'abord votre chemin le plus court, faire une note de la longueur du chemin et d'arrêter d'ajouter des nœuds à la liste ouverte.Continuez à travers les nœuds restants sur la liste jusqu'à ce que vous avez vérifié tous les chemins actuels de la longueur, puis de s'arrêter.

Answer 4

Un* avec un spécialement conçu coût (G score) et heuristique (H score) la fonction peut s'en occuper.

Pour le coût, vous pouvez garder une trace du nombre de changements de direction dans le chemin d'accès et ajouter un coût infini sur le deuxième changement (ie.coupez la recherche de ces branches).

L'heuristique prend un peu plus de réflexion, en particulier lorsque vous souhaitez garder l'heuristique admissible (jamais une surestimation de la distance minimale de l'objectif) et monotone.(La seule façon de garantir Un* recherche d'une solution optimale.)

Peut-être il ya plus d'informations sur le domaine disponibles pour créer l'heuristique?(ie.les coordonnées x,y des nœuds dans le graphe?)

Bien sûr, en fonction de la taille du graphique que vous souhaitez résoudre, vous pouvez d'abord essayer le plus simple des algorithmes comme la largeur de la recherche ou de l'algorithme de Dijkstra:fondamentalement, chaque algorithme de recherche vont le faire, et pour tous vous aurez besoin d'une fonction de coût (ou similaire), de toute façon.

Answer 5

Si vous avez un standard graphique de la fonction recherche, dire Graph.shortest(from, to) dans une bibliothèque, vous pouvez faire une boucle et de minimiser, en C#/pseudo-code:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

Si vous avez besoin de se rappeler le chemin d'accès minimal/les chemins et il se trouve que le standard de la fonction retourne les données, vous pouvez également prononcer

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

où myMin doit comparer les deux [fst, nxt, C, AC, BD] les tuples et de laisser celui qui a une plus faible distance, ou les deux, et en supposant que reduce est une fonction intelligente.

Ce qui a une certaine surcharge de la mémoire si nos graphiques sont grandes et ne pas utiliser la mémoire à tout (ce qui est possible si elles sont générées dynamiquement), mais pas vraiment à toute vitesse les frais généraux, à mon humble avis.