J'ai un graphique, avec x nœuds et bords y. Bords pondérés. Le point est de démarrer sur un nœud et d'arrêter sur un autre noeud qui est le dernier emplacement. Maintenant, voici le problème:
visualisez le problème. Les bords sont des routes et les poids des bords sont les limites de poids maximum pour les véhicules conduisant sur les routes. Nous aimerions conduire le plus grand camion possible de A à F. Je souhaite le poids maximum maximum maximum pour tous les chemins de A à F.
Puis-je utiliser une sorte d'algorithme de Dijkstra pour ce problème? Je ne sais pas comment exprimer ce problème sous la forme d'un algorithme que je puisse mettre en œuvre. Toute aide est très appréciée. Je suis confus parce que l'algorithme de Dijkstra ne voit que sur le chemin le plus court.
4 Réponses :
Voici une manière facile et efficace:
let Ceci donne un journal max soit le poids maximum de bord dans le graphique. Recherche binaire 0 <= k <= max tel que vous pouvez obtenir de a à f en utilisant uniquement les bords avec poids > = k . Vous pouvez utiliser un Première recherche d'une première recherche pour voir si cela est possible (ne prenez pas un bord si son poids est trop petit).
O ((x + y) log V) algorithme, où v est la plage de vos poids.
C'est faux. Vous ne pouvez exclure aucun des nœuds de graphique avant de traiter complètement le graphique, car il peut s'agir d'une partie de la solution, de sorte que le nœud exclu peut être sur un chemin avec un poids maximal.
@ARTUR MUSTAFIN - Il ne s'agit que de ce que vous avez édité le problème, il est correct pour ce que l'OP a affiché.
Si un camion est trop lourd pour traverser une certaine route, il n'est pas question de l'inclure dans la recherche, alors Ivlad a raison, je crois.
Ouais. Il est possible dans l'un des cas, bien sûr.
J'essayais de résoudre le problème UVA 10099 - le guide touristique . J'ai d'abord utilisé l'algorithme Floyd-Warshall qui a pu résoudre le problème dans O (x ^ 3) . Ensuite, j'ai résolu le problème en utilisant ceci avec une complexité de temps bien meilleure de O ((x + y) journal V) où v est la plage de poids dans le graphique.
Quel algorithme de type Dijkstra nécessite est la sous-structure optimale et une manière rapidement pour calculer la valeur objective d'une extension d'un bord d'un chemin avec une valeur d'objectif connue. Ici, une sous-structure optimale signifie que si vous avez un chemin optimal d'un sommet X à un Vertex Y différent, le sous-path de X au deuxième au dernier sommet est optimal.
(ivlad, je ne peux obtenir que O (x + y) avec randomisation.)
(Remarque: ce cadre couvre des algorithmes attribués aux personnes qui ne sont pas Dijkstra.)
Je ne peux pas mettre ce commentaire où il appartient: même si les flux et les chemins sont des objets combinatoires étroitement liés, je ne pense pas que les collègues ou je décrirais cela comme un "problème d'écoulement".
pas de dijkstra, aucun problème d'écoulement. C'est beaucoup plus facile: utilisez simplement votre recherche de graphique préférée (BFS ou DFS).
Au lieu de calculer et de suivre le coût associé à l'atteinte d'un certain nœud dans le graphique, il suffit de calculer la "taille" du plus grand camion qui est autorisé à utiliser ce chemin (minimum de poids de tous les bords du chemin). Lorsque plusieurs chemins de recherche se rencontrent dans un nœud, jetez le chemin qui a la «limite de poids du camion» inférieure.
Je suis d'accord, utilisez la matrice de conjonction (M) pour le graphique, réorganisez les nœuds de manière à ce que l'index de noeud de démarrage (A) de la colonne est de 0, et pour le dernier noeud (F) Index = L (M) -1.
Si je comprends correctement, vous souhaitez trouver le chemin entre certains nœuds qui possède le bord de goulot d'étranglement maximum. c'est-à-dire que vous voulez le chemin dont le plus petit bord est aussi important que possible. Si c'est ce que vous voulez résoudre, il existe une modification très simple de l'algorithme de Dijkstra qui peut être utilisée pour résoudre le problème.
L'idée derrière l'algorithme est d'exécuter l'algorithme de Dijkstra avec une torsion. Normalement, lors de l'exécution d'un algorithme de Dijkstra, vous gardez une trace de la longueur du chemin le plus court vers chaque noeud. Dans l'algorithme de Dijkstra modifié, vous stockez plutôt que pour chaque nœud, la valeur maximale possible d'un bord de poids minimal sur n'importe quel chemin qui atteint le nœud. En d'autres termes, normalement dans l'algorithme de Dijkstra, vous déterminez quel bord à développer en trouvant le bord qui optimise la quantité
D (S, U) + L (U, V)
où s est le nœud de démarrage, vous êtes un noeud que vous avez exploré jusqu'à présent, et (U, V) est un bord. Dans la modification de Dijkstra's, vous trouverez plutôt le bord minimisant
min (goulot d'étranglement (s, u), l (u, v))
C'est-à-dire que vous considérez le bord de goulot d'étranglement sur le chemin du nœud source à n'importe quel nœud que vous avez vu jusqu'à présent et considérez ce que le chemin d'étranglement serait formé si vous avez laissé ce nœud et allé quelque chose d'autre. C'est le meilleur chemin d'emble à goulot d'étranglement sur le nœud cible et vous pouvez répéter ce processus.
Cette variante de l'algorithme de Dijkstra fonctionne également dans O (M + N log N) à l'aide d'une bonne file d'attente prioritaire. Pour plus d'informations, envisagez de regarder dans Fait intéressant, il s'agit d'un problème bien connu qui est utilisé comme sous-programme dans de nombreux algorithmes. Par exemple, l'un des premiers algorithmes de temps polynomial pour résoudre le problème de débit maximal utilise cet algorithme en tant que sous-programme. Pour plus de détails sur la façon dont, consultez Ces notes de cours .
J'espère que cela vous aidera! Et si j'ai mal interprété votre question, merci de me le faire savoir afin que je puisse supprimer / mettre à jour cette réponse.
+1, c'est ce que je pensais quand j'ai dit qu'il y ait un O (x + y) algorithme - bien que c'était vraiment faux. Vous pouvez le faire O (x + y + v) où v est le poids lié en utilisant quelque chose de similaire à l'idée de tri de comptage: Garder MaxEget Listes - L [i] = Liste des nœuds x pour lesquels d [x] = i , où d [x] = bord minimum maximum de la source à x . Lorsque d [x] diminue, nous l'insérons dans une liste "plus petite", mais ne le supprimez pas de l'original. Au lieu de cela, lors de l'expansion d'un nœud x à partir d'une liste i , nous vérifions d'abord si d [x] = i , et si non, nous l'ignorons .
Cela ressemble plus à un problème de flux: en.wikipedia.org/wiki/flow_network
C'est un simple algorithme de recherche MIN Max sur un graphique non dirigé. Trouver le poids de la route maximale de tous les itinéraires disponibles à partir du noeud de démarrage pour mettre fin au nœud où pour tous les bords du chemin de route, chaque poids de bord n'est pas inférieur à la hauteur de la piste
@ARTUR MUSTAFIN - Votre édition a complètement changé le problème. S'il vous plaît ne modifiez pas de questions à ce que vous voulez qu'ils signent, la signification originale est parfaitement claire, même si vous ne le comprenez pas.
Ok, je ne comprends pas la phrase "Je veux le plus grand poids maximum autorisé pour tous les chemins de A à F", veuillez décrire ce que vous entendez dire en disant "poids pour tous les chemins", et s'il vous plaît être plus patient dans toutes les significations, Si vous comprenez ce que je veux dire.
@ARTUR MUSTAFIN - Cela signifie que vous souhaitez maximiser un
k tel qu'il existe un chemin d'accès à partir deA àf qui a tout son bord Poids> = k .