Coût minimum fortement connecté digraph

Question

I ai un digramme qui est fortement lié (à savoir, il existe un chemin de i à j et j pour i pour chaque paire de noeuds (i, j) dans le graphique G). Je souhaite trouver un graphique fortement connecté sur ce graphique que la somme de tous bords est le moins.

Pour le dire autrement, je dois vous débarrasser des bords de telle sorte que, après les enlever, le graphique sera toujours fortement liée et de moindre coût pour la somme des arêtes.

Je pense qu'il est un problème difficile NP. Je suis à la recherche d'une solution optimale, sans approximation, pour un petit ensemble de données comme 20 noeuds.

Modifier

Une description plus générale: Etant donné un grap G (V, E) trouver un graphe G « (V, E ») de sorte que s'il existe un chemin de v1 à v2 dans G que il existe aussi un chemin entre v1 et v2 dans G « et somme de chaque ei dans E » est le moins possible. de sorte que son semblable à trouver un graphique équivalent minimum, seulement ici, nous voulons minimiser la somme des poids des arêtes plutôt que la somme des arêtes.

Edit:

Mon approche à ce jour: Je pensais à le résoudre en utilisant TSP avec plusieurs visites, mais ce n'est pas correct. Mon but est de couvrir chaque ville ici, mais en utilisant un chemin de coût minimum. Donc, il est plus comme le problème posé de couverture, je suppose, mais je ne sais pas exactement. Je suis obligé de couvrir chaque ville en utilisant des chemins dont le coût total est minimum, visiter donc des chemins déjà visités plusieurs fois ne pas ajouter au coût.

Answer 1

Votre problème est connu comme forte minimum couvrant sous (di) graphique (MSSS) ou, plus généralement, le coût minimum sous (di) couvrant graphique et NP-difficile en effet . Voir aussi un autre livre: page 501 et Page 480

Je commence par enlever toutes les arêtes qui ne satisfont pas l'inégalité triangulaire - vous pouvez supprimer un bord -> c si vous allez a -> b -> c est moins cher. Cela me rappelle TSP, mais ne sais pas si cela conduit nulle part.

Ma réponse précédente était d'utiliser le Chu Liu / Edmonds algorithme qui permet de résoudre problème Arborescence; comme Kazoom et ShreevatsaR ont souligné, cela ne suffit pas.

Answer 2

Je voudrais essayer cela dans une sorte de mode de programmation dynamique.

0- mettre le graphique dans une liste

1- Faites une liste de nouveaux sous-graphes de chaque graphique dans la liste précédente, où vous supprimez un bord différent pour chacun des nouveaux sous-graphes

2- supprimer les doublons de la nouvelle liste

3- supprimer tous les graphiques de la nouvelle liste qui ne sont pas fortement connectés

4- comparer le meilleur graphique de la nouvelle liste avec les meilleurs actuelle, si mieux, définir le nouveau courant meilleur

5- si la nouvelle liste est vide, la meilleure solution courante est le cas contraire, recurse / boucle / goto 1

Dans Lisp, il pourrait peut-être ressembler à ceci:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

Les définitions de strongly-connected, list-subgraphs-1, digraph-equal, best et better sont laissés comme un exercice pour le lecteur.

Answer 3

Ce problème est équivalent au problème décrit ici: http: // www .facebook.com / carrières / puzzles.php? puzzle_id = 1

Answer 4

Peu d'idées qui m'a aidé à résoudre le fameux casse-tête facebull:

étape de prétraitement:

1. Élagage: enlever toutes les arêtes a-b s'il y a moins cher ou avoir le même coût chemin, par exemple:. A-c-b

2. Graphique décomposition: vous pouvez résoudre si le graphe sous-problèmes a des points d'articulation

3. Fusion de sommets en un sommet virtuel s'il y a seulement un bord sortant.

étape de calcul:

1. Obtenir solution approximative à l'aide du TSP réalisé avec des visites répétées. Utilisez Floyd Warshall puis résoudre le problème Affectation O (N ^ 3) en utilisant la méthode hongroise. Si nous avons une fois le cycle - il est dirigé solution TSP, sinon - branche d'utilisation et TSP lié. Après cela, nous avons la valeur limite supérieure -. Cycle du coût minimum

2. solution exacte - branche et approche liée. Nous enlevons les vertex de cycle le plus court et essayer de construire le graphique fortement lié à moindre coût, que la limite supérieure.

C'est tous les gens. Si vous voulez tester vos solutions - essayer ici: http://codercharts.com/puzzle/caribbean-salesman

Answer 5

On dirait que vous voulez utiliser le Dijkstra algorithme

Answer 6

On dirait que ce que vous voulez est essentiellement une solution optimale pour-voyageur de commerce où il est permis pour les noeuds à visiter plus d'une fois.

Edit:

Hmm. Pourriez-vous résoudre ce essentiellement par itérer sur chaque nœud i et faire ensuite un arbre couvrant minimal de tous les bords pointant ce nœud i, filles fusionnées avec un autre arbre couvrant minimal de tous les bords pointant suite à partir de ce noeud?

Answer 7

A 2-approximation de la minimum fortement connecté sous-graphe est obtenue en prenant une union d'un minimum de ramification et minimale sur branchu, à la fois ancrée au sommet même (mais arbitraire).

Une hors branchement , également connu sous le nom arborescences , est un arbre dirigé enraciné à un seul sommet couvrant tous les sommets. Une ramification en est de même des bords arrière. Ceux-ci peuvent être trouvés par algorithme de Edmonds dans le temps O (VE) , et il y a speedups à O (E log (V)) (voir wiki ). Il y a même un implémentation open source .

La référence d'origine pour le résultat 2-approximation est par JaJa et Frederickson , mais le papier est pas librement accessible.

Il y a même une approximation par Adrian 3/2 Vetta (PDF) , mais plus compliqué que ce qui précède.