Math
Ampiezza e profondità
Due copie di un labirinto, due percorsi, una cella per battuta. Lo strato in cui l'ampiezza trova una cella È la distanza minima: un'identità. La profondità non è mai più corta, e di quanto sia più lunga dipende da dove si va.
Cosa succede
Un labirinto, due ricerche, una scoperta per passo. A sinistra la ricerca in ampiezza prende le celle da una CODA - chi entra per primo esce per primo -, quindi si allarga ad anelli, e l'anello in cui trova una cella è la sua distanza più breve: in un labirinto non pesato la ricerca in ampiezza È la ricerca del cammino minimo. A destra la ricerca in profondità le prende da una PILA - chi entra per ultimo esce per primo -, quindi si tuffa nella prima svolta e torna indietro solo a un vicolo cieco; il suo percorso è un percorso, senza promessa di essere breve. Le celle blu attendono nella struttura, quelle grigio-verdi sono finite, il quadrato dorato si sta espandendo, e sotto ogni labirinto sono elencate la coda e la pila vere, con la cella successiva per prima. Disegna muri, clicca in un labirinto per prevedere dove andrà dopo quella ricerca, poi fai un passo. Se la meta è murata, entrambe le ricerche finiscono al bordo della componente della partenza e lo dicono.
Equazioni del modulo
Equazioni labirinto su una griglia m x m, quattro vicini, partenza nell'angolo in alto a sinistra; ordine dei vicini su, destra, giù, sinistra - lo stesso in entrambe le ricerche ricerca in ampiezza: lo strato in cui si trova una cella È la lunghezza del cammino minimo - un'identità, verificata con un rilassamento INDIPENDENTE fino a un punto fisso e, sulle griglie piccole, con l'enumerazione completa dei cammini semplici griglia vuota: distanza da (i, j) = i + j; celle a distanza d = min(d, m−1) − max(0, d−m+1) + 1; strato più largo = m a d = m − 1; angolo opposto = 2(m−1) = 40 a m = 21 le due ricerche coprono lo STESSO insieme - la componente della partenza, contata in modo indipendente da una foresta di insiemi disgiunti - e ciascuna guarda ogni arco due volte: 2|E| = 1196 su 21x21 con il 20 % di muri la ricerca in profondità non è mai più corta, e quanto più lunga dipende dalla CELLA: fino all'angolo opposto di una griglia vuota richiede gli stessi 2(m−1) passi, fino alla cella un passo sotto la partenza ne richiede 421 a m = 21 su una griglia vuota l'albero della ricerca in profondità è un CAMMINO HAMILTONIANO - ogni cella ha al più un figlio, la più profonda sta a m²−1, e la parità decide dove finisce il serpente: (1,0) per m pari, (m−1,0) per m dispari 21x21, 20 % di muri, meta nell'angolo opposto: ampiezza 40 passi dopo aver toccato 370 celle; profondità 50 passi dopo aver toccato 53 - entrambe pagano, in moneta diversa lo stesso labirinto, meta al centro: ampiezza 20, profondità 156; e su 297 delle 371 celle raggiungibili il percorso in profondità è lungo almeno tre volte tanto
