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.
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.
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.
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.
Leggi altre domande sui tag algorithms graph