TIPOS DE BUSQUEDA F
QUE CUENTAN CON INFORMACION
|
|
|
|
|
BUSQUEDA PREFERENTE POR LO MEJOR:
Los nodos se ordenan de manera tal que se expande primero aquel con mejor actuación. Se escoge el nodo que parece ser el mejor, según lo aconsejado por la función de evaluación, si ésta es onmisciente, el nodo verdaderamente será el mejor
F"Para enfocar la búsqueda, en tal medida debe figurar algún tipo de cálculo del costo de ruta que va de un estado al estado más cercano a la meta.
F"Una de las más sencillas estrategias en la búsqueda preferente por lo mejor, consiste en reducir al múnimoo el costo estimado para lograr una meta."
El nodo cuyo estado se considere serl el más cercano al estado de la meta es el que siempre se expande primero. Existe una función que permite el cálculo de estimación del costo que implica llegar a una meta desde un estado determinado y es la FUNCION HEURISTICA (h). Por ende aquella búsqueda que use esta función para escoger cuál es el siguiente nodo que se va a expandir es denominada Búsqueda Avara. Los algoritmos por avaricie tienen un desempeño bastante bueno, tienden a encontrar soluciones rápidamente, aunque no siempre es la óptima. Para eso se necesita un análisis más cuidadoso de las opciones a largo plazo y no sólo considerar la mejor solución más inmediata. Esta permite reducir al mínimo el costo de la meta, por lo tanto también se reduce el tiempo de búsqueda.
Una buena función heurística en problemas de determinación de ruta, corresponde a la distancia en línea recta a la meta.
F"Si h es aceptable, f(n) nunca sobreestimará el costo real de la mejor solución que pase por n."
Sera aquella que utilice f como la función de evaluación y una función h aceptable.
A lo largo de las rutas originadas en la raíz el costo f nunca disminuye. Puesto que A* expande el nodo hoja que tienen la f más baja, se concluye que una búsqueda A* se extiende desde el nodo de partida y va añadiendo nodos en bandas concentricas cuyo valor f también va aumentando.
En el caso de la búsqueda por costo uniforme(A* con h=0), las bandas se extienden en forma "circular" en torno del estado de partida. Cuanto más precisas sean las heurísticas las bandas se tienden al estado meta y se concetran más apretadamente en torno de la ruta óptima. A* es óptimamente eficiente para cualquier función heurística; ningún otro algoritmo óptimo garantiza que expandirá menos nodos que A*.
Como dificultad se puede decir que para la generalidad de problemas, la cantidad de nodos que están dentro del espacio de búsqueda en el controno de la meta sigue siendo exponencial a lo largo de toda la solución. El error es proporcional al costo de la ruta y el crecimiento exponencial resultante al final rebasa la capacidad de cualquier computadora. Se queda sin memoria mucho antes de agotar el tiempo.
F"Por tanto, siempre conviene más emplear una función heurística con valores más altos, siempre y cuando no de lugar a una sobreestimación."
A los problemas que se le imponen menos restricciones se les llama problemas relajados.
F"Es frecuente que el costo de la solución de un problema relajado constituya una buena heurística del problema original."
Una forma de inventar una buena heurística es utilizando información estadística, para ello se utiliza información probabilística, aunque se renuncia a la garantía de adminisibilidad, por otra parte se expandirán menos nodos en promedio.
LIMITADA POR LA CAPACIDAD DE LA MEMORIA
F"Lo primero que hay que ceder es la memoria disponible."
BUSQUEDA A* POR PROFUNDIZACION ITERATIVA (A*PI)
La profundización iterativa reduce el consumo de memoria. En este algoritmo cada iteración es una búsqueda preferente por profundidad que se modifica para utilizar un límite de costo f en vez de un límite por profundidad. Así es como se expanden todos lo nodos que están dentro del contorno del costo f actual y se echa un vistazo al contorno para determinar en donde se encuentra el siguiente contorno con cada iteración.
Este es un método completo y óptimo, con las mismas ventajas y desventajas que A*, pero solo necesita de un espacioo proporcional con la ruta más larga que explore.
La complejidad temporal depende fundamentalmente de l cantidad de distintos valores que adopta la función heurística. Pasa sólo a través de 2 o 3 iteraciones y su eficiencia es semejante a A*.
Tiene problemas en los dominios más complejos, entre una iteración y otra, se guarda solo un número, el del límite actual del costo f, pero no puede recordar su historia entonces está condenada a repetirla.
BUSQUEDA ACOTADA POR MEMORIA SIMPLIFICADA (A*SRM)
Este emplea toda la capacidad de memoria disponible para efectuar la búsqueda, lo que permite mejorar la eficiencia en la misma. Por lo general, es más conveniente recordar un nodo que tener que regeneralo cuando se le necesite. Es así como este método Evita estados repetidos, es COMPLETO si la memoria disponible tiene la capacidad suficiente para guardar la ruta de solución más cercana; es OPTIMA.
En síntesis, si se dispone de suficiente memoria para todo el árbol de búsqieda, resultará óptimamente eficiente.
ALGORITMOS DE MEJORAMIENTO ITERATIVO
F"La idea básica consiste en empezar con una configuración completa y efectuar modificaciones para mejorar su calidad."
Estos algoritmos se fijan sólo en el estado actual, sin mirar más allá de los vecinos inmediatos de tal estado. Es el mejor método en problemas difíciles de carácter práctico.
Se esfuerzan por efectuar cambios que permitan mejorar el estado actual.
El algoritmo se trata de un bucle que constantemente se despalza en la dirección de un valor ascendente, no se mantiene un árblo de búsqueda, por lo tanto la estructura de los datos del nodo ´solo tiene que registrar el estado y su evalución.. llamada VALOR. Cuando existe más de un sucesor idóneo que elefir, éste selecciona uno de ellos al azar.
DESVENTAJAS:
Puede que alcance un máximo local y siendo así el algoritmo para. Si se encuentra con una planicie, la búsqueda hará una elección al azar. En el caso de encontrarse con un risco pronunciado puede que la búsqueda oscile de un lado al otro, obteniendo muy poco avance.
El éxito del ascenso de cima depende en gran medida de la forma que tenga la "superficie" del espacio de estados, solo si hay unos cuantos máximos locales, el ascenso de cima con reinicio aleatorio encontratá la solución rápidamente.
En vez de empezar otra vez al azar luego de quedarse atorado en un máximo local, sería coveniente descender unos cuantos pasos y así escapar del máximo local en cuestión. Así funciona este método ya que en vez de optar por la mejor acción, se escoge una al azar; si mediante la acción se logra mejorar la situación.. se Ejecuta.