Algorithme de temps linéaire pour trouver

Définition. Étant donné un graphique$G=(V,E)$ et deux sommets $s$ et $t$, le $k$problè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 de$n$ 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ée$O(Kn(m+nlogn))$. De plus, l'autre article d'Epstein " Trouver les k chemins les plus courts " présente un algorithme qui trouve$k$ 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?

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 calcul$k$chemins 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:

La figure montre un digraphe dont la solution optimale (à partir du sommet source $s$ au sommet du but $t$) est le chemin $\pi_1 : \langle s, A, B, C, D, t\rangle$ 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 $\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$ et $\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$ les deux avec un coût égal à 7. Cependant, si les chemins doivent être simples, les deuxième et troisième chemins optimaux seraient $\pi_2 : \langle s, F, t\rangle$ et $\pi_3 : \langle s, G, t\rangle$ avec des coûts de 10 et 11, respectivement.

Étant donné un graphique $G(V, E)$ où $V$ est l'ensemble des sommets et $\langle u, v\rangle\in E, u, v\in V$ 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|\log |V|+k)$. Cependant, cet algorithme nécessite que le graphique soit donné explicitement.$K^*$allè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|\log |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 pour$O(k(|E|+|V|\log |V|))$temps. Alors que le pire cas asymptotique de Yen est destiné à énumérer$k$ 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 le$k$ 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 $k$chemins les plus courts. Intelligence artificielle, 175 (18), 2129-2154.

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

Hershberger, J., Maxel, M. et Suri, S. (2007). Trouver le$k$chemins 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 pour$k$chemins simples les plus courts. Networks, 12, 411-427.

Lawler, EL (1972). Une procédure de calcul de la$k$meilleures 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 le$k$chemins sans boucle les plus courts d'un réseau. Sciences de la gestion, 17, 712-716.

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