Inteligencia artificial: Ejemplos de navegación por árboles
duri_duranPráctica o problema30 de Octubre de 2017
387 Palabras (2 Páginas)122 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.
No obstante, podremos proponer una tercera función que aproxima mejor los números en los que la distancia de un dígito a la solución es mucho mayor que la distancia de los otros dos dígitos. Esta función heurística sería la siguiente:
h3(x) = d1 + d2 + d3 + positivo(d1-d2-d3-1) + positivo(d2-d1-d3-1) + positivo(d3-d1-d2-1)
La función positivo, es una función que nos devuelve 0 en caso de que el número sea negativo y el número en caso de que este sea positivo.
[pic 2]
Con esta función podemos saber si un dígito es mayor que la suma de los otros. Al restarle a un dígito los otros dos, para obtener la diferencia, debemos restarle adicionalmente una unidad para evitar así una posible sobreestimación.
...