Trova la lunghezza minima / massima del grafico diretto

Per il percorso più breve, inizia dal noto algoritmo di Dijkstra.

When you're on E, according to certain values and variable states, only G may be available...

Una soluzione semplice, che voglio incoraggiare a implementare, è implementare dijkstra in modo tale che chiami una funzione per ottenere i collegamenti in uscita da un determinato nodo. Puoi quindi fare i tuoi controlli lì. Quando cambiano le condizioni, invaliderei i risultati della ricerca e eseguirli di nuovo.

Nota : è ancora meglio se puoi contrassegnare i nodi come non validi. In questo modo l'algoritmo può memorizzare nella cache gli elenchi di collegamenti e rivalutare solo per i nodi invalidati.

Il fatto che un dato collegamento o nodo possa non essere disponibile non rappresenta un problema se il grafico non può cambiare mentre viene utilizzato. Basta calcolarlo per il grafico come lo hai.

Poiché questa è una preoccupazione, suppongo che ci sia qualcosa che attraverserà il grafico e potrebbe scoprire che è cambiata da un momento all'altro ... quando ciò accade, questo qualcosa ha avanzato una certa distanza sul grafico e ha senso calcolare il percorso dalla posizione corrente al bersaglio sul grafico modificato.

Non sono sicuro di come si desidera definire il percorso più lungo ...

Forse, una buona definizione per il percorso più lungo è: il percorso più breve che massimizza il numero di nodi visitati. Sotto questa definizione, camminare su un loop infinito non è vantaggioso.

Cercheremo il percorso più breve ... ma abbiamo bisogno di una nuova metrica per chiamare "distanza". La mia intuizione iniziale è di usare una metrica che non aumenta quando visitiamo un nuovo nodo.

Se la distanza non aumenta né diminuisce quando si visita un nuovo nodo, i seguenti percorsi hanno la stessa lunghezza:

A -> B
A -> C -> F -> G -> I -> B

Tuttavia, vogliamo che il secondo percorso sia migliore (intendo, "più breve", intendo, per avere un valore inferiore nella metrica, intendo, per essere preferibile).

Una soluzione semplice è ridurre la metrica quando si visita un nuovo nodo.

Note:

• Una metrica negativa può essere problematica. Per trovare il percorso, non è sicuro usare Dijkstra con negativi. Possiamo normalizzarlo solo con valori positivi usando una funzione sigmoid prima di comparare.
• Abbiamo anche bisogno di codificare la regola secondo cui la distanza è diversa a seconda di quale sia o non abbiamo visitato un nodo. Puoi risolvere questo con mezzi simili a quello che ho descritto per avere parti del grafico non disponibili. Tranne che, invece di passare il nodo corrente per valutare i collegamenti disponibili, si passa al percorso corrente.

Con questa metrica abbiamo:

A B - length: -1

A C D F G I B - length: -6

A C D E G I B - length: -6

A C D E B - length: -4

A C D E J - length: -4

A C D E C D F G I B - length: -5
        ¯ ¯
A C D E C D E G I B - length: -3
        ¯ ¯ ¯
A C D E C D E B - length: -1
        ¯ ¯ ¯
A C D E C D E J - length: -1
        ¯ ¯ ¯
A C D E C D E C D E F G I B - length: -1
        ¯ ¯ ¯ ¯ ¯ ¯

Quindi il nostro percorso "più lungo" è uno dei due percorsi più lunghi che non si ripetono ( A C D F G I B o A C D E G I B ).

Nel caso in cui non sia evidente, un percorso con un loop è sempre considerato peggiore rispetto alla sua variante senza loop poiché il loop attraversa i nodi visitati e quindi aumenta la metrica. E ricorda che stiamo riducendo la metrica.

Se stai usando Dijkstra con un sigmoide di questa metrica - come suggerisco io - i loop verranno scartati perché - come spiegato sopra - porteranno sempre a percorsi peggiori che quelli senza loop.

