Inteligencia artificial: Ejemplos de navegación por árboles
Enviado por duri_duran • 30 de Octubre de 2017 • Prácticas o problemas • 387 Palabras (2 Páginas) • 72 Visitas
Inteligencia artificial: Ejemplos de navegación por árboles
En el ejemplo del árbol de la derecha se pretende llegar del número 104 al 200, teniendo en cuenta las operaciones permitidas. Como podemos observar, la función heurística 1 presenta un mínimo local en 202. Esto se deduce de analizar los valores de la función tanto para el nodo anterior (203) como para el posterior (302). El nodo posterior se supone más cerca del objetivo por lo que el valor de la función heurística debería ser menor. Como este no es el caso, y el nodo anterior también presenta un valor superior al del nodo 202, podríamos afirmar que esta función heurística presenta mínimos locales. [pic 1]
Para la segunda función heurística, no encontramos motivos en el árbol de la derecha para poder decir si presenta mínimos locales o no. No obstante sí los presenta, como se puede observar en la tabla siguiente, en donde se muestra un ejemplo en el que se pretende ir del número 114 al 200. Para ello se realizan las operaciones señaladas en la tabla, llegando en el paso 5 a un mínimo local.
Paso | Op | Nodo | h |
0 |
| 114 |
|
1 | R3 | 113 | 5 |
2 | S1 | 213 | 4+1 |
3 | R3 | 212 | 3 |
4 | R2 | 202 | 2+1 |
5 | R3 | 201 | 1 |
6 | R1 | 101 | 2 |
7 | R3 | 100 | 1 |
8 | R1 | 200 | 0 |
Después de analizar estas dos funciones, llegamos a la conclusión de que cualquier función heurística que trabaje únicamente con la distancia de los dígitos a la solución va a presentar mínimos locales. Esto es debido a las restricciones de no poder aplicar dos operaciones sobre un mismo dígito y a la existencia de números prohibidos. En el caso de buscar una función heurística similar, que no presentase mínimos locales, seguramente propondríamos una función que sobreestimase.
...