Esiste un problema di commesso viaggiatore in cui la soluzione ottimale presenta bordi che si incrociano?traversate nel problema del commesso viaggiatore
I nodi sono in un piano x-y, quindi incrociare in questo caso significa che se si dovesse disegnare il grafico, due segmenti di linea che collegano quattro nodi separati intersecheranno.
banalmente, qualsiasi grafico collegato in cui ogni nodo ha due spigoli ha una sola soluzione TPS e se disegnato con incroci soddisferà i criteri indicati.
Se si mettono altri vincoli, come se si stesse modellando un viaggio in tutto il mondo usando gli alisei, quindi i costi sono solo in qualche modo legati alla posizione nello spazio, si potrebbe trovare un caso più complesso in cui l'attraversamento è ottimale.
"il grafico connesso in cui ogni nodo ha due spigoli" è un cerchio, non è vero? – AVB
Se due bordi in una linea poligonale chiusa si incrociano, allora c'è una linea poligonale con gli stessi vertici ma con un perimetro più piccolo. Questa è una conseguenza della disuguaglianza triangolare. Quindi, una soluzione per il TSP deve essere un semplice poligono. Vedi this article (Figura 4).
Domanda: Come parte del tour del commesso viaggiatore, non è necessario che l'ultima città visitata ricolleghi alla prima città visitata, e in questo modo l'ultimo percorso "interseca"/attraversa più fronti precedenti? Modifica: Forse dipende da come lo disegni? Come se esistesse un modo per disegnarlo come un poligono senza bordi intersecanti. – Jason
@Jason, il punto della mia risposta è il TSP euclideo, la soluzione non si incrocia mai. – lhf
Nel caso in cui l'articolo si sposti: ["Vendite e chip" in: Colonna caratteristica dell'AMS] (http: //www.ams.org/samplings/feature-column/fcarc-tsp) – Wolf
Se si considera una metrica non euclidea come L1 (distanza Manhattan), allora è abbastanza facile costruire tour più brevi che si intersecano.
+--3--+
| | |
| | |
2--+--1
| | |
| | |
+--4--+
Se ogni coppia vicina di incroci è raggiungibile a 1, quindi tutti i tour hanno lunghezza 8, compreso quello autointersecante che va 1 -> 2 -> 3 -> 4 -> 1
Tuttavia, credo che questo potrebbe essere tradotto in un problema di commesso viaggiatore in uno spazio euclideo tridimensionale, nel qual caso la soluzione ottimale (equivalente a questo), non avrebbe attraversamenti. La chiave per la mia aggiunta è che tutti i problemi NP completi, incluso il problema TSP a distanza di manhattan, possono essere "ridotti" l'uno all'altro. Quindi risolvere TSP manhattan non è diverso dal risolvere il TSP euclideo ... e nel TSP euclideo, nessuna soluzione ottimale avrà un vantaggio. –
È possibile ottenere i bordi di attraversamento se il costo di andare dal nodo A-> C più il costo B-> D> costo A-> B e C-> D. Potresti ottenere questo quando il costo non è adeguato alla distanza tra i nodi.
Un esempio di vita reale potrebbe essere che vi è un bonus da andare da A a C (ad esempio è possibile contrabbandare alcune contrabande) o il costo dipende dai passaggi precedenti (andare a sinistra un semaforo potrebbe costare molto di tempo).
Definire i bordi che si incrociano, per favore. –
Se i bordi si intersecano, ciascun nodo dipende dalla posizione. Essenzialmente questo significa che un incrocio è un nodo e quindi cambia la prospettiva di quale sia la soluzione ottimale. – Pindatjuh
Perché se due traiettorie di volo di un aereo si incrociano, puoi sempre saltare tra gli aerei a metà strada? –