J'ai un digraphe qui est fortement connecté (c'est-à-dire un chemin de i à J et J à i pour chaque paire de nœuds (i, j) dans le graphique g). Je souhaite trouver un graphique fortement connecté de ce graphique de sorte que la somme de tous les bords est le moins.
Pour le mettre différemment, je dois me débarrasser des bords de manière à ce que, après leur retrait, le graphique sera toujours fortement connecté et le moins coûté pour la somme des bords.
Je pense que c'est un problème dur np. Je recherche une solution optimale, pas d'approximation, pour un petit ensemble de données comme 20 nœuds.
modifier
Description plus générale: Compte tenu d'une grappine G (V, e) Rechercher un graphique G '(V, E') de telle sorte que s'il existe un chemin de V1 à V2 en G que là-bas n'existe également un chemin entre V1 et V2 en G 'et la somme de chaque EI dans E' est le moins possible. Donc, sa valeur similaire à la recherche d'un graphe équivalent minimum, nous ne voulons qu'à minimiser la somme des poids de bord plutôt que la somme des bords.
éditer:
Mon approche jusqu'à présent:
J'ai pensé à la résoudre à l'aide de TSP avec plusieurs visites, mais ce n'est pas correct. Mon objectif ici est de couvrir chaque ville mais d'utiliser un chemin de coût minimum. Donc, c'est plus comme le problème de la couverture, je suppose, mais je ne suis pas vraiment sûr. Je suis obligé de couvrir chaque ville à l'aide de chemins dont le coût total est minimum, alors visitant les chemins déjà visités à plusieurs reprises n'ajoute pas au coût.
7 Réponses :
semble être ce que vous voulez essentiellement, c'est une solution optimale pour voyager-vendeur où elle est autorisée pour que les nœuds soient visités plus d'une fois.
EDIT:
hmm. Pourriez-vous résoudre cela en itérant essentiellement sur chaque noeud I, puis effectuant une arborescence minimale de toutes les bords pointant
En fait, j'ai résolu ce problème TSPM, mais cela ne fonctionnerait pas, dans mon cas, je devrais être autorisé à revenir sur le nœud ainsi que les bords à plusieurs reprises, je modifierai la question pour plus de description
sonne comme si vous souhaitez utiliser le Algorithme Dijkstra
Dijkstra ne s'applique pas ici ... du moins pas de manière évidente.
Eh bien, vous pouvez utiliser Dijkstra pour résoudre le TSP. C'est donc est une solution possible. C'est juste une question de définition de l'espace de recherche des solutions partielles, puis de la chercher dans l'ordre au moins coûteux. Bien sûr que cela ne signifie pas que c'est une bonne solution dans ce cas.
Je voudrais essayer cela dans une stratégie de programmation dynamique.
0- Placez le graphique dans une liste
1- Faites une liste de nouveaux sous-gradins de chaque graphique dans la liste précédente, où Vous retirez un bord différent pour chacun des nouveaux sous-graphes
2- Supprimer des duplicats de la nouvelle liste
3- Supprimer tous les graphiques de la nouvelle liste qui ne sont pas fortement connectées
4- Comparez le meilleur graphe de la nouvelle liste avec le meilleur actuel, si mieux, définissez le meilleur meilleur actuel
5- Si la nouvelle liste est vide, le meilleur est la solution, sinon la solution , recueil / boucle / goto 1
dans lisp, il pourrait peut-être ressembler à ceci: Les définitions de fortement connectés , list-Subgraphs-1 , digraph--égal , meilleur , et meilleur est laissé comme un exercice pour le lecteur.
Votre problème est connu sous le nom Je commencerais à supprimer tous les bords qui ne répondent pas à l'inégalité du triangle - vous pouvez éliminer le bord A -> C si aller a -> B -> C est moins cher. Cela me rappelle le TSP, mais je ne sais pas si cela mène n'importe où.
Ma réponse précédente consistait à utiliser le algorithme Chu-Liu / Edmonds qui résolvent arborescence problème; Comme Kazoom et Shreevatsar ont souligné, cela n'aide pas.
La MST pour l'arborescence dirigée ne résout pas vraiment le problème. L'arbre dirigé MST trouve le chemin le plus court que de la racine à un autre nœud. Dans mon cas, j'ai besoin de trouver un graphique qui a des chemins d'un nœud à tous les autres nœuds, peut ne pas être le moins, mais la somme globale des bords d'un graphique doit être minimum.
"L'arbre dirigé MST trouve le chemin le plus court que de la racine à un autre nœud" - c'est ce que Dijkstra fait? Selon une autre référence que j'ai liée, la somme globale est minimisée et le graphique résultant est fortement connecté. Pourriez-vous clairement indiquer ce qui ne va pas? (Ce n'est pas une utilisation littérale de l'algorithme MST non dirigée vers un graphique dirigé)
@SDCVVC: Le graphique résultant donné par le problème minimum-arborescence est une arborescence, mais pas fortement connecté. Il a des chemins de la racine à tous les autres nœuds, mais pas entre toutes les paires de nœuds. Par exemple, il n'a pas de bord entrant dans la racine ou sortant des feuilles.
Pour obtenir un facteur de 2 sur Optimal, choisissez un nœud arbitraire et calculez une arborescence minimale de survol et dans l'arbre pour ce nœud.
Ce problème est équivalent au problème décrit ici: http: // www .Facebook.com / Carrières / Puzzles.php? Puzzle_id = 1
Peu d'idées qui m'ont aidé à résoudre le célèbre casse-tête Facebull:
Étape de prétraitement:
Écran: retirez tous les bords A-B S'il y a moins cher ou ayant le même chemin le chemin , par exemple: A-C-B.
Decomposition graphique: Vous pouvez résoudre les sous-programmes si le graphique a des points d'articulation
fusion de sommetex dans un sommet virtuel s'il n'y a qu'un seul bord sortant.
Étape de calcul:
Obtenez une solution approximative à l'aide de la TSP dirigée avec des visites répétées. Utilisez Floyd Warshall et ensuite résoudre le problème d'affectation O (N ^ 3) en utilisant la méthode hongroise. Si nous avons eu une fois le cycle - c'est une solution de TSP dirigée, sinon, utilisez la branche et la TSP liée. Après cela, nous avons une valeur limite supérieure - le cycle du coût minimum.
solution exacte - approche de la branche et de la liaison. Nous retirons les sommets du cycle le plus court et essayons de créer un graphique fortement connecté avec moins de coût que la limite supérieure.
C'est tous les gens. Si vous souhaitez tester vos solutions - essayez ici: http://codercharts.com/puzzzle/caribbean-salesman
Quel est le but de Floyd Warshall?
Pourquoi peut utiliser Hongrois (n'ai pas besoin de prendre soin du poids?)
après avoir utilisé la méthode hongroise. Si nous n'avons jamais eu du cycle. Pourquoi le résultat était la valeur limité supérieure du cycle du coût minimum?
1. Nous avons besoin de fw pour l'étape 1. Si nous avons eu le chemin A-> B (par exemple A-> C-> B) plus court que le sommet original A-> B, alors nous pouvons supprimer ce sommet. 2. Si hongrois nous donne un cycle - il est égal à la solution de TSP dirigée, donc nous le prenons comme limite supérieure.
Si nous obtenons un cycle multi-cycle, nous faisons donc chaque cycle à un sommet virtuel et de la hongroise à nouveau? jusqu'à ce que nous n'obtenions qu'un seul cycle, alors c'est la limite supérieure
Aucune utilisation multiparative de l'algo hongrois ne nous obtient pas la solution de TSP dirigée :)
On dirait que l'étape 1 était utilisée pour obtenir une solution approximative (la valeur limite supérieure). Quelle est la moyenne de supprimer les sommets du cycle le plus court? Lors de l'utilisation de la branche et de la liaison, il aura besoin de calculer la limite basse afin que nous puissions jeter l'arborescence de redondance, mais quelle est la limite basse, j'essaie d'utiliser une mini entrée et une sortie et de ne pas sûrer comment ...
J'ai trouvé que lorsque vous utilisez une branche et lié pour résoudre le problème de la TSP. Les gens ont choisi d'utiliser une mini-entrée de nœud et une mini-coupuut, pourquoi cela fera-t-il partie de la limite basse? il semble apparaître deux choisi sur certaines lignes ou des cols
tks. J'ai eu A Expliquer pour pourquoi la somme (minipput, minioutput) / 2 sera la plus petite < / a>
Une 2-approximation du sous-scénomètre minimal est obtenu en prenant une union d'un minimum de ramification et de rabroucissage minimal, à la fois enracinée au même sommet (mais arbitraire). < / p>
Un sort-ramification , également connu sous le nom de arborescence , est un arbre dirigé enraciné à un seul sommet couvrant tous les sommets. Une ramification est la même avec les bords inversés. Ceux-ci peuvent être trouvés par algorithme d'Edmonds dans le temps o (ve) < / em>, et il y a des écarts pour o (e journal (v)) (voir le page wiki ). Il y a même un Implémentation open source .
La référence initiale du résultat 2-approximation est le Papier de Jaja et Frederickson < / a>, mais le papier n'est pas librement accessible.
Il y a même une approximation 3/2 par adrian vetta (PDF) , mais plus compliqué que ce qui précède.
Non ce n'est pas, j'essaie d'implémenter le TSP et ses variations
Je suis confus quant à ce que le coût est. Est-ce la somme du coût des bords que vous gardez? La somme du coût des chemins n ^ 2 entre chaque paire de nœuds? La somme du coût d'un ensemble de chemins couvrant chaque nœud (qui ne convient pas vraiment à l'exigence de SCC)?
coût serait une somme de poids de tous les bords qui font le graphique