Come implementare l'algoritmo di commesso viaggiatore con dipendenze tra posizioni

4

C'è un modo per implementare il venditore ambulante o l'algoritmo dell'acquirente con vincoli tra le posizioni? Per esempio, devo prendere l'oggetto X prima dell'articolo B, c prima di D e F, G, H in qualsiasi ordine.

    
posta SaadK 09.02.2018 - 08:20
fonte

3 risposte

2

Gli elenchi di Wikipedia diversi approcci per soluzioni esatte ed euristiche per il TSP standard. Ognuno di questi approcci esplora lo spazio di soluzioni e soluzioni parziali in un ordine speciale. Quindi immagino che la maggior parte di loro (forse tutti) possano essere estesi limitando lo spazio di ricerca a quelle (parziali e complete) soluzioni che soddisfano le tue dipendenze aggiuntive.

Come semplice esempio, l'euristica del vicino più vicino seleziona normalmente una posizione dopo l'altra e sceglie sempre la posizione non visitata più vicina. Ora estendilo con il vincolo addizionale di scegliere la posizione più vicina tranne B, purché X non sia stato visitato prima.

Ovviamente, per trovare soluzioni veramente buone che sono vicine all'ottimo, è necessario implementare qualcosa di più sofisticato come ricottura simulata , limitato allo spazio di ricerca di soluzioni (parziali) che soddisfano l'elenco dei vincoli.

    
risposta data 10.02.2018 - 07:43
fonte
1

Se hai solo una una dipendenza , "afferra l'elemento X prima dell'elemento B", la soluzione è banale.

Trova il percorso più breve possibile. O incontri X prima di B su quella rotta, o percorri il percorso nella direzione opposta.

    
risposta data 10.02.2018 - 18:57
fonte
0

Per quanto comprendo la tua domanda, il problema che stai cercando di risolvere è stato studiato sotto il nome di problema di venditore ambulante con vincolo di precedenza, questo potrebbe costituire un buon punto di partenza per la tua ricerca.

    
risposta data 13.02.2018 - 23:16
fonte

Leggi altre domande sui tag