Math
Anchura y profundidad
Dos copias de un laberinto, dos recorridos, una celda por tic. La capa en que la anchura encuentra una celda ES la distancia más corta, una identidad. La profundidad nunca es más corta, y cuánto más larga depende de adónde vayas.
Qué ocurre
Un laberinto, dos búsquedas, un descubrimiento por paso. A la izquierda la búsqueda en anchura toma las celdas de una COLA - el primero en entrar sale primero -, así que se extiende en anillos, y el anillo en que encuentra una celda es su distancia más corta: en un laberinto sin pesos la búsqueda en anchura ES la búsqueda del camino más corto. A la derecha la búsqueda en profundidad las toma de una PILA - el último en entrar sale primero -, así que se lanza al primer desvío y solo retrocede en un callejón sin salida; su ruta es una ruta, sin promesa de ser corta. Las celdas azules esperan en la estructura, las gris verdosas están terminadas, el cuadro dorado se está expandiendo, y bajo cada laberinto se listan la cola y la pila reales, la siguiente celda primero. Dibuje paredes, pulse en un laberinto para predecir adónde va después esa búsqueda y dé un paso. Si la meta queda tapiada, ambas búsquedas terminan en el borde de la componente del inicio y lo dicen.
Ecuaciones del módulo
Ecuaciones laberinto en una cuadrícula m x m, cuatro vecinos, inicio en la esquina superior izquierda; orden de los vecinos arriba, derecha, abajo, izquierda - el mismo en ambas búsquedas en anchura: la capa en la que se encuentra una celda ES la longitud del camino más corto - una identidad, comprobada frente a una relajación INDEPENDIENTE hasta un punto fijo y, en cuadrículas pequeñas, frente a una enumeración completa de caminos simples cuadrícula vacía: distancia a (i, j) = i + j; celdas a distancia d = min(d, m−1) − max(0, d−m+1) + 1; capa más ancha = m en d = m − 1; esquina opuesta = 2(m−1) = 40 con m = 21 ambas búsquedas cubren el MISMO conjunto - la componente del inicio, contada de forma independiente por un bosque de conjuntos disjuntos - y cada una mira cada arista dos veces: 2|E| = 1196 en 21x21 con 20 % de muros en profundidad nunca es más corto, y cuánto más largo depende de la CELDA: hasta la esquina opuesta de una cuadrícula vacía da los mismos 2(m−1) pasos, hasta la celda un paso por debajo del inicio da 421 con m = 21 en una cuadrícula vacía el árbol en profundidad es un CAMINO HAMILTONIANO - cada celda tiene como mucho un hijo, la más profunda está en m²−1, y la paridad decide dónde termina la serpiente: (1,0) para m par, (m−1,0) para m impar 21x21, 20 % de muros, meta en la esquina opuesta: anchura 40 pasos tras tocar 370 celdas; profundidad 50 pasos tras tocar 53 - ambas pagan, en distinta moneda el mismo laberinto, meta en el centro: anchura 20, profundidad 156; y en 297 de las 371 celdas alcanzables la ruta en profundidad es al menos tres veces más larga
