Chemin partiel le plus court dans un graphique

Question

J'ai un réseau défini par une matrice, où [i, j] élément de la matrice représente le coût d'obtention du nœud i au nœud j. S'il n'y a pas de chemin entre i et j alors [i, j] est Infini. Je remplis la matrice avec les valeurs négatives, de sorte que si la distance entre i et j est courte alors je mets très petite valeur dans [i, j], par exemple -50, si la distance est longue je mets plus grande valeur, par exemple -5.

Je me demande comment il est possible de trouver le plus court chemin partiel dans le réseau, le seul contraintes est le chemin d'accès doit aller dans l'ordre prédéfini, comme éléments se produisent dans la matrice i, i + 1, i + 2, ..

par exemple simplifié,

╔═══╦═══╦═════╦═══╦═══╦═════╗ 
║ ║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║ 
╠═══╬═══╬═════╬═══╬═══╬═════╣ 
║ 1 ║ 0 ║ -20 ║ ║ ║ -10 ║ 
║ 2 ║ ║ 0 ║ ║ ║  ║ 
║ 3 ║ ║  ║ 0 ║ ║  ║ 
║ 4 ║ ║  ║ ║ 0 ║ -50 ║ 
║ 5 ║ ║  ║ ║ ║  ║ 
╚═══╩═══╩═════╩═══╩═══╩═════╝ 

ici, la forme de chemin complet 1 à 5 est égal à -10, mais si nous prenons chemin 1 à 2, puis 4 à 5 nous obtenons meilleur score - 50, donc ici nous avons sauté 3 et c'est ok pour un chemin partiel. Donc le chemin partiel - est un chemin qui n'a pas à visiter tous les nœuds, il peut être juste un court segment 1 à 2, le plus court chemin partiel a le plus court parmi tous les chemins partiels. La contrainte sur la commande est très simple, nous commençons toujours à chercher le chemin depuis le nœud 1 et allons dans l'ordre croissant, donc pour tous les segments [i, j] [i1, j1] dans les chemins, j> i et i1 > = j.

Je me demande s'il y a un bon moyen de trouver le meilleur chemin partiel score dans le réseau, je pense que la recherche exhaustive est également une bonne solution, le nombre de nœuds est d'environ 15-20.

Answer 1

Vous avez essentiellement un Directed Acyclic Graph (DAG) ici, et vous êtes à la recherche d'un plus long chemin en elle, selon w(u,v) - où w(u,v) est le positif poids de chaque connexion (bord). S'il n'y a pas de limite entre u et v, nous indiquerons son poids avec l'infini négatif: w(u,v)=-infinity.

Le graphique est G=(V,E) où V est un mis contenant tous vos nœuds et E = { (u,v,w(u,v) | u<v} est l'ensemble des arêtes.

En général, Longest Path Problem est NP-complet. Heureusement, votre problème est un DAG, et il existe une solution efficace à ce problème. Tout d'abord topologically sort les nœuds, puis - du dernier au premier:

d(v) = max { d(u) + w(v,u) | for all edges (v,u) } 

Lorsque vous avez terminé, pour chaque noeud v d (v) désignera le plus long chemin qui commence par ce nœud, vous ne devez trouver la valeur maximale de ceux-ci pour obtenir le nœud désiré et la valeur maximale.

Vous pouvez reconstruire le chemin plus tard par:

v <- startNode //the node just found to be starting the desired path 
list <- [v] 
while (d(v) != 0): 
    for each edge (v,u): 
     if d(v) - w(v,u) == d(u): 
      list.append(u) 
      break 
return list