Estrategias de búsqueda informada

Estrategias de búsqueda informada.

Esta sección muestra cómo una estrategia de búsqueda informada puede encontrarsoluciones de una manera más eficiente que una estrategia no informada. Algunasestrategias son:

Búsqueda voraz primero el mejor.

La búsqueda voraz primero el mejor trata de expandir el nodo más cercano al obje­ tivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: ñn) = h(n). Veamos cómo trabaja para los problemas de encontrar una ruta en Rumania utilizando la heurística «Bstanriaoi linea recta que llamaremos hDUt Si el objetivo es Bucarest, tendremos que conocer las distancias en línea recta a Bucarest, que se muestran en la Figura 4.1. Por ejemplo, h[xJyEn(Arad)) = 366. Notemos que los valores de hDLRno pue­ den calcularse de la descripción de problema en sí mismo. Además, debemos tener una cierta cantidad de experiencia para saber que hnK está correlacionada con las distancias reales del camino y es, por lo tanto, una heurística útil.

Búsqueda primero el mejor es una BÚSQUEDA-GRAFO donde los nodos no expandidos de costo mínimo (según alguna medida) se escogen para la expansión. Los algoritmos primero el mejor utilizan típicamente una función heurística h(n) que estima el costo de una solución desde n.

h(n) = coste estimado del camino más barato desde el nodo n a un nodo objetivo.

Esta búsqueda es un caso en el cual se selecciona un nodo para la expansión basada en la función de evaluación h(n). Esta función devuelve un número que sirve para representar lo deseable o indeseable que sería la expansión de un nodo. Se expande primero aquel nodo que tiene mejor evaluación, se escoge el que parece ser el mejor aunque podría no serlo.

Búsqueda primero el mejor avara expande nodos con h(n) mínima. No es óptima, pero es a menudo eficiente.

Ejemplo: Un turista necesita viajar desde Sevilla hasta Almería recorriendo la menor distancia posible.

Búsqueda A*: minimizar el costo estimado total de la solución.

A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama bús­ queda A* (pronunciada «búsqueda A-estrella»). Evalúa los nodos combinando g{n), el coste para alcanzar el nodo, y h(n), el coste de ir al nodo objetivo: f[n) = g{n) + h{n) Ya que la g{rí) nos da el coste del camino desde el nodo inicio al nodo n, y la h(n) el cos­ te estimado del camino más barato desde n al objetivo, tenemos: f[tíj = coste más barato estimado de la solución a través de n.

Asi, si tratamos de encontrar la solución más barata, es razonable intentar primero el nodo con el valor más bajo de g(n) + h(rij. Resulta que esta estrategia es más que razonable: con tal de que la función heurística h(n) satisfaga ciertas condiciones, la búsqueda A* es tanto completa como óptima. La optimalidad de A* es sencilla de analizar si se usa con la Búsqueda-Árboles. En este caso, A* es óptima si h{ri) es una hanjsticaadmfeiHe es decir, con tal de que la h{rí) nunca sobrestime el coste de alcanzar el objetivo. Las heurísticas admisibles son por naturaleza optimistas, porque piensan que el coste de resolver el problema es me­ nor que el que es en realidad. Ya que g(rí) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la f\ri) nunca sobrestima el coste verdadero de una solución a través de n.

Búsqueda A* expande nodos con mínimo f(n)=g(n) + h(n).  A* es completa y optima, con tal que garanticemos que h(n) sea admisible (para BÚSQUEDA-ÁRBOL) o consistente (para BÚSQUEDA-GRAFO). La complejidad en espacio de A* es todavía prohibitiva.

Ejemplo: Un cliente de un almacén solo dispone de dinero en efectivo para comprar un producto al día. Este cliente necesita comprar (3) tres productos: Un producto tipo A, uno tipo B y uno tipo C. Comprará uno de estos productos el primer día, otro el segundo día y por último otro, el tercero. El almacén tiene las siguientes existencias:  Dos clases de productos tipo A: El producto A1 con un precio de 200.000 pesos y el producto A2 con un precio de 220.000. El cliente comprará un producto A1 o un producto A2, ya que solo necesita un producto tipo A.  Productos tipo B, a un precio de 150.000.  Productos tipo C, a un precio de 100.000.   Además el cliente puede aprovechar de los siguientes descuentos: Si alguno de los días anteriores compró un producto de clase A2, tendrá un descuento del 20% en los productos que compre a partir de ese día.  Si alguno de los días anteriores compró un producto tipo B, tendrá un descuento del 10% en los productos que compre a partir de ese día.  Se pide determinar, haciendo uso del algoritmo A* Primero el mejor, en qué orden debe comprar los tres productos para que el coste total que le suponga la compra sea mínimo. Se considera que el descuento sobre el precio de cualquier producto puede llegar (aunque solo llega en ciertas ocasiones) como máximo hasta el 30%, por lo tanto el precio mínimo de un producto podría ser el 70% de su precio real.

Búsqueda heurística con memoria acotada.

La forma más simple de reducir la exigencia de memoria para A* es adaptar la idea de profundizar iterativamente al contexto de búsqueda heurística, resultando así el algorit­ mo A* de profundidad iterativa (A*PQ. La diferencia principal entre A*PI y la profun­ didad iterativa estándar es que el corte utilizado es el /coste (g + h) más que la profundidad; en cada iteración, el valor del corte es el /coste más pequeño de cualquier nodo que excedió el corte de la iteración anterior. A*PI es práctico para muchos pro­ blemas con costos unidad y evita el trabajo asociado con el mantenimiento de una cola ordenada de nodos. Lamentablemente, esto sufre de las mismas dificultades con costos de valores reales como hace la versión iterativa de búsqueda de coste uniforme descri­ ta en el Ejercicio 3.11. Esta sección brevemente examina dos algoritmos más recientes con memoria acotada, llamados BRPM y A*M. La búsqueda recuráva dd primero mejor (BRPM) es un algoritmo sencillo re­ cursivo que intenta imitar la operación de la búsqueda primero el mejor estándar, pero utilizando sólo un espacio lineal. En la Figura 4.5 se muestra el algoritmo. Su estructu­ ra es similar a la búsqueda primero en profundidad recursiva, pero más que seguir in­ definidamente hacia abajo el camino actual, mantiene la pista del /valor del mejor camino alternativo disponible desde cualquier antepasado del nodo actual. Si el nodo ac­ tual excede este límite, la recursividad vuelve atrás al camino alternativo. Como la re- cursividad vuelve atrás, la BRPM sustituye los /valores de cada nodo a lo largo del camino con el mejor /valor de su hijo. De este modo, la BRPM recuerda el /valor de la mejor hoja en el subárbol olvidado y por lo tanto puede decidir si merece la pena ex­ pandir el subárbol más tarde.