6.3.2. Problema de las n reinas.
Además, en cada nodo (excepto en las hojas) se comprueban 4 posibles descendientes. Este es el número de veces que se ejecutan las funciones Criterio y Genera (s[nivel]:= s[nivel] + 1).
Solución: Estimación de la eficiencia por probabilidad. Hacemos un cálculo aproximado del número de nodos esperado.
Estimación de la eficiencia por probabilidad.
- Generamos varias permutaciones de (1, 2, .., n), de forma aleatoria.
- Para cada una calcular el nivel al que llegaría (aplicando la función Criterio), y el número de nodos máximo para ese nivel.
- Hacer una media del número de nodos.