La decisión de expandir un nodo del márgen se toma a partir de una funcion de evaluación, la cual produce un número que representa lo deseable (o indeseable) que sería la expansión del mismo. Cuando los nodos se ordenan de manera tal que se expande primero aquel con mejor evaluación, entonces se trata de una estrategia denominada búsqueda preferente por lo mejor. Sin embargo, si en verdad fuese posible expandir desde un principio el mejor nodo, en realidad no se trataría de una búsqueda; sería encaminarse directamente a la meta
Una
estrategia simple consiste en reducir al mínimo el costo estimado para lograr
una meta. Aunque es posible estimar el costo que implica llegar a una meta desde
un estado determinado, no es posible hacerlo con precisión. La función que se
utiliza para calcular tales estimados de costo se conoce como función heurística.
A
la búsqueda que utiliza una función heurística para escoger qué nodo se
expandirá es denominada “búsqueda avara”.
La
búsqueda avara y la preferente por profundidad se asemejan por su indicación a
utilizar una sola ruta hasta llegar a la
meta, pero se atorarán cuando se topen con un callejón sin salida. Esta búsqueda
no es óptima y es incompleta.
Esta
búsqueda es una combinación de la búsqueda avara con la búsqueda por costo
uniforme. Lo que se hace es combinar las dos funciones de evaluación mediante
una suma: f(n) = g(n) + h(n) donde g(n) calcula es costo de la ruta que va desde
el nodo de partida al nodo n, y h(n) es el costo estimado de la ruta más barata
que va de n a la meta, tenemos que f(n) es el costo estimado de la solución
más barata pasando por n. Lo interesante de esta estrategia es que no solo es razonable, sino
que se puede demostrar que es completa y óptima.
Una
forma de caracterizar la calidad de una heurística es mediante el factor de
ramificación efectiva b*. Si la cantidad total de nodos expadida por A* para un
problema determinado es N, y la profundidad de la solución es d, entonces b* es
el factor de ramificación que deberá tener un arbol uniforme de profundidad d
para que pueda contener N nodos.
Si llamamos problemas relajados a aquellos en que se imponen menos restricciones entonces podemos decir que es frecuente que el costo de la solución de un problema relajado constituya una buena heurística del programa original.
Una forma de inventar una buena heurística es utilizando información estadística. Para ello se efectúa una búsqueda a través de diversos problemas de adiestramiento y se obtienen las estadísticas correspondientes. Muchas veces existe la posibilidad de tomar rasgos de un estado que forman parte de su función de evaluación heurística. Normalmente se supone a la función de evaluación como una combinación lineal de los valores de los rasgos. Otro factor no considerado hasta el momento es el costo de búsqueda que implica la aplicación de una función heurística a un nodo. Si la complejidad de la heurística es tal que el cálculo de su valor para un nodo tarda tanto como la expansión de cientos de nodos, habrá que hacer una reconsideración. Una buena función heurística es aquella que es eficiente así como precisa.
A pesar de los inteligentes algoritmos de búsqueda inventados hasta ahora, la realidad es algunos problemas son en sí mismos muy difíciles de resolver. Al tratar de enfrentarlos, lo primero que hay que ceder es la memoria disponible.
Anteriormente
hemos mostrado lo útil que es la profundización iterativa como técnica para
reducir el consumo de memoria. Ahora probaremos nuevamente este método,
convirtiendo la búsqueda A* en una A* por profundización iterativa o A*PI. En
este algoritmo, cada iteración es una búsqueda preferente por profundidad.
Esta se modifica para utilizar un límite de costo f en vez de un límite de
profundidad. De esta forma, en cada iteración se expanden todos los nodos que
están dentro del contorno del costo f actual, y se echa un vistazo al contorno
para determinar en dónde se encuentra el siguiente contorno. Una vez concluída
una búsqueda dentro de un contorno determinado, se procede a efectuar una nueva
iteración utilizando un nuevo costo f para el contorno siguiente.
En
algunos espacios de problemas, las dificultades de A*PI tienen que ver con el
empleo de muy poca memoria. Entre una iteración y otra, se guarda sólo un número,
el del límite actual del costo f. Puesto que no puede recordar su historia,
A*PI está condenada a repetirla.
Aquí
explicaremos en qué consiste el algoritmo A*SRM (A* acotada por memoria
simplificada), el cual emplea toda la capacidad de memoria disponible para
efectuar una búsqueda.
A*SRM
se caracteriza por lo siguiente:
Hará uso de
toda la memoria que pueda disponer.
En la medida
que se lo facilite la memoria, evitará los estados repetidos.
Es
completa si
la memoria disponible tiene capacidad suficiente para guardar la ruta de solución mas cercana.
Es óptima si
dispone de suficiente memoria para guardar la ruta de solución óptima mas
cercana. De lo contrario produce la mejor solución que sea posible obtener con
la memoria disponible.
Si se dispone
de suficiente memoria para todo el árbol de búsqueda, ésta resultará óptimamente
eficiente.
El
diseño de A*SRM es simple. Si tiene que generar un sucesor, pero ya no hay
memoria, es necesario que se haga espacio en la lista de espera. Para ello,
excluir un nodo de la lista de espera; a estos nodos excluidos se les denomina
nodos olvidados. Prefiere así excluir nodos que no tienen futuro, es decir, con
un elevado costo f. Para evitar el regreso a explotar subárboles excluídos de
la memoria, conserva la información de los nodos ancestros sobre la calidad de
la mejor ruta en el subárbol olvidado. Así, sólo tendrá que regenerar el subárbol
si las demás rutas ofrecen peores perspectivas que la ruta que se ha olvidado.
Cuando cuenta con la suficiente memoria, A*SRM resuelve problemas mucho más dificiles que A* sin incurrir en excesos considerables en cuanto a generación de nodos adicionales. Su desempeño es bastante bueno en problemas que tienen espacios de estado que guardan estrecha relación entre sí y en heurísticas con valores reales, problemas que resultan difíciles para A*PI. Sin embargo, en el caso de problemas especialmente difíciles, con frecuencia A*SRM se ve forzada a alternar continuamente entre una y otra de las rutas de solución propuestas. De esta forma, la cantidad adicional de tiempo necesaria en la regeneración repetida de los mismos nodos trae como consecuencia que aquellos problemas que practicamente serían solubles usando A*, son irresolubles para A*SRM. Si bien no existe una teoría que explique el compromiso que existe entre tiempo y memoria, al parecer es un problema insoslayable.
Hay cierto tipo de problemas en los cuales la información necesaria para encontrar una solución se encuentra en la misma descripción del estado. En estos casos, los algoritmos de mejoramiento iterativo constituyen el método de solución más práctico. Estos algritmos se dividen en dos clases principales: algoritmos de ascenso de cima y algoritmos de endurecimiento simulado.
Se trata de un bucle que constantemente se desplaza en la dirección de un valor ascendente. Como el algoritmo no mantiene un árbol de búsqueda, la estructura de datos del nodo sólo tiene que registrar el estado y su evaluación, denominado valor. Una mejora importante consiste en que cuando existe más de un sucesor idóneo que escoger, el algoritmo selecciona uno de ellos al azar. Esta política tiene tres desventajas:
Máximos locales: es una cima cuya altura es inferior a la cima más alta de todo el espacio de estados. Una vez que ha alcanzado un máximo local, el algoritmo para, no obstante que todavía la solución diste de ser satisfactoria.
Planicie: las planicies son áreas del espacio de estados en donde la función de evaluación básicamente es plana. La búsqueda realizará un paseo al azar.
Riscos: las laderas de algunos riscos tienen pendientes muy pronunciadas, por lo que es fácil para una búsqueda llegar a la cima del risco; sin embargo, puede suceder que la pendiente de tal cima se aproxime demasiado gradualmente a un pico. A menos que existan operadores que se desplacen por la cima del risco, la búsqueda oscilará de un lado a otro, obteniendo muy poco avance.
En
vez de empezar otra vez al azar luego de quedarse atorado en un máximo local,
sería conveniente descender unos cuantos pasos y así escapar del máximo local
en cuestión. En esto consiste el endurecimiento simulado. El bucle más interno
de la fusión simulada es bastante similar al del ascenso de cima. 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. De lo contrario, el algoritmo realizará la acción con cierta
probabilidad inferior a 1. La probabilidad disminuye exponencialmente con lo
“malo” de la acción.
El
endurecimiento simulado se utilizó ampliamente por primera vez en la resolución
de los problemas de distribución de areas de la VLSI, a pirncipios de los 80.
Desde entonces se ha utilizado ampliamente en la programación de actividedes
fabriles y otras tareas de optimización a gran escala.
Los
problemas que satisfacen restricciones (PSR) se pueden resolver recurriendo a métodos
de mejoramiento iterativo: primero se asignan valores a todas las variables, y
luego se aplican operadores de modificación con el fin de conducir la
configuración hacia una solución. Lo que hacen los operadores de modificación
es, sencillamente, asignar un valor distinto a una variable.
Algoritmos
que resuelven PSR comunmente se denominan métodos de reparación heurística,
puesto que reparan las incosistencias presentes en una configuración dada. En
la elección del nuevo valor de una variable, la heurística más obvia
consistiría en elegir el valor que produzca el mínimo de conflictos con otras
variables: la heurística del mínimo de conflictos.
Este método se ha utilizado, por ejemplo, para programar las observaciones del telescopio espacial Hubble, lo que ha permitido reducir el tiempo necesario para programar una semana de observaciones, de tres semanas a aproximadamente diez minutos.
