L'animazione di Wikipedia per la generazione di labirinti con DFS non è coerente con l'algoritmo scritto dato lì, non è vero?

Question

L'animazione di Wikipedia per la generazione di labirinti con DFS non è coerente con l'algoritmo scritto dato lì, non è vero?

#1 da (2 voti)

4

Dai un'occhiata a questo link:

Qui, l'algoritmo teorico dato è:

Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell.

Ma non penso che l'animazione a destra usi lo stesso algoritmo per generare il labirinto, anche se non è corretto.

Ritengo che l'animazione utilizzi questo algoritmo:

Inizia con qualsiasi cella non visitata, fallo diventare parte del labirinto e contrassegnalo come visitato.
Aggiungi i vicini non visitati di quella cella al gruppo di celle che può essere considerato successivo
Scegli una qualsiasi cella dal set e contrassegnala come visitata.
Controlla se quella cella non ha nessun vicino visitato tranne ONE (quello che ha causato l'aggiunta di questa cella al set in primo luogo). Altro vai a 3.
Continua fino a quando tutte le celle sono visitate.

Mi sbaglio?

algorithms

posta Programming Noob 23.04.2012 - 23:38

fonte

1 risposta

Leggi altre domande sui tag algorithms

Derivati del file di origine e avvisi di attribuzione del copyright Esiste una tecnologia per l'assegnazione dinamica del contesto di esecuzione per i programmi destinati a molte piattaforme con prestazioni di runtime ampiamente variabili? [chiuso]

score 2 · Accepted Answer

L'animazione utilizza l'algoritmo descritto nell'articolo. Il loro stack consiste delle celle che sono state visitate. Quando raggiungono un vicolo cieco, tornano indietro schioccando le celle dalla pila finché non ne incontrano una che ha un vicino non visitato e quindi iniziano a esplorare un percorso che inizia in quella cella (spingendo quella cella nello stack).

Non stanno mantenendo un insieme di celle non visitate e ne scelgono a caso un altro da visitare. Se guardi da vicino, scelgono sempre di esplorare partendo da una cella più vicina al quadrato rosso.

Se etichettiamo le celle in modo che la cella in basso a sinistra sia (1, 1) e la cella in alto a destra sia (30, 20), noterai che la sua prima 'decisione' al momento 0:03 quando colpisce una fine a (1, 5). Torna indietro all'ultima cella con un vicino non visitato (1, 7) ed è costretto a esplorare (1, 8) dopo. Se capisco l'algoritmo che descrivi, dovresti scegliere casualmente una qualsiasi cella che ha toccato parte del percorso che è stato già generato.