Je résous un problème d'optimisation de la recherche de graphiques. J'ai besoin de trouver les k meilleurs chemins les plus courts acycliques à travers un graphique pondéré dirigé.
Je sais qu'il existe un certain nombre d'algorithmes k-best exacts et approximatifs, mais la plupart des recherches récentes semblent être orientées vers des graphiques très grands et très peu connectés (par exemple, l'itinéraire routier et les directions), et mon graphique n'est ni l'un ni l'autre.
Distinguer les aspects de mon problème:
Le graphique se compose d'environ 160 sommets.
Le graphique est presque entièrement connecté (bidirectionnellement, donc ~ 160 ^ 2 ~ = 25k bords)
k sera assez petit (probablement moins de 10)
La longueur maximale du trajet sera probablement limitée et très petite également (par exemple 3 à 5 bords)
J'ai dit «acyclique» ci-dessus, mais juste pour réitérer - les solutions ne doivent pas inclure de cycles. Ce n'est pas un problème pour le meilleur chemin le plus court, mais cela devient un problème pour k-meilleur - par exemple, considérez un itinéraire routier - le 2ème chemin le plus court de A à B pourrait être le même que le meilleur, avec un rapide voyage autour d'un bloc quelque part. C'est peut-être mathématiquement optimal, mais pas une solution très utile. ;-)
Nous devrons peut-être repeser les bords à la volée pour chaque calcul. Un coût de périphérie se compose d'une somme pondérée de plusieurs facteurs, et les exigences finales (chaque fois que nous les obtenons) peuvent permettre à un utilisateur de spécifier sa propre hiérarchisation de ces facteurs de pondération, modifiant les pondérations de bord. Il s'agit d'un graphique relativement petit (nous devrions pouvoir le représenter dans quelques centaines de Ko), il est donc probablement raisonnable de cloner le graphique en mémoire, d'appliquer la repondération, puis d'exécuter la recherche sur le graphique cloné. Mais s'il existe une méthode plus efficace pour effectuer la recherche tout en calculant les poids à la volée, je suis intéressé.
Je regarde les algorithmes décrits dans Santos (algorithmes de chemin le plus court K), Eppstein 1997 (Trouver les k chemins les plus courts), et d'autres. L'algorithme de Yen est intéressant, principalement en raison de l' implémentation Java existante . Je n'ai pas peur de lire les documents de recherche, mais j'ai pensé qu'il valait la peine de jeter les détails de mon problème et de demander des conseils pour gagner du temps de lecture.
Et si vous avez des pointeurs vers des implémentations Java, c'est encore mieux.
la source
Réponses:
Pour répondre partiellement à ma propre question:
Depuis la publication de cette question, j'ai découvert que nous devons gérer les poids de bords négatifs ainsi que les positifs (la limitation aux chemins acycliques / simples / sans boucle signifie que la meilleure solution est définie, tandis que sans cette limitation, le chemin le plus court à travers un graphique avec négatif- les cycles de coûts ne sont pas définis).
L'algorithme de Yen et la plupart des autres que j'ai examinés dépendent d'une série de recherches parmi les meilleures; la plupart utilisent Dijkstra pour ces recherches intermédiaires. Dijkstra ne prend pas en charge les poids de bord négatifs, mais nous pouvons remplacer Bellman-Ford à sa place (au moins en yen; probablement à Lawler ou Eppstein également). J'ai développé une modification de Bellman-Ford avec une limitation de longueur de trajet (en bords) et une vérification de cycle explicite pendant la recherche (à la place de la détection de cycle post-recherche standard). La complexité de calcul est pire, mais toujours traitable pour mes besoins. Je vais modifier cette réponse et créer un lien vers un rapport technique si j'obtiens la permission de la publier.
la source
Je dirais que cette question peut être facilement googlé et est également un doublon:
Cela étant dit, j'ai déjà utilisé et implémenté Eppstein et le recommande. Je l'ai trouvé assez élégant. Si je me souviens bien, cela peut aussi être optimal, et l'article suivant l'explique très bien:
http://pdf.aminer.org/001/059/121/finding_the_k_shortest_paths.pdf
la source