Algorithme de temps linéaire pour trouver

8

Définition. Étant donné un graphiqueG=(V,E) et deux sommets s et t, le kproblème le plus court est de trouver le k chemins simples les plus courts entre s et t dans G.

Notez que la longueur de ces chemins n'est pas nécessairement égale, et les sommets s et t sont nécessairement k-lié. Je me demandais s'il y avait un temps linéaire (en termes den et m) algorithme pour ce problème.

J'ai regardé quelques articles dans la littérature, comme " A New Implementation Of Yen's Ranking Loopless Paths Algorithm " mais la complexité temporelle est vraiment élevéeO(Kn(m+nlogn)). De plus, l'autre article d'Epstein " Trouver les k chemins les plus courts " présente un algorithme qui trouvek les chemins les plus courts qui ne sont pas nécessairement des chemins simples avec un temps d'exécution O(n+m+k).

Existe-t-il un algorithme de temps linéaire pour le k-un problème de chemins les plus courts?

orezvani
la source
L'algorithme de @DW Eppstein trouve des chemins qui ne sont pas nécessairement simples. OP veut un algorithme similaire, éventuellement dans le même temps d'exécution, qui trouve lekchemins simples les plus courts. L'algorithme de classement de Yen est trop lent pour cela.
Yuval Filmus

Réponses:

7

Tout d'abord, la réponse qui s'applique ici a déjà été donnée par Raphaël dans les commentaires à la question: " Étant donné que nous ne savons même pas comment trouver un chemin le plus court simple en temps linéaire, j'en doute. " Dans ce qui suit, ainsi, je suppose que vous êtes intéressé à connaître les meilleurs algorithmes disponibles dans l'état actuel de la technique. Dans ce qui suit, je décris la meilleure limite du pire des cas (au meilleur de ma connaissance) mais aussi un algorithme qui pourrait fonctionner en temps linéaire dans certains cas spécifiques.

Mais avant de décrire les derniers développements de l'état de l'art, j'ai voulu souligner l'importance des voies simples dans ce problème spécifique. En fait, beaucoup de gens négligent l'importance de cette exigence et certains ne la comprennent même pas à première vue.

Lors du calcul du chemin le plus court d'un sommet de départ à un sommet cible, le chemin optimal est nécessairement simple , c'est-à-dire qu'il ne répète aucun sommet. Cependant, lors du calculkchemins optimaux, deuxième, troisième, ... les meilleurs chemins ne sont peut-être pas simples. Pour le prouver, je donne ici un exemple qui a été légèrement adapté de Hershberger, Maxel & Suri, 2007:

entrez la description de l'image ici

La figure montre un digraphe dont la solution optimale (à partir du sommet source s au sommet du but t) est le chemin π1:s,UNE,B,C,,t avec un coût égal à 5. S'il n'est pas nécessaire que les chemins soient simples, les deuxième et troisième chemins optimaux sont π2:s,UNE,B,C,,C,,t et π3:s,UNE,B,UNE,B,C,,t les deux avec un coût égal à 7. Cependant, si les chemins doivent être simples, les deuxième et troisième chemins optimaux seraient π2:s,F,t et π3:s,g,t avec des coûts de 10 et 11, respectivement.

Étant donné un graphique g(V,E)V est l'ensemble des sommets et u,vE,u,vV s'il y a une arête entre les sommets u et v, l'état actuel de la technique pour ce problème à ma connaissance est décrit ci-dessous:

La première amélioration significative pour résoudre le k le problème des chemins optimaux est l'algorithme d'Eppstein (Eppstein, 1998) qui O(|E|+|V|Journal|V|+k). Cependant, cet algorithme nécessite que le graphique soit donné explicitement.Kallège cette exigence tout en conservant une faible complexité (Aljazzar & Leue, 2011) et permet en outre l'application d'heuristiques admissibles. Dans les deux cas, les sorties calculées par ces algorithmes ne sont pas nécessairement des chemins simples.

Dans le cas où les chemins doivent être simples, les meilleurs résultats sont dus à Yen (Yen, 1971, 1972), généralisé plus tard par Lawler (Lawler, 1972), qui en utilisant des structures de données modernes peut être implémenté dans O(k|V|(|E|+|V|Journal|V|))pire moment. Dans le cas des graphiques non orientés, Katoh, Ibaraki et Mine (Katoh, Ibaraki & Mine, 1982) améliorent l'algorithme de Yen pourO(k(|E|+|V|Journal|V|))temps. Alors que le pire cas asymptotique de Yen est destiné à énumérerk les chemins les plus courts simples dans un graphe orienté restent invaincus (encore une fois, à ma connaissance!), plusieurs tentatives ont été faites pour le surpasser dans la pratique.

L'un de ces travaux est dû à John Hershberger et al., Qui a introduit un algorithme de chemins de remplacement qui est connu pour échouer à peine. En conséquence, leur algorithme fournit une accélération qui croît linéairement avec le nombre moyen d'arêtes dans lek les chemins les plus courts mais, dans certains cas (sous forme de graphiques aléatoires), cette accélération est minimisée.

J'espère que cela t'aides,

Bibliographie

Aljazzar, H. et Leue, S. (2011). K: Un algorithme de recherche heuristique pour trouver le kchemins les plus courts. Intelligence artificielle, 175 (18), 2129-2154.

Eppstein, D. (1998). Trouver lekchemins les plus courts. SIAM Journal on Computing, 28 (2), 652-673.

Hershberger, J., Maxel, M. et Suri, S. (2007). Trouver lekchemins simples les plus courts: un nouvel algorithme et son implémentation. ACM Transactions on Algorithms, 3 (4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). Un algorithme efficace pourkchemins simples les plus courts. Networks, 12, 411-427.

Lawler, EL (1972). Une procédure de calcul de lakmeilleures solutions aux problèmes d'optimisation discrets et son application au problème de chemin le plus court. Management Science, 18, 401-405.

Yen, JY (1971). Trouver lekchemins sans boucle les plus courts d'un réseau. Sciences de la gestion, 17, 712-716.

Yen, JY (1972). Un autre algorithme pour trouver lekchemins de réseau sans boucle les plus courts. Actes de la 41st Management Operations Research Society of America, 20.

Carlos Linares López
la source
Merci, cela fonctionne réellement dans O(n+m)dans les graphiques non pondérés. En fait, un article plus récent (mentionné dans la question) m'a fait penser que son temps de fonctionnement doit être meilleur que celui de Kotah; cela m'a donné une mauvaise impression.
orezvani
Heureux de vous entendre comme ça @kezzos
Carlos Linares López