La réduction de c. à thé de circuit Hamiltonien
Comment puis-je convertir l' (décision de la version) du problème du voyageur de commerce pour le circuit Hamiltonien problème (c'est à dire la façon de réduire c. à thé de HCP, de sorte que si j'ai une solution HCP, alors je vais utiliser cette solution pour résoudre c. à thé de problème)?
OriginalL'auteur Madu | 2012-11-13
Vous devez vous connecter pour publier un commentaire.
Tous les problèmes de NP peut être polynôme à temps réduit à n'importe quelle NP-complet de problème - c'est ce qui fait la NP-complet problèmes si importants.
Voici une chaîne de réductions:
C. à thé est un problème dans NP, de sorte qu'il peut être réduit, dans ridiculement long temps polynomial, de Circuit Hamiltonien.
J'ai eu les réductions de Ordinateurs et Intraitable: Un Guide de la Théorie de la NP-Complétude
Il y a un problème de décision formulation de c. à thé de, donné dans le livre que j'ai référencé. En évitant la notation mathématique, le problème de décision est de savoir si il y a une tournée de toutes les villes avec un poids total ne dépasse une certaine limite.
Je suis consciente qu'il existe, mais alors vous avez probablement dire "Le thé de problème de décision est dans NP si ..." problème de Décision formulations ne sont pas équivalentes pour le problème pour lequel la formulation est faite, il y a juste intermédiaires chemins de traduire un problème NP-complet de problème (pour prouver qu'un problème est NP-difficile). TSP est NP-dur qui est complètement différent d'être dans NP.
Il n'y a pas de formulation de la question, donc en supposant que les FST et Circuit Hamiltonien à la fois référé à la décision des problèmes avec ces noms est tout aussi raisonnable de ne pas le faire.
Oh, je vois. Qui serait effectivement un sens. (sinon, pourquoi voulez-vous traduire ces deux problèmes). Votre hypothèse est raisonnable, on devrait peut-être clarifier. Merci! 🙂 Et désolé pour la inutile de le sermonner.
OriginalL'auteur Patricia Shanahan
Le Cycle Hamiltonien Problème est prouvé pour être NP-complet (Comme d'aujourd'hui, le meilleur algorithme connu pour résoudre a exponentielle de la complexité),
Aussi, Le Cycle Hamiltonien Problème est un problème de décision (étant Donné un graphe, il y a une boucle avec le non-chevauchement des bords couvrant tous les sommets?) alors que c. à thé est un problème de recherche (Dans tous les cycles hamiltoniens me donner l'une avec un coût moindre).
.... Je ne pense pas que la réduction que vous demandez existe (intuitivement c. à thé est plus complexe) et si c'est le cas, je ne pense pas que ce serait vous aider en raison de L'Hamiltonien Problème étant NP-complet (exponentielle de la complexité n'est pas pratique pour les grandes suffisamment de problèmes).
Si vous voulez juste pour résoudre le TSP, puis il suffit d'utiliser l'un des algorithmes connus. Certains d'entre eux sont conçus pour fonctionner raisonnablement bien pour un petit nombre de sommets (c'est peut être suffisant pour vous).
Remarque: je suis en supposant que vous voulez dire la TSP problème de recherche et du Cycle Hamiltonien problème de décision, ce qui pourrait ne pas être le cas.
OriginalL'auteur fons
Prendre votre graphique et retirer toutes les arêtes. Prendre l'arbitraire d'un sommet v et ajouter des arêtes orientées à partir de ce sommet si l'avantage ajouté de destination n'est pas loin de v de k la constante de longueur de thé de problème de décision.
Si la construction du graphe a un cycle Hamiltonien, alors il est aussi un tour de longueur < k dans le graphique d'origine, donc une solution à la TSP.
Inversement, si il n'y a pas de cycle hamiltonien dans le graphe:
comme vous l'avez construit tous les chemins de longueur < k de départ au sommet v et comme une solution à la TSP est un chemin de longueur < k de départ à v, et un cycle hamiltonien, il n'y a pas de solution à la TSP dans le graphique d'origine.
OriginalL'auteur Serge Kireev
À partir de l'article de Wikipedia sur le Chemin hamiltonien problème, pourrait vous donner un indice:
"Le cycle Hamiltonien problème, c'est aussi un cas particulier du problème du voyageur de commerce, obtenu par le réglage de la distance entre deux villes à une si elles sont adjacentes et deux, et de vérifier que la distance totale parcourue est égale à n (si si, le parcours est un circuit Hamiltonien; si il n'y a pas de circuit Hamiltonien puis la route la plus courte sera plus long)."
OriginalL'auteur Bitwise
Bien, la question est de savoir ce que vous voulez faire exactement. Normalement, le TSP est de trouver la
smallest. Si vous voulez trouver le plus petit, alors vous ne pouvez pas le faire de cette façon. Uniquement si vous avez la solution à partir de la Hamilton problème.Parce que le Hamilton problème ne se soucie pas de pondération de bord, mais qui est nécessaire pour le vendeur.
Exemple:
Le graphique A,B,C avec A-(10)-B, B-(10)-C, C-(1)-Un
Clairement, A->B->C est un Hamilton façon, mais la solution optimale pour les pts serait->C->B
Si vous voulez juste trouver aucune solution pour le TSP, pas nécessairement le plus petit, alors que vous venez de la carte c. à thé de nœuds à Hamilton nœuds, de résoudre, de revenir avec la cartographie et vous avez terminé.
OriginalL'auteur tb-
l'entrée de l'instance de la TSP est un graphe complet et l'entrée de l'instance de Ham_Cycle est un graphe non orienté G(u,v). Ensuite, vous la transformation de la fonction doit mapper le graphe G un graphe complet.
fn w(u,v)
OriginalL'auteur Ashraf Saleh