Costruire un creatore del percorso

Mi sembra che sapere che tutte le strade eseguano N_S o E_W ti consentiranno di calcolare facilmente un'euristica eccellente per A * algoritmo , che al primo pensiero sembrerebbe essere il miglior algoritmo per scopi generali per risolvere questo problema.

Con una così grande euristica dovresti essere in grado di utilizzare una struttura estremamente sparsa a causa della possibilità di eseguire potature estese.

EDIT - In risposta alla richiesta di elaborare sull'euristica: Con l'algoritmo A * è necessario un euristico ammissibile , {h (x)} che è una stima della distanza dal nodo corrente verso il bersaglio. Per essere "ammissibile" l'euristica o la stima della distanza dal punto corrente (x) all'obiettivo deve essere inferiore o uguale alla distanza reale. Normalmente si può usare la distanza in linea retta ("in linea d'aria") tra i due punti, poiché nessuna strada effettiva potrebbe essere più corta di una linea retta.

Nel tuo problema ti viene detto che tutte le strade corrono verso nord-sud o est-ovest, quindi senza strade diagonali. Facciamo un esempio specifico: Supponiamo che si voglia stimare la distanza minima, h (x), per iniziare dal punto (0,0) e arrivare a (10,10). Ora questo è un quadrato con un lato di lunghezza 10, quindi normalmente si stima che potrebbe esserci una strada che andava direttamente da (0,0) a (10,10), quindi la distanza della linea retta sarebbe la radice quadrata di 200 o circa 14,14. Ma nel tuo caso, dal momento che tutte le strade percorrono N-S o E-W, sappiamo che la distanza minima possibile è 20. Ovviamente la distanza reale potrebbe essere più dipendente dalle strade disponibili.

Poiché hai un'euristica ammissibile per due punti (x1, y1), (x2, y2) essendo h (x) = (abs (x2-x1) + abs (y2-y1)); questo h (x) è sempre maggiore o uguale alla distanza della linea retta, e quindi è un euristico "migliore" in quanto porterà a uno spazio soluzione più piccolo che dovrà essere esplorato. In altre parole una maggiore potatura degli alberi.

Non c'è dubbio che un algoritmo di rete stradale e di rotta è meglio modellato con un grafico e usando l'algoritmo A *, Dijkstra o qualche variazione di quelli per la ricerca.

Nel tuo caso, senza dubbio le intersezioni dovrebbero essere modellate come nodi e le strade come bordi. Come autore di un pacchetto GPS commerciale, modifico il punto di partenza di ogni strada come nodo (quindi una giunzione di tre strade ha tre nodi); questo modello più complesso ti consente di contare i costi di virata (in particolare, rendendo costosi i turni a U) e le restrizioni di svolta.

Se tutte le strade hanno lo stesso limite di velocità o se vuoi trovare la distanza più breve, A * è un buon algoritmo, ma se h (x) non è abbastanza vicino al costo effettivo del percorso, l'instradamento A * potrebbe non offrire vantaggio di velocità rispetto all'algoritmo Dijkstra più semplice. Ho usato A * in origine, ma in questi giorni utilizzo un algoritmo Dijkstra bidirezionale modificato, che puoi pensare come A * senza il sovraccarico extra del calcolo h (x).

Il fatto che tutte le strade si trovino su una griglia può influenzare la struttura dati scelta, ma puoi dividere il codice in due parti, una è un algoritmo A * o Dijkstra generico che supporta qualsiasi grafico indipendentemente da come è memorizzato, e l'altro si occupa dei dettagli di implementazione della struttura dati.

Un grafico diretto dovrebbe essere l'approccio migliore nel tuo caso. Probabilmente è vero che una struttura più ottimale potrebbe forse essere concepita prendendo in considerazione il vincolo dato che le strade possono essere dirette solo Nord-Sud o Est-Ovest, ma non vorrei perdere tempo a pensare a questa possibilità: legherebbe il tuo soluzione a un vincolo artificiale e risulterebbe in una struttura dati che sarebbe più hacky e meno accademica. Puoi prendere in considerazione questo vincolo se ti viene chiesto di disegnare la mappa del tuo dominio, ma questo è tutto.

Crea una griglia (array bidimensionale) di giunzioni. Ogni Giunzione può avere un'uscita verso sud e un'uscita verso est (le uscite nord e ovest sono uscite dalla cella vicina). Ogni uscita può avere un nome e un intervallo di numeri. Questo ti permette di navigare.

Per una ricerca più semplice, un nome di strada dato è un elenco di riferimenti di Junction.