Come può l'algoritmo A * da applicare al problema del commesso viaggiatore? [duplicare]

Question

Eventuali duplicati:
Utilizzando A * per risolvere problema del commesso viaggiatore

Ho recentemente appreso che il A * algoritmo può essere applicato al problema del commesso viaggiatore. Bot esattamente come possiamo definire l'inizio e l'obiettivo qui, e come si applicano i pesi ai nodi (qual è l'euristica)?

Qualcuno mi spieghi come A * può essere applicato qui?

Answer 1

A * è un derivato del Dijsktra, che non credo che può essere utilizzato in questo modo. In primo luogo, il TSP inizia generalmente da qualsiasi nodo. Ancora più importante, però, questi algoritmi cercano di trovare il percorso più breve tra due punti, indipendentemente dal numero di nodi visitati. Infatti, essi dipendono dal fatto che il percorso più breve da S a T con qualche nodo A, il percorso da S ad A è irrilevante se è lo stesso costo.

L'unico modo che vedo questo funzionamento è che se si è generato un nuovo grafico che rappresenta i nodi visitati. Ad esempio, nella vostra coda di priorità, che ci si posiziona l'insieme dei nodi visitati e nodo corrente. Questo porterebbe ad esaminare possibilmente $ n2 ^ n $ nodi (che non è coindientally il tempo di esecuzione della soluzione di programmazione dinamica per il TSP http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM ). Finora, non grande, ma utilizzando un * invece di Dijsktra, si potrebbe essere in grado di trovare un'euristica che viene eseguito in un ragionevole lasso di tempo.

Per implementare questa, il nodo di partenza dovrebbe essere (1, {}) e il nodo finale sarebbe (1, {} 1..n). Si potrebbe imitare i pesi bordo del grafico originale. Per quanto riguarda i suggerimenti sul euristica, siete da soli ..

Answer 2

A * può essere applicato qui, anche se potrebbe non essere il miglior algoritmo.

Si dovrà allontanarsi dal grafico delle città e le strade tra di loro. Invece, definire un grafo orientato dove percorsi parziali sono i nodi e due nodi x e y sono sse collegato y può essere costruito da x con l'aggiunta di un singolo "step" nella città grafico originale. Il nodo di partenza è un percorso vuoto. Il nodo obiettivo è un percorso attraverso le visite che tutte le città. (Ottimalità di questo percorso è garantita dalle proprietà del euristica e A * stesso algoritmo.)

[ Modifica : In un primo momento ho pensato un percorso dovrebbe essere un elenco ordinato di città, ma ora credo di @ spinning_plate suggestione che rappresenta il percorso da una coppia (lunghezza, set di città) è sufficiente .]

Il costo del percorso è la distanza totale percorsa. L'euristica dovrebbe essere qualche ricevibile stima (di solito, una sottostima) del totale minima lunghezza della corsa.

Un buon candidato per tale stima potrebbe essere un'approssimazione veloce del TSP (la soluzione di un problema rilassato ). Faresti esegue l'algoritmo di approssimazione per ogni nodo (percorso parziale), sul set di città non ancora coperte. Che dà l'algoritmo la necessaria limite superiore sulla distanza il venditore deve ancora andare.

Answer 3

Se ho un martello ( A * Ricerca ), tutti i problemi ( TSP ) è un chiodo ( pathfinding ).

Sì, in teoria è possibile trasformare il problema TSP in un grafico molto più grande e l'uso A * Ricerca su di esso. Ma purtroppo è inutile perché non scala (vedi il commento di spinning_plate). Anche piccoli casi potrebbero richiedere anni per risolvere in questo modo su hardware moderno.

NP-completo , pathfinding non è.

Se si tratta di vite ( NP problema completo ), utilizzare un cacciavite ( metaheurstics, ... ).

Utilizzare algoritmi come metaeuristiche ( Tabu Search , algoritmi genetici, ricottura simulata, ... ). Per alcuni esempi di software, vedi Drools Planner , openTS, JGAP, cpsolver, ...

Answer 4

A * è un'estensione dell'algoritmo di Dijkstra dove la soluzione ottimale di attraversare un grafico direzionale viene presa in considerazione. Non sono sicuro che questo vale per il problema TSP.

Il problema TSP stati che si vuole ridurre al minimo la distanza che viaggiano durante la visita ogni destinazione esattamente una volta. L'algoritmo A * ha bisogno di un'euristica per guidarlo del modo in cui la soluzione ottimale è noto per essere una linea retta (bisogna stare attenti con la A * euristica di non sovrastimare la distanza alla meta). Questa dose non vale per il problema TSP.

domanda contiene anche informazioni sulla A * algoritmo e TSP problema.