Algoritmo di approssimazione per la variante TSP, inizio e fine fissi ovunque ma punto di partenza + più visite ad ogni vertice CONSENTITO

Question

NOTA: dovuto al fatto che il viaggio non termina nello stesso punto in cui è iniziato e anche il fatto che ogni punto può essere visitato più di una volta fintanto che visito ancora tutti loro, questa non è in realtà una variante TSP, ma l'ho messa a causa della mancanza di una migliore definizione del problema.

Quindi ..

Supponiamo che io sto andando su un'escursione con n punti di interesse. Questi punti sono tutti collegati da sentieri escursionistici. Ho una mappa che mostra tutte le tracce con le loro distanze, dandomi un grafico diretto.

Il mio problema è come approssimare un tour che inizia in un punto A e visita tutti i n punti di interesse, mentre termina il tour ovunque tranne il punto in cui ho iniziato e voglio che il tour sia il più breve possibile.

A causa della natura dell'escursionismo, ho pensato che questo non sarebbe stato un problema simmetrico (o posso convertire il mio grafico asimmetrico in uno simmetrico?), Poiché passare dall'altitudine all'altitudine è ovviamente più semplice dell'altro modo in giro.

Inoltre, credo che debba trattarsi di un algoritmo che funziona per grafici non metrici, in cui la disuguaglianza del triangolo non è soddisfatta, poiché passare da a a b a c potrebbe essere più veloce di prendere una strada lunga e bizzarra che va da a a c direttamente. Ho considerato se la disuguaglianza triangolare regge ancora, dal momento che non ci sono restrizioni riguardo a quante volte visito ogni punto, purché le visiti tutte, nel senso che sceglierei sempre il più breve di due distinti percorsi da a a c e quindi mai takr la lunga e bizzarra strada.

Credo che il mio problema sia più semplice di TSP, quindi questi algoritmi non si adattano a questo problema. Ho pensato di usare uno spanning tree minimo, ma ho difficoltà a convincermi che possono essere applicati a un grafico diretto asimmetrico non metrico.

Quello che voglio davvero sono alcune indicazioni su come posso venire con un algoritmo di approssimazione che troverà un tour ottimale nei pressi attraverso tutti i punti n

Answer 1

È possibile semplificare questo problema ad un normale problema TSP con n + 1 vertice. Per fare ciò, prendi il nodo 'A' e tutti i punti di interesse e calcola un percorso più breve tra ogni coppia di questi punti. È possibile utilizzare l'algoritmo di percorso più corto di tutte le coppie sul grafico originale. Oppure, se n è significativamente più piccolo della dimensione del grafico originale, utilizzare l'algoritmo del percorso più breve della singola origine per questi vertici n + 1. Inoltre puoi impostare la lunghezza di tutti i percorsi, che termina con "A", con un percorso costante, più grande di qualsiasi altro, che consente di terminare il viaggio ovunque (questo potrebbe essere necessario solo per gli algoritmi TSP, trovando un percorso di andata e ritorno) .

Come risultato, si ottiene un grafico completo, che è metrico, ma ancora asimmetrico. Tutto ciò che serve ora è risolvere un normale problema TSP su questo grafico. Se vuoi convertire questo grafico asimmetrico in uno simmetrico, Wikipedia spiega come farlo.

Answer 2

Per ridurre il problema a TSP asimmetrico, introdurre un nuovo nodo u e creare archi di lunghezza L da u a A e da tutti i nodi ma da A a u, dove L è molto grande (abbastanza grande da non rivedere la soluzione ottimale u). Elimina u dal tour per ottenere un percorso da A a qualche altro nodo tramite tutti gli altri. Sfortunatamente questa riduzione preserva l'obiettivo solo in modo additivo, il che rende le garanzie di approssimazione peggiori di un fattore costante.

L'obiettivo della riduzione Evgeny evidenziato è non-metrico TSP simmetrico, in modo che la riduzione non sia utile, poiché le approssimazioni conosciute richiedono tutte istanze metriche.Supponendo che la raccolta di scie formi un grafico planare (o che sia vicino ad esso), esiste un'approssimazione del fattore costante dovuta a Gharan and Saberi, che può essere sfortunatamente piuttosto difficile da attuare e potrebbe non dare risultati concreti nella pratica. Frieze, Galbiati, and Maffioli forniscono una semplice approssimazione del fattore di registro per i grafici generali.

Se ci sono un numero ragionevole di scie, diramazioni e rilegature potrebbero essere in grado di darvi una soluzione ottimale. Sia G & S che branch e bound richiedono la risoluzione del programma lineare Held-Karp per ATSP, che può essere utile di per sé per valutare altri approcci. Per molte istanze TSP simmetriche che si verificano in pratica, fornisce un limite inferiore al costo di una soluzione ottimale entro il 10% del valore reale.