En un post anterior explicaba el algoritmo minimax (como introducción a la poda alfa-beta). Ahora veremos un poco de algorítmica, mas concretamente el backtracking. Podría decirse (a groso modo) que sería una busqueda minimax o poda alfa-beta pero sin heurística, además, el backtracking nos asegura que siempre encontrará la solución (si la hay) recorriendo así todos los estados posibles.
En wikipedia podemos obtener las reglas y una explicación de su complejidad, excelentes.Pongo la implementación en PHP como una primera aproximación para la resolución del problema (La implementación la he realizado en php y orientada a objetos para que sea mas facil comprender el proceso de backtracking, evidentemente, no persigo eficiencia).
Backtraking
El software dispone de modo traza para ver los pasos de "vuelta atrás"
Algunos tiempos de ejecución en mi ordenador:
- Tablero 4x4 => 0.19897794723511 seg.
- Tablero 5x5 => 39.455229997635 seg.
- Tablero 6x6 => 364.00200605392 seg.
- Tablero 7x7 => 39521.259037971 segundos
- Tablero 8x8 => aún ejecutándose :)
No hay comentarios:
Publicar un comentario