Shortest Path su un grafico non orientato?

Question

Così ho pensato che questo (anche se un po di base) domanda apparteneva qui:

Say Ho un grafico di dimensione 100 nodi disposte in un modello 10x10 (si pensi scacchiera). Il grafico è non orientato, e non ponderata. Si muove attraverso il grafico comporta lo spostamento di tre spazi avanti e uno spazio per a destra oa sinistra (simile a come un cavaliere di scacchi si muove attraverso una scheda).

Dato un nodo di inizio fisso, come si potrebbe trovare il percorso più breve per qualsiasi altro nodo sulla scheda?

I immaginato che ci sarebbe solo un vantaggio tra i nodi che sono mosse vitali. Quindi, dato queste informazioni, vorrei trovare il percorso più breve da un nodo di partenza per un nodo finale.

Il mio pensiero iniziale era che ogni bordo è ponderato con il peso 1. Tuttavia, il grafico non orientato, in modo Djikstras non sarebbe una misura ideale. Pertanto, ho deciso di farlo utilizzando una forma alterata di una ricerca in profondità.

Tuttavia, non ho potuto per la vita di me immaginare come ottenere il percorso più breve utilizzando la ricerca.

Un'altra cosa che ho provato stava mettendo il grafico in forma di albero con il nodo di partenza come radice, e quindi selezionando il risultato più superficiale (basso numero di riga) che mi ha dato il nodo finale desiderato ... questo ha funzionato, ma era incredibilmente inefficiente e, quindi, non sarebbe lavoro per un grafico più grande.

Qualcuno ha qualche idea che mi potrebbe puntare nella giusta direzione, su questo?

La ringrazio molto.

(ho cercato di mettere in una visualizzazione del grafico, ma non riuscì a causa della mia reputazione bassa)

Answer 1

Se i bordi nel grafico rappresentano solo validi si muove tra certe posizioni, utilizzando Dijkstra avrebbe funzionato bene. Tuttavia, come il grafico è ponderata sarebbe eccessivo. Un semplice breadth-first-search darà la risposta ottimale.

Answer 2

Nicholas già fornito una risposta perfetta. Tuttavia, vorrei affrontare il tuo tentativo originale per uso ricerca in profondità.

In primo luogo, sia Dijkstra (che funziona bene con i nodi non ponderati come notato da Nicholas Mancuso) o in ampiezza ricerca incorrere nei rifiuti esponenziale della vostra memoria. Il loro vantaggio, tuttavia, è che non hanno mai ri-espandere tutti i nodi, mentre sono garantiti per trovare le soluzioni ottimali. Purtroppo, la loro limitazione è molto importante e non dovrebbe essere previsto per scalare ragionevolmente.

Se si vuole risolvere grandi istanze del consumo problematico di iterativo-Approfondire Depth-First Ricerca (IDF). Basta emettere una ricerca in profondità dal vostro stato iniziale con una serie profondità massima ad una determinata soglia, $ d_ {max} $. Se non hai trovato la soluzione, quindi incrementare la profondità dell'ultima iterazione da una costante $ k $ fissa. Così, nel $ i $ -esima iterazione, una ricerca in profondità è lanciato in profondità $ d_ {max} + i \ times k $ (con la prima iterazione di essere numerati da 0). Se $ d_ {max} = k = 1 $ quindi si sono garantiti per trovare la soluzione ottimale durante l'uso della memoria lineare nella profondità della soluzione.

Bene, si potrebbe pensare che la ri-espansione nodi è piuttosto cattiva idea. Affatto! Questo è ciò che garantisce un consumo lineare della memoria mentre l'iterazione che domina il tempo complessivo di esecuzione è solo l'ultimo in modo che possa essere dimostrato che questo algoritmo incorre in un overhead di $ \ frac {b} {B-1} $ con $ b $ è il fattore effettivo di ramificazione, e questo è chiaramente un piccolo vale pena di prendere in considerazione al momento di fronte a problemi difficili.

Saluti,