Aiuta con l'algoritmo per trovare il percorso ottimale tra i vari percorsi, dove l'ordine conta

Question

Aiuta con l'algoritmo per trovare il percorso ottimale tra i vari percorsi, dove l'ordine conta

#1 da (3 voti)

1

Questa sembra essere una variazione del problema del venditore ambulante, e ho iniziato (come per quanto alcuni leggano almeno) percorrendo quella strada per risolverlo, ma le restrizioni sugli ordini mi confondono un po '.

Ho una mappa con un numero arbitrario di destinazioni su di essa.
Un agente riceve un insieme di rotte commerciali.
Ogni singola rotta deve essere elaborata in ordine, ma tutte le rotte possono essere mescolate.

Ad esempio:

Inizio a S0 .
Ho una route Alpha che deve visitare A1 , A2 e A3 .
Ho una route Beta che deve visitare B4 , B5 e B6 .

Un'opzione valida sarebbe semplicemente unire le rotte insieme:

S0 - > A1 - > A2 - > A3 - > B4 - > B5 - > B6

Ma forse parti di Beta sono in realtà vicino alle parti iniziali di Alpha , quindi sarebbe meglio andare:

S0 - > A1 - > B4 - > B5 - > A2 - > A3 - > B6

Esiste un modo per calcolare una rotta ottimale (o "probabilmente abbastanza ottimale") tra questi nodi, senza calcolare ogni distanza tra ogni coppia possibile di nodi? In alternativa, potrei costruire un grafico di ogni viaggio possibile, ma sembra anche che potrebbe diventare problematico.

algorithms path-finding

posta Cylindric 18.06.2017 - 23:19

fonte

1 risposta

Leggi altre domande sui tag algorithms path-finding

È una cattiva pratica avere molti modelli di visualizzazioni e controller? È standard per registrare ogni caso di un'istruzione switch?

score 3 · Answer 1

La cosa sorprendente di questo problema è che ogni volta ci sono solo due scelte, la prossima A o la successiva B. Ciò significa che potrei codificare la rotta come AAABBB. Che in questo caso significa scegliere tutte le A e quindi tutte le B's.

Questo rende semplice esplorare ogni possibile viaggio. Solo permute quella stringa. Se sei riluttante a calcolare tutti quelli che potresti eseguire l'algoritmo ingordo e scegliere sempre quale sia mai più breve, A o B, ad ogni passo. Non può garantire di essere ottimale ma è probabile che sia ragionevole.