Comment minimiser le coût total de l'arborescence du plus court chemin

Question

J'ai un graphique acyclique orienté avec des arêtes positives. Il a une source unique et un ensemble de cibles (sommets les plus éloignés de la source). Je trouve les chemins les plus courts de la source à chaque cible. Certains de ces chemins se chevauchent. Ce que je veux, c'est un arbre de chemin le plus court qui minimise la somme totale des poids sur tous les bords.

Par exemple, considérons deux des cibles. Étant donné que tous les poids de bord sont égaux, s'ils partagent un seul chemin le plus court sur la plus grande partie de leur longueur, cela est préférable à deux chemins les plus courts sans chevauchement (moins d'arêtes dans l'arbre équivaut à un coût global inférieur).

Autre exemple: deux chemins ne se chevauchent pas sur une petite partie de leur longueur, avec un coût élevé pour les chemins non superposés, mais un faible coût pour le long chemin partagé (faible coût combiné). D'un autre côté, deux chemins ne se chevauchent pas sur la plus grande partie de leur longueur, avec des coûts faibles pour les chemins qui ne se chevauchent pas, mais un coût élevé pour le chemin partagé court (également, coût combiné faible). Il y a beaucoup de combinaisons. Je veux trouver des solutions avec le coût global le plus bas, compte tenu des chemins les plus courts de la source à la cible. En d'autres termes, je veux les arbres les plus courts et les plus courts.

Est-ce que cela sonne des cloches? Quelqu'un peut-il me signaler des algorithmes pertinents ou des applications analogues?

À la votre!

Answer 1

Si vous avez seulement des coûts positifs et que vous minimisez, utilisez simplement le Dijkstra's algorithm.

Answer 2

Ce problème (Steiner Tree) est NP-difficile et SNP-complet max. Il n'y a donc pas d'algorithmes polynomiaux ni de PTAS (approximations arbitrairement proches) sauf si P = NP. Le MST peut donner un poids arbitrairement pire qu'optimal, à moins que vous ne connaissiez une caractéristique particulière de votre graphique (par exemple, le graphique est planaire, ou du moins que les poids obéissent à l'inégalité du triangle). Par exemple, si vous avez K_1,000,000.001 avec tous les poids de tranche 1 et une seule cible, la solution optimale a un poids de 1 et le MST a un poids de 1.000.000.000.

Si vous supposez que tous les bords entre les cibles et tous les bords entre la source et chaque cible existent, vous pouvez toujours dépasser d'un facteur arbitraire. Considérez l'exemple ci-dessus, mais changez le poids marginal entre la cible et la source à 2 000 000 000 000 000 000 (vous êtes toujours éloigné d'un facteur d'un milliard de l'optimal).

Bien sûr, vous pouvez transformer le graphique pour «supprimer» les poids de bord ayant un temps O (E) élevé en traversant le graphique. Ceci plus un MST de l'ensemble des cibles et de la source donne un rapport d'approximation de 2.

De meilleurs rapports d'approximation existent. Robins & Zelikovsky ont un algorithme polynomial qui est jamais plus de 54,94% pire que optimale: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik & Chlebikova montrent que se rapprochant plus de 1,05% est NP-difficile: The Steiner tree problem on graphs: Inapproximability results (doi 10.1.1.4.1339 Si votre graphique est planaire, la situation est meilleure. Il y a un algorithme rapide qui donne une approximation arbitrairement proche due à Borradaile, Kenyon-Mathieu & Klein (basé sur Erickson, Monma, & Veinott): An O(nlogn) approximation scheme for Steiner tree in planar graphs (doi 10.1.1.133.4154)