Ia_intro_busqueda

BÚSQUEDA HEURÍSTICA

El objetivo de los métodos de búsqueda heurística es reducir el número de estados a generar durante la búsqueda. Utilizan en su estrategia de control las funciones de evaluación heurística, que llamaremos fev. Estas son una aplicación del conjunto de todos los estados posibles en

f:{estados}€ tal que f(estadoj)=nj

De esto se deduce que el valor de esta función dependeexclusivamente del estado que se está evaluando en un instante dado, es decir, para ese estado, el valor es función de la información disponible hasta ese momento sobre la búsqueda. Por regla general, el sistema experto almacenará esta información, refinándola mediante el aprendizaje.

Este valor numérico lo que hace es una ESTIMACIÓN de lo bueno que puede ser este estado para llegar a la meta.Esta estimación, que suele ser de coste pero que también puede ser de otro parámetro, cumple dos condiciones:

El valor mínimo (máximo) de esta función se ha de dar cuando se llega a la meta.

Se pretende que el valor calculado por esta función sea óptimo durante todo el camino. En este caso se dice que la fev es óptima, y por tanto nos va a dar la mejor solución (la óptima): la búsqueda sería lasimple ejecución de una secuencia de operadores. En un caso real no sabemos cual es el camino óptimo (de ahí la búsqueda) y lo que se hace es buscar, a lo largo del camino, el valor que más se acerque a este valor óptimo.
Un detalle que hay que tener en cuenta es que la fev, aunque utilice el conocimiento del dominio para el cálculo de su valor, forma parte del solucionador y por tanto forma partede las tareas de búsqueda; estas son, recordemos, las que usan los métodos de resolución para definir las tareas genéricas (no dependientes del dominio).

Encontrar una fev óptima podría ser fácil si no fuese por un detalle: su cálculo también tiene un coste asociado: puede darse el caso de que el coste del algoritmo con esa fev óptima sea mayor que el coste del algoritmo sin ella. Así pues,volvemos a encontrarnos en una situación en la que debemos llegar al compromiso entre el coste del algoritmo con fev y el coste sin ella.

Para identificar una fev, lo que hacemos es identificar todas las restricciones que ha de cumplir el problema. Luego simplificamos el modelo, es decir, relajamos estas restricciones (quitamos una o varias), de manera que se convierte en el mismo problema, pero menosestricto (subproblema más sencillo). Con esto lo que conseguimos es que la fev sea más simple, pero lo suficientemente útil para que nos estime lo bueno que sea el estado para llegar a la meta en función de las restantes restricciones. Para poder simplificar el modelo, el problema ha de poderse descomponer en subproblemas más sencillos.

Dado un problema, el valor calculado por una fev, queestima lo bueno que es el estado para llegar a la meta teniendo en cuenta todas las restricciones, va a ser mejor que el calculado por todas las fev que estimen lo mismo, pero cumpliendo solo algunas de estas restricciones. Cuanto más simple sea el modelo relajado, menor coste tendrá la fev, ya que esta es más simple, pero, en contrapartida, también dirigirá peor la búsqueda.

Una fev que solo midaun parámetro del problema, además de ser demasiado simple para estimar la distancia a la meta, también puede producir otros problemas:

Máximos (mínimos) locales.- Es un estado que es el estimado como mejor que todos los que le rodean, pero que se estima peor que alguno que está más alejado.

Altiplanicies o mesetas.- Son un conjunto de estados que tienen el mismo valor de fev, por lo que no setiene información de por donde seguir.
Estos inconvenientes se pueden solventar, aunque no definitivamente, con fevs que midan más de un parámetro y eligiendo adecuadamente el método de búsqueda.

1. MÉTODO DEL GRADIENTE O BÚSQUEDA EN ESCALADA
Es un método de búsqueda sin vuelta atrás (se convierte en un algoritmo voraz). Corresponde a la búsqueda en profundidad guiada por una fev. Al igual que su...