Supongo que te estás refiriendo al problema del cubo Rubik 6.006, página en mit.edu
En primer lugar, debe hacer BFS, porque eso le brinda los caminos más cortos. DFS no es particularmente útil en esta situación.
En segundo lugar, el BFS de dos lados es apropiado aquí debido a la apariencia del gráfico de estado. Desde cualquier estado de cubo, puede alcanzar algunos otros estados (llamémoslo k estados, olvidé cuántos movimientos puede realizar). Hay poca superposición entre los estados alcanzables, incluso después de tener en cuenta todas las simetrías posibles.
- ¿Por qué los registros cuánticos son mejores que los registros clásicos (computación cuántica)?
- ¿Puedes jugar con un procesador cuántico?
- ¿Podría decirse que el mundo no observado es cuántico y el mundo observado es clásico?
- ¿La amenaza de la Inteligencia Artificial Avanzada y la Computación Cuántica hace que la amenaza del calentamiento global parezca un día más de verano?
- ¿Qué piensan los físicos sobre la explicación intuitiva de la mecánica cuántica por Eliezer Yudkowsky? ¿Qué tan bueno / preciso es?
Si usa Vanilla BFS y encuentra la solución después de que l se mueva, habrá explorado l niveles del gráfico y habrá descubierto los caminos más cortos a todas las configuraciones que están a menos de su punto de partida. Debido a la apariencia del gráfico, explorará aproximadamente k ^ l nodos.
Si usa BFS de 2 lados, los dos lados se encontrarán después de explorar 1/2 nodos en cada lado. Esto significa que explorará 2 * k ^ (l / 2), que es aproximadamente la raíz cuadrada de cuántos nodos habría explorado con BFS directo.
Si desea visualizar esto, BFS le ofrece un árbol corto y grueso. BFS de 2 lados le ofrece un diamante compuesto por 2 pequeñas mitades del árbol corto y gordo.
