Calcolo del percorso più breve in un labirinto

0

Attualmente sto cercando di mappare come creare un buon algoritmo che non avrà problemi per trovare il percorso più breve. Il labirinto consiste in una dimensione X e Y come input; Tuttavia, il labirinto genererà ostacoli all'interno delle dimensioni e generato casualmente. C'è un ingresso e almeno un'uscita dopo aver trovato il percorso più breve. Il modo per trovare l'uscita e il percorso più breve sarà in un ordine di movimenti. Prima controlla se è disponibile la salita, poi a sinistra, poi a destra e infine in basso (movimenti prioritari: up- > left- > right- > down). I movimenti devono essere orizzontali e verticali, quindi le mosse diagonali sono illegali, sfortunatamente.

Il mio pensiero era probabilmente quello di costruire un algoritmo di backtracking che risolva questo problema; ma c'è un problema per questo. Dice che il labirinto non sarà più di un miliardo di quadrati, il che significa che può essere un X e Y più grande. Pertanto, il programma si spegnerà e dovrà allocare più memoria da eseguire con un file Gigabyte. Quindi, per ridurre questa quantità di memoria, forse usare bitfield per ridurre e manipolare bitwise (che non ho mai usato come una struttura dati).

Il mio punto debole è di avere una solida base su come affrontare un problema che può essere devastante per codificare e come fare attenzione. Mi stavo chiedendo quale tipo di approccio dovrei considerare anche io. Sono felice di discutere ulteriormente e di essere curioso dei tuoi approcci. Mi piace fare un sacco di domande solo per me per capire in modo efficiente.

    
posta Zeid Tisnes 16.01.2018 - 23:04
fonte

1 risposta

2

Gli algoritmi di ricerca del percorso sono ben studiati. Cioè in genere utilizzi l'algoritmo A * se la posizione di uscita è nota e altrimenti l'algoritmo Dijkstra .

Entrambi funzionano su grafici non su griglie, quindi puoi ridurre la dimensione del problema trovando percorsi tra intersezioni connesse piuttosto che percorsi tra tessere adiacenti.

Il problema è più difficile se la mappa del labirinto non è visibile, ma deve essere scoperta camminando attraverso il labirinto. In tal caso, backtracking / depth-first-search è davvero una buona soluzione.

A * è una variante di Dijkstra che sa come camminare nella giusta direzione. Pertanto ha bisogno di cercare molti meno nodi nei tipici problemi. Per un labirinto progettato per ingannare, questo potrebbe non avere importanza.

Questi algoritmi eseguono una sorta di ricerca in ampiezza attraverso il grafico. Mantengono una coda di nodi, ordinati per il loro percorso minimo finora. Per ogni iterazione, la ricerca continua dal nodo che ha la distanza minima. Il vantaggio è che il primo percorso dall'inizio alla fine trovato è garantito come il percorso più breve. Non è necessario continuare a cercare. Nel peggiore dei casi, l'unico percorso è anche il percorso più lungo. Avrai quindi visitato ogni nodo una volta.

Entrambi questi algoritmi hanno una complessità ottimale nel caso peggiore con O(|V| log |V| + |E|) , dove |V| è il numero di vertici (nodi) nel grafico e |E| è il numero di spigoli. Ciò presuppone che la coda dei nodi da visitare sia implementata con un heap di Fibonacci.

Questo caso particolare è più semplice poiché il livello di ciascun nodo è limitato: ci sono al massimo 4 connessioni (su, giù, sinistra, destra) a ciascun nodo. Pertanto, il numero di fronti è limitato |E| <= 4 · |V| . Inoltre, il caso peggiore si verifica solo se la coda contiene quasi tutti i nodi. Per un problema 2D, il tuo grafico è planare e questo non può generalmente accadere. Vedrai quindi i tipici tempi di esecuzione vicini a |V| log sqrt |V| che si riduce quasi in modo lineare con la dimensione del labirinto.

Nel caso in cui il labirinto non abbia cicli (vale a dire, vi è al massimo un percorso dall'inizio alla fine), quindi non è necessario mantenere una coda di nodi vicini. Invece, un algoritmo basato su topologia può trovare tutti i percorsi dal nodo iniziale in Theta(|V| + |E|) , cioè il tempo lineare. Nota che un algoritmo basato sulla ricerca come A * potrebbe essere ancora più veloce in alcuni casi se riesce a trovare rapidamente il nodo di uscita.

Nei commenti sopra, Jules ha menzionato un ottimo tutorial link sulla ricerca del percorso. Contiene illustrazioni ricche e interattive che aiutano a costruire una chiara comprensione dei concetti di ricerca del percorso.

    
risposta data 19.01.2018 - 20:02
fonte

Leggi altre domande sui tag