Hai usato un algoritmo di commesso viaggiatore per risolvere un problema?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho studiato TSP al college nel contesto di NP Completezza. In realtà non ho mai avuto una situazione in cui si sarebbe applicato a un problema pratico. Un po 'di ricerca mostra che è stato usato per scegliere il percorso più economico per spostare un trapano, che sta facendo buchi nei circuiti. È praticamente tutto ciò che ho potuto trovare.
Lo stai usando? Quali altre applicazioni pratiche ha la TSA?
Soluzione
Come con gli altri in questo thread, ho creato una soluzione a un problema NP completo al college (era un progetto secondario per un amico): un programma di programmazione. Al momento in cui ho accettato di lavorare sul suo problema, non sapevo cosa fosse NP completo. In seguito mi sono reso conto di aver escogitato una buona euristica per risolvere il problema, ma ovviamente il vero trucco era sapere quando dire all'utente che non c'era soluzione e che avevano sovraccaricato il problema.
È stato un ottimo modo per riunire le mie eventuali lezioni teoriche e il mondo reale.
Ancora una volta, l'euristica e "abbastanza vicino" vanno generalmente bene per gli usi del mondo reale in cui si preferiscono soluzioni quasi ottimali a causa del costo di ricerca e attuazione della soluzione ideale.
Altri suggerimenti
Una volta mi è stato assegnato il compito di scrivere un programma per riempire un'area rettangolare in modo abbastanza uniforme con un "squiggle". - una linea curva che non si interseca da sola. Il mio primo tentativo è stato quello di generare punti casuali all'interno del rettangolo e cercare di trovarne un tour (non necessariamente il più breve). Purtroppo questo approccio non ha funzionato molto bene e l'ho abbandonato.
Alla fine ho risolto il problema:
Il mio metodo di successo non era legato al TSP ma per i curiosi lo riassumerò:
Inizia con un segmento a linea singola. Ora loop: se una linea è "troppo lunga", dividerla in due. Sposta ogni punto un po 'a caso, ma fai in modo che i punti si respingano. Termina il ciclo quando è possibile fare pochi progressi. Ci sono dettagli ma spero che tu abbia l'idea.
Naturalmente questo produce un percorso angolare (che sarebbe stato accettabile) ma è facile trasformare gli angoli in archi lisci.
E sì, ho mantenuto il codice.
Non l'ho mai usato personalmente, ma un'altra applicazione oltre ai circuiti di perforazione è se vuoi andare in un numero di posti diversi, diciamo per vendere i vuoti. È possibile utilizzare una soluzione del problema per decidere il modo più economico per visitare ovunque esattamente una volta.
Sapere quando un problema è NP-difficile è utile per escludere soluzioni che implicano la risoluzione di quel problema. Ogni volta che vedi TSP (o qualsiasi altro problema NP-difficile) sollevare la sua brutta testa per problemi di dimensioni non banali che conosci stai andando sulla strada sbagliata. Non solo lo sai, ma conosci perché e puoi dirlo con sicurezza al tuo capo / compagno di squadra / a chiunque.
Detto ciò http://en.wikipedia.org/wiki/CONCORDE rivela che :
Il Concorde è stato applicato ai problemi di mappatura genica, [1] funzione proteica previsione, [2] percorso del veicolo, [3] conversione di immagini bitmap in disegni in linea continua, [4] programmazione dei movimenti delle navi per sismica sondaggi, [5] e nello studio del proprietà di ridimensionamento combinatorio problemi di ottimizzazione. [6]
Sì, lo uso nell'applicazione Geocaching per la pianificazione del percorso.
Attualmente utilizza una distanza in linea retta tra i punti ma dovrebbe correttamente (quando ci arrivo) utilizzare le strade per calcolare le distanze tra i punti.
Il più delle volte non si desidera utilizzare un algoritmo che risolva il problema NP-Complete / Hard. Vuoi solo un algoritmo che sia "abbastanza buono". Questi si basano generalmente sull'euristica e forniscono approssimazioni ragionevoli.
Ho avuto un problema che era un'istanza di Independent-Set (NP-Complete), ma ho trovato un algoritmo avido che ha dato risultati abbastanza buoni nella stragrande maggioranza dei casi e ha avuto un runtime efficiente.
Molti tipi di ordini ottimizzati, come il ritiro del car pooling, la consegna dei pacchi UPS, ecc. ovunque i requisiti di attraversamento dei nodi possano essere espressi in una dimensione di sforzo, come il tempo o la distanza.
TSP è il ciao mondo dei problemi NP completi. Nella sua forma canonica pura, non lo troverai spesso in natura ( demo come questa non inclusa ), ma un enorme sottoinsieme di problemi completi NP sono correlati o addirittura basati su TSP, come ad esempio:
- Routing del veicolo (include il routing del camion di approvvigionamento)
- Rotta aerea / volo
- Instradamento dei treni
- Percorso della macchina per l'aratro di piste da sci
Ognuno di questi ha vincoli extra specifici per il dominio, che li rendono più difficili da risolvere. Quindi TSP è una buona introduzione ai problemi completi di NP, per comprenderne la natura.
Pochi problemi nella vita reale corrispondono alle cose che impari durante le lezioni di matematica. I problemi sono semplificati e astratti in modo da poter vedere la matematica e non distrarsi dai dettagli. Il miglior esempio reale di TSP di grandi dimensioni, come hai menzionato, in realtà non coinvolge alcun venditore ambulante: comporta macchine di pianificazione che hanno lavori da eseguire con cristallografia a raggi X dove devi orientare un campione di un cristallo da diverse angolazioni.
Questa società si basava su un algoritmo TSP migliorato.
Indirizzano gli installatori e i riparatori di TV via cavo a New York tra gli altri problemi.
Poiché gli umani in genere sono in grado di risolvere i problemi TSP alla pari o meglio della maggior parte degli algoritmi per mappe con 20-60 nodi, non è molto comune avere un computer che risolva il problema. Quando il costo è abbastanza alto, avere il computer con un miglioramento dell'1-2% rispetto a un essere umano può valere il costo dell'esecuzione del calcolo. Se il percorso non cambia, allora si può giustificare passare del tempo a ottimizzarlo. Questo è comune nella progettazione di circuiti integrati.
I siti Web di viaggio delle compagnie aeree utilizzano una versione specializzata del problema TSP quando mostrano un elenco di compagnie aeree e i prezzi per ciascuna rotta. La differenza è invece della distanza, si ottimizzano per il costo e sicuramente non è necessario visitare una città una volta sola! Supponiamo che tu voglia volare da LGA a LAX. Ci sono circa 1/2 dozzine di rotte dirette e un numero infinito di altre rotte. Potrebbe suggerire LGA- > ORD- > LAX o LGA- > DWF- > LAX. Gli esseri umani, che possono valutare manualmente le rotte, a volte possono trovare tariffe più basse di quelle ricercate dai siti di viaggio. In genere, le persone non vogliono più di due collegamenti, ma non esiste un limite massimo al numero di collegamenti per un determinato volo.
L'ho usato per risolvere i percorsi del mio Gioco per iPhone del commesso viaggiatore . La cosa interessante è che le persone sono molto brave a risolvere il percorso più breve, ma non a risolvere il percorso più lungo. I percorsi più lunghi e più brevi hanno la stessa complessità, ma le persone sembrano addestrate per essere in grado di trovare percorsi più brevi, spesso più veloci e migliori di quelli che un computer può fare.
Nel mio primo lavoro abbiamo creato un'applicazione di pianificazione per l'assistenza domiciliare.
Abbiamo risolto il problema TSP con alcuni vincoli temporali non lineari e con un'ulteriore funzione di costo non lineare.
Abbiamo usato un solutore non ottimale per risolvere il problema.
Google Maps (e tutti gli altri software di routing basati su mappe) non utilizzano un qualche tipo di venditore ambulante per risolvere le indicazioni stradali?
Non ho usato TSP per quanto ne so, ma ho lavorato su una serie di robot autonomi per attraversare un labirinto. Quindi mi chiedo se TSP potrebbe essere applicato alla risoluzione dei labirinti.
