Algoritmo di percorso più breve con vincolo di carburante e rifornimento variabile

Question

Supponiamo di avere un grafico ponderato non orientato. Si desidera trovare il percorso più breve dalla sorgente al nodo di destinazione mentre si inizia con un "carburante" iniziale. Il peso di ogni spigolo è uguale alla quantità di "carburante" che si perde andando oltre il bordo. Ad ogni nodo, puoi avere una quantità predeterminata di carburante aggiunta al tuo conteggio del carburante - questo valore può essere 0. Un nodo può essere visitato più volte, ma il carburante verrà aggiunto solo la prima volta che arrivi al nodo. ** Tutti i nodi possono avere diverse quantità di carburante da fornire.

Questo problema potrebbe essere correlato a un treno che viaggia dalla città A alla città B. Anche se i due sono direttamente collegati da una pista semplice, c'è una carenza di carbone, quindi il treno non ha abbastanza carburante per fare il viaggio. Invece, deve fare il viaggio molto più breve dalla città A alla città C, che è noto per avere abbastanza carburante per coprire il viaggio di ritorno verso A e quindi proseguire verso B. Quindi, il percorso più breve sarebbe la distanza da A a C più il distanza da C a A più la distanza da A a B. Supponiamo che il costo del carburante e la distanza siano equivalenti.

Ho visto un esempio in cui i nodi riempiono sempre il "serbatoio" fino alla sua capacità massima, ma non ho visto un algoritmo che gestisce quantità diverse di rifornimento di carburante a nodi diversi. Cos'è un algoritmo efficiente per affrontare questo problema?

Answer 1

Sfortunatamente questo problema è NP-difficile. Data un'istanza di percorso di commesso viaggiatore da s a t con soglia decisionale d (Esiste un percorso st che visita tutti i vertici di lunghezza al massimo d?), Creare un'istanza di questo problema nel modo seguente. Aggiungi un nuovo vertice di destinazione collegato a t da un lato molto lungo. Dare carburante iniziale d. Impostare la lunghezza del nuovo spigolo e del carburante in ogni vertice diverso dalla destinazione in modo che (1) il carburante totale di tutti i vertici sia uguale alla lunghezza del nuovo spigolo (2) non è possibile usare il nuovo spigolo senza raccogliere tutto il carburante. È possibile raggiungere la destinazione se e solo se esiste un breve percorso di commesso viaggiatore.

Di conseguenza, gli algoritmi per questo problema saranno simili a quelli di TSP. Preelaborare costruendo un grafico completo su sorgente, bersaglio e vertici con carburante diverso da zero. La lunghezza di ciascun bordo è uguale alla distanza.

Se ci sono abbastanza pochi vertici speciali, è possibile la programmazione dinamica esponenziale (O (2^n poly (n))). Per ogni coppia composta da un sottoinsieme di vertici (in ordine di dimensioni non diminuenti) e un vertice in quel sottoinsieme, determinare il modo più economico per visitare tutto il sottoinsieme e terminare al vertice specificato. Effettuare questa operazione in modo efficiente utilizzando i risultati precompilati per il sottoinsieme meno il vertice e ogni possibile ultimo waypoint.C'è un'ottimizzazione che elimina le sottoluzioni che sono peggiori di una soluzione conosciuta, il che può aiutare se non è necessario utilizzare molti waypoint.

In caso contrario, la riproduzione potrebbe essere una programmazione di numeri interi. Ecco una formulazione, probabilmente probabilmente migliorabile. Sia x(i, e) una variabile che sia 1 se il fronte diretto e è preso come il i ° passo (contando dallo zeroth) altrimenti 0. Sia f(v) il combustibile disponibile al vertice v. Lascia che sia y(i) una variabile che è il carburante in mano dopo i passi i. Supponiamo che il numero totale di passaggi sia T.

minimize sum_i sum_{edges e} cost(e) x(i, e) 
subject to 
for each i, for each vertex v, 
    sum_{edges e with head v} x(i, e) - sum_{edges e with tail v} x(i + 1, e) = 
     -1 if i = 0 and v is the source 
     1 if i + 1 = T and v is the target 
     0 otherwise 
for each vertex v, sum_i sum_{edges e with head v} x(i, e) <= 1 
for each vertex v, sum_i sum_{edges e with tail v} x(i, e) <= 1 
y(0) <= initial fuel 
for each i, 
    y(i) >= sum_{edges e} cost(e) x(i, e) 
for each i, for each vertex v, 
    y(i + 1) <= y(i) + sum_{edges e} (-cost(e) + f(head of e)) x(i, e) 
for each i, y(i) >= 0 
for each edge e, x(e) in {0, 1} 

Answer 2

Non esiste un algoritmo efficiente per questo problema. Se si prende un grafico esistente G della dimensione n, è possibile assegnare a ciascun lato un peso di 1, ciascun nodo un deposito di 5 e quindi aggiungere un nuovo nodo che si sta tentando di collegare a ciascun nodo con un peso di 4 * (n -1). Ora l'esistenza di un percorso dall'origine al nodo di destinazione in questo grafico è equivalente all'esistenza di un percorso hamiltoniano in G, che è un noto problema np-completo. (Vedi http://en.wikipedia.org/wiki/Hamiltonian_path per dettagli.)

Detto questo, si può fare meglio di una soluzione ricorsiva ingenua per la maggior parte dei grafici. Prima fare una prima ricerca di ampiezza dal nodo di destinazione in modo che sia nota la distanza di ogni nodo dal bersaglio. Ora puoi prendere in prestito l'idea principale della ricerca A * di Dijkstra. Effettua una ricerca di tutti i percorsi dall'origine, utilizzando una coda di priorità per cercare sempre di far crescere un percorso la cui distanza attuale + il minimo rispetto all'obiettivo sia al minimo. E per ridurre il lavoro probabilmente vuoi anche scartare tutti i percorsi che sono ritornati a un nodo che hanno visitato in precedenza, tranne che con meno carburante. (Questo eviterà percorsi sciocchi che girano intorno a loop avanti e indietro quando il carburante si esaurisce.)

Answer 3

Supponendo il consumo di carburante come peso positivo e la possibilità di aggiungere il combustibile come peso negativo e trattare ulteriormente l'iniziale di combustibile disponibile come un altro bordo pesata negativo, è possibile utilizzare Bellman Ford per risolverlo singola fonte percorso più breve.

Come da this answer, altrove, i grafici non orientati possono essere indirizzati sostituendo ciascun bordo con due in entrambe le direzioni. L'unico vincolo di cui non sono sicuro è la parte in cui è possibile effettuare il rifornimento solo una volta. Questo può essere risolto naturalmente dall'algoritmo, ma non ne sono sicuro.