Addendum : dopo aver postato la risposta, noto che ho ottenuto alcuni risultati interessanti ... ad esempio: A C D E C D F G I B riesce a visitare più nodi di A C D F G I B ma punteggi peggiori (superiori), non è quello che mi aspettavo. Suppongo di poterlo modificare per essere più o meno interessati ad andare oltre il suo modo di raggiungere più nodi prima di raggiungere l'obiettivo applicando fattori alla distanza aggiunta o ridotta ... ad esempio, potremmo aumentare solo la metà del valore quando attraversando un nodo visitato Qual è la proporzione ideale per aumentare? Non ne ho idea. Per scopi pratici può essere ottimizzato per adattarsi al design o al dominio del problema.

Un problema curioso, come menzionato nei commenti sembra essere un'istanza del problema del percorso più lungo , che è NP -difficile. Dovrebbe esserci una soluzione esponenziale in tempo con backtracking. Per questo è necessario un qualche tipo di bookeeping (flag, hashset) di quali bordi / nodi sono già sondati dal percorso.
La soluzione potrebbe essere descritta come

1. Se il nodo corrente è un nodo obiettivo, registra il percorso se è il più lungo / il più breve finora
2. Se c'è un margine non visitato che conduce a un nodo non visitato, lo attraversa
3. Se non esiste tale margine, fai il backtrack fino a trovare il nodo che ha tale bordo (reimpostazione del flag attraversato sulla parte del percorso non tracciato)
4. Esci quando fai il backtracking al nodo di entrata e non ci sono bordi disponibili (= percorso è vuoto)

Prima parte:

Se conosci il punto di ingresso e l'elenco dei punti di uscita, e in assenza di qualsiasi euristica adatta, usa un approccio banale, L'algoritmo di Dijkstra per ogni coppia (entrata, uscita) e mantiene solo il più breve.

Per il percorso più lungo, utilizza una distanza negativa anziché la distanza nell'algoritmo.

Se hai un'euristica (es. c'è qualche geografia nel grafico), preferisci l'algoritmo A * perché sarà più efficiente.

Ora questo è banale, ma non il più efficiente: dato che hai un singolo punto di partenza, ricalcolerai la distanza degli stessi sotto-percorsi più volte. Quindi potrebbe essere interessante adattare l'algoritmo di Dijkstra, al fine di fermarsi solo quando tutti i nodi di destinazione sono raggiunti e lavorano simultaneamente con la distanza più breve e più lunga.

Seconda parte

Non è chiaro cosa cerchi di ottenere: minimo / massimo tra due nodi qualsiasi? O solo dai punti di ingresso?

Come suggerimento generale per questa parte più ampia, suggerirei di esaminare gli algoritmi per spanning tree , e guarda come sfruttare il risultato per il tuo scopo.

Ad esempio, se costruisci un albero di spanning minimo (MST), avrai un grafico aciclico che contiene tutto il percorso più breve tra tutti i nodi connessi. Quindi non avresti bisogno di eseguire l'algoritmo di Dijkstra per ogni coppia possibile; dovresti solo trovare l'unico percorso nel MST che contiene i due nodi. ( Nota: il termine "albero" potrebbe essere fuorviante: qui non si tratta di un albero costruito e bilanciato attorno a un nodo radice, ma un albero nel senso se la teoria del grafo, che è un grafo aciclico con un solo percorso tra qualsiasi due nodi )

MST ha diverse altre applicazioni in ottimizzazioni grafiche.

Nota che se il tuo grafico contiene diversi componenti connessi indipendenti (gruppo di nodi che sono raggiungibili tra loro), avrai bisogno di una foresta di spanning tree (un albero per ogni componente connesso). Se si utilizza per gli spanning tree una struttura dati che fornisce facilmente l'insieme di nodi nell'albero, si sarebbe in grado di trovare molto facilmente se 2 nodi sono connessi: entrambi devono appartenere al set di nodi dello stesso spanning tree .

Scopri la pianificazione delle azioni orientate all'obiettivo

link

Ciò consente di impostare le condizioni per i nodi disponibili.

Tuttavia, il problema con i loop è più difficile. Dovrai definire ciò che contati come ripetizione e non è così semplice come visitare due volte lo stesso nodo.

ad esempio potresti considerare il percorso più lungo nell'esempio come

A C D E C D F G I B