Trovare il percorso più breve tra i nodi con una svolta

Trasforma il tuo grafico in qualcosa che può essere cercato facilmente!

Come?

Dato un grafico X {A, E} (A essendo l'insieme di vertici, E essendo l'insieme di bordi (diretti)), costruisci un grafico X' {A, E*} , in modo che un bordo sia in E* (dal punto B puntare D) se c'è una coppia di bordi in E tale che il primo sia da B a C, e il secondo - da C a D.

Potresti anche voler mantenere una mappatura inversa per i bordi (ad esempio, come è stato costruito il bordo?)

Quanto è difficile?
Potenzialmente fino a N ^ 3 dove N è il numero di vertici, a seconda della struttura del grafico. Dato che gli algoritmi di ricerca del percorso sono generalmente nell'ordine di N ^ 2 a N ^ 3, dovrebbe andare bene. Anche N ^ 3 è il modo ingenuo: potresti essere in grado di trovare un modo migliore.

Che cosa faccio con questo?
Dato questo nuovo grafico - Qualsiasi percorso di pari lunghezza in X è un percorso in X' se si elimina ogni vertice dispari. Inoltre, qualsiasi percorso attraverso X' è un percorso di lunghezza pari fino a X se si riempiono gli spazi attraverso la mappatura inversa dalla prima sezione. OSSIA Hai una proiezione da percorsi di lunghezza pari in X a percorsi in X' .

Questa suriezione preserva anche il paragone della lunghezza del percorso - un percorso K 'è più lungo di un percorso L' in X' se i loro percorsi corrispondenti in X - K e L - hanno la stessa relazione, cioè K è più lungo di L .

Eh ... OK, allora? Bene, tutta questa teoria ti consente di rivendicare una cosa precisa: il percorso più breve attraverso X' avrà un percorso di lunghezza pari più breve corrispondente attraverso X . Questo grafico avrà lo stesso numero di vertici e forse un numero maggiore o minore di spigoli. Quindi uno dei numerosi algoritmi di ricerca del percorso funzionerà - la tua domanda implica che puoi già usarli.

Posso fare tutto questo senza il grafico in più?
Perchè si! Certo che puoi! Usa la tua immaginazione! Come in - non costruisci esplicitamente il grafico in più. Basta implicarlo . Ciò richiederà modifiche all'algoritmo di ricerca del percorso effettivo: quando viene chiesto ai nodi adiacenti a un determinato nodo, anziché elencare tutto collegato direttamente, elencare tutto collegato tramite esattamente 2 spigoli.

A seconda della situazione, questa potrebbe essere una soluzione migliore. Quello "teorico" consente l'utilizzo di algoritmi di ricerca pronti all'uso, ma soffre di molte impostazioni. Il secondo mitiga l'impostazione al costo di modificare gli algoritmi (e IMHO ha più spazio per gli errori)

(Presumo che abbiate mescolato il termine "vertici" con "bordi", un grafico di solito consiste in vertici = nodi, con bordi tra loro).

Vorrei provare qualcosa sulla falsariga della seguente idea:

• dal tuo grafico iniziale, costruisci uno nuovo contenente gli stessi nodi, ma bordi diversi

• disegna un bordo nel nuovo grafico tra due nodi A e B, quando c'è un percorso in due passaggi da A a B nel grafico originale. Questo dovrebbe essere facile da costruire eseguendo una semplice ricerca in profondità su ogni nodo con una profondità limitata di 2. Se il tuo grafico originale aveva bordi ponderati, assegna ai nuovi bordi la somma dei pesi dei due bordi corrispondenti dal grafico originale

• ora puoi applicare un algoritmo standard per il percorso più breve a questo nuovo grafico

• dalla soluzione trovata dovrebbe essere banale costruire il percorso corrispondente nel grafico originale

Funziona perché ogni tracciato con un numero pari di spigoli nel grafico originale può essere suddiviso in sotto-percorsi di lunghezza 2.