algoritmo di approssimazione per TSP variante, partenza fissa e fine ovunque ma partendo point + visite multiple per ogni vertice AMMESSO

Question

NOTA: A causa del fatto che il viaggio non finisce nello stesso luogo è iniziato e anche il fatto che ogni punto può essere visitato più di una volta il tempo che mi ancora visitare tutti loro, questo non è davvero un TSP variante, ma lo metto a causa della mancanza di una migliore definizione del problema.

Il problema è stato originariamente pubblicato su StackOverflow, ma mi è stato detto che questo sarebbe un posto migliore. Ho ottenuto uno puntatore, che ha convertito il problema da non metriche ad un una metrica.

..

Supponiamo che sto andando su un'escursione con n punti di interesse. Questi punti sono tutti collegati da sentieri escursionistici. Ho una mappa che mostra tutti i sentieri con le loro distanze, dandomi un grafo orientato.

Il mio problema è come approssimare un tour che parte da un punto A e visite tutte le n punti di interesse, mentre terminando il tour ovunque, ma al punto in cui ho cominciato e voglio il tour di essere il più breve possibile.

A causa della natura del trekking, ho pensato che questo non sarebbe purtroppo un problema simmetrica (o posso convertire il mio grafico asimmetrica ad uno simmetrica?), Dal momento che va da alta a bassa quota è ovviamente più facile che il contrario .

Dal momento che non ci sono restrizioni per quanto riguarda il numero di volte che visito ogni punto, a patto che visito tutti loro, non importa se il percorso più breve da A a D passa attraverso b e c. Basta questo per dire che detiene disuguaglianza triangolare e quindi ho un problema metrica?

Credo che il mio problema è più facile che TSP, in modo da questi algoritmi non si adattano a questo problema. Ho pensato di usare un minimo spanning tree, ma ho un momento difficile applicarlo a questo problema, che, date le circostanze, dovrebbe essere un'asimmetrica grafo orientato metrica?

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

Answer 1

Non so come risolvere il problema o mostrare la sua NP-difficile, ma si possono trovare tutti paio percorso più breve per convertire il grafico a una metrica, basta sostituire $ E_ {a, b} $ con il percorso più breve da un ? B e se non c'è confine tra $ a, b $ aggiungi nuovo bordo con il minor peso percorso, ora è possibile eseguire una certa approssimazione per TSP per trovare approssimazione per il vostro problema, come io conosco meglio approssimazione per TSP è attualmente $ O ({\ log n \ over \ log {\ log n}}) $ . idea di base sta usando Held-Karp relax e trovando albero speciale spanning quindi utilizzando il metodo come algoritmo di Christofides. (Che ha alcune nuove definizioni come sottile albero, ... che rende più difficile rispetto ad altri metodi per caso asimmetrica), è possibile utilizzare anche noto $ o (\ log n) $ approssimazioni. Inoltre ho pensato il tuo problema di approssimare con una copertura ciclo minimo, ma non ho potuto ottenere un buon risultato. Se ho trovato niente io aggiornare questa risposta.