Qual è l'algoritmo/soluzione più semplice per un singolo percorso più breve attraverso un grafico non orientato ponderato reale?

Question

Ho bisogno di trovare un percorso più breve attraverso un grafico non orientato i cui nodi sono reali (positivi e negativi) ponderati. Questi pesi sono come risorse che puoi guadagnare o perdere inserendo il nodo.

Il costo totale (somma delle risorse) del percorso non è molto importante, ma deve essere maggiore di 0 e la lunghezza deve essere la più breve possibile.

Per esempio consideriamo un grafico in questo modo:

A-start node; D-end node 

A(+10)--B(0)--C(-5) 
    \  | /
     \ |/
D(-5)--E(-5)--F(+10) 

Il percorso più breve sarebbe A-E-F-E-D

di Dijkstra da solo non fare il trucco, perché non in grado di gestire valori negativi. Quindi, ho pensato ad alcune soluzioni:

Prima si utilizza l'algoritmo di Dijkstra per calcolare la lunghezza di un percorso più breve da ciascun nodo al nodo di uscita, non considerando i pesi. Questo può essere usato come una sorta di valore euristico come in A *. Non sono sicuro che questa soluzione possa funzionare, ed è anche molto costosa. Ho anche pensato di implementare l'algoritmo di Floyd-Warshall, ma non so come.

Un'altra soluzione era calcolare il percorso più breve con l'algoritmo di Dijkstra non considerando i pesi, e se dopo aver calcolato la somma delle risorse del percorso è inferiore a zero, passare attraverso ciascun nodo per trovare un nodo vicino che potrebbe aumentare rapidamente la somma delle risorse, e aggiungilo al percorso (più volte se necessario). Questa soluzione non funzionerà se c'è un nodo che potrebbe essere sufficiente per aumentare la somma delle risorse, ma più lontano dal percorso più breve calcolato.

Ad esempio:

A- start node; E- end node 
A(+10)--B(-5)--C(+40) 
     \ 
     D(-5)--E(-5) 

Potresti aiutarmi a risolvere questo problema?

MODIFICA: Se durante il calcolo del percorso più breve, si raggiunge un punto in cui la somma delle risorse è uguale a zero, quel percorso non è valido, poiché non è possibile proseguire se non c'è più benzina.

Answer 1

Questa non sembra una soluzione elegante, ma data la possibilità di creare percorsi ciclici non vedo un modo intorno ad esso. Ma lo risolverei in modo iterativo. Usando il secondo esempio - Inizia con un punto in A, assegna il valore A. Sposta un 'giro' - ora ho due punti, uno a B con un valore di 5, e uno a D anche con un valore di 5. Spostare di nuovo - ora ho 4 punti da tracciare. C: 45, A: 15, A: 15, ed E: 0. Potrebbe essere che quello su E può oscillare e diventare valido, quindi non possiamo ancora lanciarlo. Sposta e accumula, ecc. La prima volta che raggiungi il nodo finale con un valore positivo hai finito (anche se potrebbero esserci percorsi equivalenti aggiuntivi nello stesso turno)

Ovviamente problematico in quanto il numero di punti a la traccia aumenterà abbastanza rapidamente e presumo che il tuo grafico sia molto più complesso dell'esempio.

Answer 2

Provare ad aggiungere il valore assoluto del peso minimo (in questo caso 5) a tutti i pesi. Ciò eviterà percorsi ciclici negativi

Gli attuali algoritmi di percorso più breve richiedono il calcolo del percorso più breve per ogni nodo poiché vanno combinando soluzioni su alcuni nodi che aiuteranno a regolare il percorso più breve in altri nodi. Non c'è modo di farlo solo per un nodo.

Buona fortuna

Answer 3

Modifica: Non ho letto abbastanza bene la domanda; il problema è più avanzato di un normale problema con il percorso più breve della singola sorgente. Sto lasciando questo post per ora solo per darti un altro algoritmo che potresti trovare utile.

Il Bellman-Ford algorithm risolve il problema del percorso più breve della singola origine, anche in presenza di spigoli con peso negativo. Tuttavia, non gestisce i cicli negativi (un percorso circolare nel grafico il cui peso è negativo). Se il tuo grafico contiene cicli negativi, probabilmente sei nei guai, perché credo che ciò renda il problema NP-completo (perché corrisponde allo longest simple path problem).

Answer 4

Lo farei in modo simile a quanto suggerito da Mikeb: fare una ricerca di ampiezza sul grafico degli stati possibili, vale a dire (posizione, carburante-sinistra) -pairs.

Usando il tuo esempio grafico:

• ottagoni: a corto di carburante
• Scatole: I nodi figlio omessi per ragioni di spazio

ricerca questo grafico in ampiezza è garantito per darti il ​​percorso più breve che raggiunge effettivamente l'obiettivo se esiste un percorso di questo tipo. In caso contrario, dopo un po 'dovrai rinunciare (dopo aver cercato i nodi x, o magari quando raggiungi un nodo con un punteggio superiore al valore assoluto di tutti i punteggi negativi combinati), poiché il grafico può contenere loop infiniti.

Devi assicurarti di non interrompere immediatamente la ricerca dell'obiettivo se vuoi trovare il percorso più economico (carburante saggio), perché potresti trovare più di un percorso della stessa lunghezza, ma con costi diversi.