Variazione sul problema del commesso viaggiatore - scegliere un buon sottopercorso da molti nodi sulla base di vincoli

Question

versione TLDR: La maggior parte questione importante è, che in un problema di TSP, invece di trovare il ciclo hamiltoniano più breve, che cosa sono buoni modi per trovare il percorso migliore (suppongo quello che le visite più nodi), che è al massimo di lunghezza X, con un punto di partenza fisso.

Versione completa:

Mi interessa alcune idee per un problema che coinvolge TSP. In primo luogo, un problema di esempio reale TSP è quando si hanno posizioni geografiche N da visitare e avete bisogno di indicazioni di guida per un percorso ottimale (o quasi ottimale) per visitare tutti, sia un andata e ritorno o dalla A alla Z. c'è una bella JS implementazione per questo a http://www.gebweb.net/optimap/ e un risolutore di JS TSP disponibili alla pagina http://code.google.com/p/google-maps -tsp-solver / .

Ora considerare che si dispone di N = 100 - 1000+ posizioni. A quel punto non è possibile calcolare il percorso con qualsiasi quantità ragionevole di tempo / risorse, ma anche se fosse possibile, che non è quella utile per la maggior parte degli scenari del mondo reale. Diciamo che si sceglie un punto di partenza fisso e sulla base di tale, da quelle 1000+ luoghi che si desidera generare un ottimale sottopercorso , che si inserisce in un (relativamente piccolo) vincolo max ( per esempio, un percorso che può essere coperto in 1 giorno o 1 settimana). Come può essere risolto in tempo reale? I miei pensieri sofar:

1. Crea la matrice durata da punto di partenza (questo passaggio è anche fattibile a poche migliaia punti) e scegliere un piccolo sottoinsieme di punti che sono più vicini al punto di partenza. Idealmente questo sottoinsieme dovrebbe essere abbastanza grande, che visitarlo completamente è sicuramente> vincolo max , ma abbastanza piccolo per elaborare rapidamente, per lo meno con algoritmi euristici.

2. Trova un percorso ottimale tenendo conto le location scelte nella fase 1. Ma invece di un percorso che le visite tutto punti di questa serie, ho bisogno del miglior percorso che soddisfa max vincolo in tal modo non dovrebbe visitare tutti i punti (lo possono visita tutto ma sarebbe il bordo Astuccio). Io non sono particolarmente sicuro su come sarebbe migliore per affrontare questo uno in modo efficiente?

Tutti i link, o idee apprezzate, in particolare per il punto 2.

responsabilità :. Naturalmente il nocciolo del problema è indipendente dal linguaggio, sto usando JS / Google Maps come un esempio di applicazione del mondo reale

Answer 1

OK, ecco il mio schizzo di una soluzione, in pseudo-codice. Hai bisogno di sapere su Priorità code

Define a data structure Route {
  the route taken so far, 
  and can give the score (nodes visited)
  the distance traveled
  and the remaining nodes allowed
  the current location.
}

Define a Priority Queue of Routes which sorts on distance traveled.
Define a SortedSet of Routes which sorts on score called solutions.

Add a Route of Length 0, at the depot to the priority queue.
Loop until the head of the priority queue is greater than MAX
   Route r = take the head of the priority queue.
   for each potential remaining node n in r, 
     (in increasing order of distance from the current location)
      child = a new route of r with n appended
      if child distance < max, append to priority queue, otherwise break
   if no children were appended add r to solutions

Questa efficace fa una ricerca in ampiezza dello spazio delle soluzioni, in modo ragionevolmente efficiente della memoria. Inoltre, se è troppo lento, poi quando il ciclo su tutti i bambini è possibile accelerare l'algoritmo da solo prendendo N più vicino vicini, dove N è configurabile. Si può perdere la soluzione ottimale, ma dovrebbe essere ragionevole nella maggior parte dei casi.