Búsqueda heurística
En casi todos los espacios de estado, existe información que permite guiar los procesos de búsqueda, normalmente esa información no es perfecta, es decir no es un algoritmo que permite conocer de forma precisa cual es el mejor camino para obtener la solución.
Este tipo de información no perfecta que ayuda a resolver problemas a un espacio de estado, pero que no siempre acierta con el mejor camino se denomina heurística.
Cuando se dispone de este tipo de información las técnicas de búsqueda se pueden ver muy beneficiadas de su utilización.
Técnica de escalada
La técnica de escalada es la evolución de la técnica de profundidad en la que cada nodo se dispone en una forma de evaluar cómo está de cerca o de lejos la solución. La forma más común de evaluar es la función de evaluación.
f(nodo)= # de casillas bien colocadas (maximizo)
f’(nodo)= # de casillas mal colocadas (minimizo)
Como ejemplo del juego 8-puzzle se puede definir una función de evaluación que fuera igual:
f(nodo)= # de casillas bien colocadas (máximo)
Que devuelven un número que representa como está de cerca un determinado estado de la solución, cuanto mayor sea el número se estará cerca de la solución.
Por tanto si se tiene que elegir entre varios estados se debería escoger aquel, que tendría un valor mayor de esta función, es decir es una función que se debe maximizar.
procedimiento escalada (estado inicial estado final)
N = estado inicial; Exito = Falso.
Hasta que éxito.
Generar los sucesos de N
Si algún sucesor es estado final entonces Exito = Verdadero.
Si No
- Evaluar cada nodo como la función de evaluación
- N = mejor sucesor
Si Exito
entonces Solución = camino desde nodo del estado-inicial al nodo N por los
punteros.
Si No
Solución = Fracaso.
La técnica de escalada exagera los problemas de la profundidad en el sentido de que no asegura de que se alcance la solución óptima relacionada con esto existen dos problemas que ocurren a menudo cuando se utiliza escalada:
1. Puede haber máximo o mínimos locales esto ocurre por ejemplo cuando la función de evaluación elegida es maximizante y todos los sucesores de un determinado nodo tienen menor valor que el valor del nodo.
2. Altiplanicies: Es un caso parecido al anterior y sucede cuando los mejores sucesores de un nodo tienen igual valor que el nodo. Las soluciones que se pueden adoptar son:
- Retroceder
- Dar mas de un paso
Retroceder: A la lista de razones a la que se debe retroceder que provienen a la técnica de profundidad se le añade cuando ocurra cualquier caso de los anteriores.
Dar más de un paso: En lugar de retroceder se generan todos los sucesores de los sucesores del nodo en cuestión y aún así no hay ningún sucesor de los sucesores que sea mejor que el nodo, se puede expandir un nivel mas, hasta que se obtenga un valor mayor / menor que el nodo.
Método de Haz
Es una variación de la técnica ecalada. Considera a K como el número de ramas a expandir.
Búsqueda Avara
Es cuando se reduce al mínimo el costo estimado para alcanzar un a meta, h(n). Aunque por lo general, el tiempo de búsqueda disminuye en comparación con lo necesario cuando se emplea un algoritmo que no cuenta con información, el de la búsqueda ávara no es un algoritmo óptimo y completo.
Para un mejor entendimiento de esta búsqueda se aplicará en distancia de ciudades de Arad – Bucharest:
También considere el siguiente cuadro:
Se escoge la ruta con menor distancia de acuerdo al cuadro anterior:
Método de búsqueda asterisco (A*)
La reducción al mínimo de f(n)= g(n) + h(n) combina las ventajas de la búsqueda por costo uniforme y la búsqueda ávara. Cuando se repiten los estados que se manejan y se garantiza que h(n) nunca haga una sobreestimación, existe una búsqueda asterisco.
g(n) = Costo de la ruta de partida al nodo n
h(n) = Costo de la ruta mas barata que va de n a la meta
f(n) = Costo estimado de la solución mas barata pasando por n
f(n)= g(n) + h(n)
Si aplicáramos el método Asterisco obtendríamos:
En donde g(n) = ruta inicial hasta n y h(n) = unidad establecida en el cuadro de Distancias en línea recta a Bucarest.