existe-t-il un problème de vendeur itinérant où la solution optimale a des arêtes qui croient?
Les nœuds sont dans un plan X-y, le croisement de ce cas signifie si vous devez dessiner le graphique, deux segments de ligne connectant quatre nœuds distincts se croisent.
4 Réponses :
De manière triviale, tout graphe connecté où chaque nœud a deux bords n'a qu'une solution TPS, et si elles sont dessinées avec des passages à niveau correspondent à vos critères indiqués.
Si vous mettez d'autres contraintes, telles que si vous modeliez voyager dans le monde en utilisant des vents commerciaux, les coûts ne sont que quelque peu liés à la position dans l'espace, vous pourriez trouver un cas plus complexe où la traversée est optimale.
"Graphique connecté où chaque nœud a deux bords" est un cercle, n'est-ce pas?
Si deux bords dans une ligne de ligne polygonale fermée, il y a une ligne polygonale avec les mêmes sommets mais avec un périmètre plus petit. C'est une conséquence de l'inégalité du triangle. Donc, une solution au TSP doit être un simple polygone. Voir Cet article (Figure 4).
Question: Dans le cadre de la tournée commerciale itinérante, n'est-il pas nécessaire que la dernière ville visitée se connecter à la première ville visitée et que le dernier chemin «intersecte» / traverse plusieurs bords précédents? EDIT: Peut-être que cela dépend de la façon dont vous le dessinez? Comme il y a un moyen de le dessiner comme un polygone sans bords intersectant.
@Jason, le point de ma réponse est le pour la TSP euclidien, la solution ne se traverse jamais.
Juste au cas où l'article se déplace: "Ventes et puces" dans: Colonne de fonctionnalités de la AMS
Si vous envisagez une métrique non euclidienne comme L1 (Distance Manhattan), il est assez facile de construire des visites les plus courtes qui se croisent auto-intersect. si chaque paire d'intersections voisines est à Distance 1, puis toutes les visites ont la longueur 8, y compris l'auto-intersection qui va 1 -> 2 -> 3 -> 4 -> 1.
Cependant, je pense que cela pourrait être traduit dans un problème de vendeur itinérant dans un espace de 3-D euclidien, auquel cas la solution optimale (équivalente à celle-ci) n'aurait aucune traversée. La clé de mon ajout est que tous les problèmes de NP complets - y compris le problème de la TSP de la distance de Manhattan - peuvent être "réduits" les uns aux autres. Donc, la résolution de la TSP de Manhattan n'est pas différente de la résolution de la TSP Euclidian ... et de l'euclidian TSP, aucune solution optimale n'aura une traversée de bord.
Vous pouvez obtenir des arêtes de croisement si le coût d'aller du nœud A-> C plus le coût B-> D> coûte A-> B et C-> D. Vous pourriez obtenir cela lorsque le coût n'est pas approprié à la distance entre les nœuds.
Un exemple de vie réel peut être qu'il existe un bonus d'aller de A à C (par exemple, vous pouvez faire une contrebande de contrebande) ou le coût dépend des étapes précédentes (Turing laissant des feux de circulation pourraient vous coûter beaucoup de temps).
Définir les bords qui croient, s'il vous plaît.
Si les bords traversent, chaque nœud est dépendant de l'emplacement. Cela signifie essentiellement qu'un bord de croisement est un nœud, puis change la perspective de la solution optimale.
Parce que si deux chemins de vol d'aéronefs traversent, vous pouvez toujours sauter entre les avions à mi-chemin?
@Pete Kirkham, quel est ton point?
@Pindatjuh Airports / Vols sont un exemple de graphique pour entrer dans un solveur de TSP où les bords de croisement n'introduisent pas de nœud.
@bob La réponse à cette question dépend entièrement de deux informations que vous ne fournissez pas - que vous utilisiez une métrique euclidien et si vous pouvez envisager une franchise des bords d'un nœud. Si vous avez une métrique eucidienne, mais pas de changement à des traversées (par exemple une compagnie aérienne plate avec un ensemble fixe de vols entre les villes), il y a des exemples avec des passages à niveau, si vous avez d'autres métriques avec des nœuds implicites à travers une traversée, il y a de nouveau des exemples, mais Si vous avez à la fois des métriques Eucildian et des nœuds implicites à toutes les passages à niveau, le raisonnement de LHF s'applique.