Algoritmos de búsqueda local y problemas de optimización

Algoritmos de búsqueda local y problemas de optimización.

Los algoritmos de búsqueda que hemos visto hasta ahora se diseñan para explorar sistemáticamente espacios de búsqueda. Esta forma sistemática se alcanza manteniendo uno o más caminos en memoria y registrando qué alternativas se han explorado en cada punto a lo largo del camino y cuáles no. Cuando se encuentra un objetivo, el camino a ese objetivo también constituye una solución al problema.

En muchos problemas, sin embargo, el camino al objetivo es irrelevante. Por ejemplo, en el problema de las 8 -reinas [véase la página 74), lo que importa es la configuración final de las reinas, no el orden en las cuales se añaden. Esta clase de problemas incluyen muchas aplicaciones importantes como diseño de circuitos integrados, disposición del suelo de una fábrica, programación del trabajo en tiendas, programación automática, optimización de redes de telecomunicaciones, dirigir un vehículo, y la gestión de carteras.

Si no importa el camino al objetivo, podemos considerar una clase diferente de algoritmos que no se preocupen en absoluto de los caminos. Los algoritmos de búsqueda local funcionan con un solo estado actual (más que múltiples caminos) y generalmente se mueve sólo a los vecinos del estado. Típicamente, los caminos seguidos por la búsqueda no se retienen. Aunque los algoritmos de búsqueda local no son sistemáticos, tienen dos ventajas claves: (1 ) usan muy poca memoria (por lo general una cantidad constante); y (2 ) pueden encontrar a menudo soluciones razonables en espacios de estados grandes o infinitos (continuos) para los cuales son inadecuados los algoritmos sistemáticos.

Búsqueda de ascensión de colinas

En la Figura 4.11 se muestra el algoritmo de búsqueda de ascoKión de colinas Es simplemente un bucle que continuamente se mueve en dirección del valor creciente, es decir, cuesta arriba. Termina cuando alcanza «un pico» en donde ningún vecino tiene un valor más alto. El algoritmo no mantiene un árbol de búsqueda, sino una estructura de datos del nodo actual que necesita sólo el registro del estado y su valor de función objetivo.

La ascensión de colinas no mira delante más allá de los vecinos inmediatos del estado actual. Se parece a lo que hacemos cuando tratamos de encontrar la cumbre del Everest en una niebla mientras sufrimos amnesia. Para ilustrar la ascensión de colinas, usaremos «1 p n b lo m de las 8-ronas introducido en la página 74. Los algoritmos de búsqueda local típicamente usan una fimmlafimción por columna.

La función sucesor devuelve todos los estados posibles generados moviendo una reina a otro cuadrado en la misma columna (entonces cada estado tiene 8 x 7 = 56 sucesores). La función de costo heurística h es el número de pares de reinas que se atacan la una a la otra, directa o indirectamente. El mínimo global de esta función es cero, que ocurre sólo en soluciones perfectas. La Figura 4.12(a) muestra un estado con h = 17.

La figura también muestra los valores de todos sus sucesores, con los mejores sucesores

que tienen h = 12. Los algoritmos de ascensión de colinas eligen típicamente al azar entre el conjunto de los mejores sucesores, si hay más de uno.