INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

El uso de información heurística en la resolución de problemas aparece en un artículo

de Simon y Newell (1958), pero la frase «búsqueda heurística» y el uso de las funciones

heurísticas que estiman la distancia al objetivo llegaron algo más tarde (Newell y

Ernst, 1965; Lin, 1965). Doran y Michie (1966) dirigieron muchos estudios experimentales

de búsqueda heurística aplicados a varios problemas, especialmente al 8-puzle

y 15-puzle. Aunque Doran y Michie llevaran a cabo un análisis teórico de la longitud

del camino y «penetrancia» (proporción entre la longitud del camino y el número total

de nodos examinados hasta el momento) en la búsqueda heurística, parecen haber ignorado

la información proporcionada por la longitud actual del camino. El algoritmo A*,

incorporando la longitud actual del camino en la búsqueda heurística, fue desarrollado

por Hart, Nilsson y Raphael (1968), con algunas correcciones posteriores (Hart et al.,

1972). Dechter y Pearl (1985) demostraron la eficiencia óptima de A*.

El artículo original de A* introdujo la condición de consistencia en funciones heurísticas.

La condición de monotonía fue introducida por Pohl (1977) como un sustituto

más sencillo, pero Pearl (1984) demostró que las dos eran equivalentes. Varios algoritmos

precedentes de A* utilizaron el equivalente de listas abiertas y cerradas; éstos incluyen

la búsqueda primero en anchura, primero en profundidad, y costo uniforme (Bellman,

1957; Dijkstra, 1959). El trabajo de Bellman en particular mostró la importancia de añadir

los costos de los caminos para simplificar los algoritmos de optimización.

Pohl (1970, 1977) fue el pionero en el estudio de la relación entre el error en las funciones

heurísticas y la complejidad en tiempo de A*. La demostración de que A* se ejecuta

en un tiempo lineal si el error de la función heurística está acotado por una constante

puede encontrarse en Pohl (1977) y en Gaschnig (1979). Pearl (1984) reforzó este re-

146 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO

sultado para permitir un crecimiento logarítmico en el error. El «factor de ramificación

eficaz», medida de la eficiencia de la búsqueda heurística, fue propuesto por Nilsson

(1971).

Hay muchas variaciones del algoritmo A*. Pohl (1973) propuso el uso del ponderado

dinámico, el cual utiliza una suma ponderada fw(n)
wgg(n)  whh(n) de la longitud

del camino actual y de la función heurística como una función de evaluación, más

que la suma sencilla f (n)
g(n)  h(n) que utilizó A*. Los pesos wg y wh se ajustan dinámicamente

con el progreso de la búsqueda. Se puede demostrar que el algoritmo de

Pohl es -admisible (es decir, garantiza encontrar las soluciones dentro de un factor 1 

de la solución óptima) donde  es un parámetro suministrado al algoritmo. La misma

propiedad es exhibida por el algoritmo A* (Pearl, 1984), el cual puede escoger cualquier

nodo de la franja tal que su f-costo esté dentro de un factor 1   del nodo de la

franja de f-costo más pequeño. La selección se puede hacer para minimizar el costo de

la búsqueda.

A* y otros algoritmos de búsqueda en espacio de estados están estrechamente relacionados

con las técnicas de ramificar-y-acotar ampliamente utilizadas en investigación

operativa (Lawler y Wood, 1966). Las relaciones entre la búsqueda en espacio de estados

y ramificar-y-acotar se han investigado en profundidad (Kumar y Kanal, 1983; Nau

et al., 1984; Kumas et al., 1988). Martelli y Montanari (1978) demostraron una conexión

entre la programación dinámica (véase el Capítulo 17) y cierto tipo de búsqueda

en espacio de estados. Kumar y Kanal (1988) intentan una «ambiciosa unificación» de

la búsqueda heurística, programación dinámica, y técnicas de ramifica-y-acotar bajo el

nombre de PDC (el «proceso de decisión compuesto»).

Como los computadores a finales de los años 1950 y principios de los años 1960 tenían

como máximo unas miles de palabras de memoria principal, la búsqueda heurística

con memoria-acotada fue un tema de investigación. El Grafo Atravesado (Doran y

Michie, 1966), uno de los programas de búsqueda más antiguos, compromete a un operador

después de realizar una búsqueda primero el mejor hasta el límite de memoria. A*PI

(Korf, 1985a, 1985b) fue el primero que usó un algoritmo de búsqueda heurística, óptima,

con memoria-acotada y de la que se han desarrollado un número grande de variantes.

Un análisis de la eficiencia de A*PI y de sus dificultades con las heurística

real-valoradas aparece en Patrick et al. (1992).

El BRPM (Korf, 1991, 1993) es realmente algo más complicado que el algoritmo

mostrado en la Figura 4.5, el cual está más cercano a un algoritmo, desarrollado independientemente,

llamado extensión iterativa, o EI (Russell, 1992). BRPM usa una cota

inferior y una cota superior; los dos algoritmos se comportan idénticamente con heurísticas

admisibles, pero BRPM expande nodos en orden primero el mejor hasta con una

heurística inadmisible. La idea de guardar la pista del mejor camino alternativo apareció

en la implementación elegante, en Prolog, de A* realizada por Bratko (1986) y en

el algoritmo DTA* (Russell y Wefald, 1991). El trabajo posterior también habló de espacios

de estado meta nivel y aprendizaje meta nivel.

El algoritmo A*M apareció en Chakrabarti et al. (1989). A*MS, o A*M simplificado,

surgió de una tentativa de implementación de A*M como un algoritmo de comparación

para IE (Russell, 1992). Kaindl y Khorsand (1994) han aplicado A*MS para

producir un algoritmo de búsqueda bidireccional considerablemente más rápido que los

BÚSQUEDA INFORMADA Y EXPLORACIÓN 147

EXTENSIÓN ITERATIVA

algoritmos anteriores. Korf y Zhang (2000) describen una aproximación divide-y-vencerás,

y Zhou y Hansen (2002) introducen una búsqueda A* en un grafo de memoriaacotada.

Korf (1995) revisa las técnicas de búsqueda de memoria-acotada.

La idea de que las heurísticas admisibles pueden obtenerse por relajación del problema

aparece en el trabajo seminal de Held y Karp (1970), quien utilizó la heurística

del mínimo-atravesando el árbol para resolver el PVC (véase el Ejercicio 4.8).

La automatización del proceso de relajación fue implementado con éxito por Prieditis

(1993), construido sobre el trabajo previo de Mostow (Mostow y Prieditis, 1989).

El uso del modelo de bases de datos para obtener heurísticas admisibles se debe a Gasser

(1995) y Culberson y Schaeffer (1998); el modelo de bases de datos disjuntas está

descrito por Korf y Felner (2002). La interpretación probabilística de las heurística fue

investigada en profundidad por Pearl (1984) y Hansson y Mayer (1989).

La fuente bibliográfica más comprensiva sobre heurísticas y algoritmos de búsqueda

heurísticos está en el texto Heuristics de Pearl (1984). Este libro cubre de una manera

especialmente buena la gran variedad de ramificaciones y variaciones de A*,

incluyendo demostraciones rigurosas de sus propiedades formales. Kanal y Kumar

(1988) presentan una antología de artículos importantes sobre la búsqueda heurística. Los

nuevos resultados sobre algoritmos de búsqueda aparecen con regularidad en la revista

Artificial Intelligence.

Las técnicas locales de búsqueda tienen una larga historia en matemáticas y en informática.

En efecto, el método de Newton-Raphson (Newton, 1671; Raphson, 1690)

puede verse como un método de búsqueda local muy eficiente para espacios continuos

en los cuales está disponible la información del gradiente. Brent (1973) es una referencia

clásica para algoritmos de optimización que no requieren tal información. La búsqueda

de haz, que hemos presentado como un algoritmo de búsqueda local, se originó

como una variante de anchura-acotada de la programación dinámica para el reconocimiento

de la voz en el sistema HARPY (Lowerre, 1976). En Pearl (1984, el Capítulo 5)

se analiza en profundidad un algoritmo relacionado.

El tema de la búsqueda local se ha fortalecido en los últimos años por los resultados

sorprendentemente buenos en problemas de satisfacción de grandes restricciones como

las n-reinas (Minton et al., 1992) y de razonamiento lógico (Selman et al., 1992) y por

la incorporación de aleatoriedad, múltiples búsquedas simultáneas, y otras mejoras. Este

renacimiento, de lo que Christos Papadimitriou ha llamado algoritmos de la «Nueva

Era», ha provocado también el interés entre los informáticos teóricos (Koutsoupias y Papadimitriou,

1992; Aldous y Vazirani, 1994). En el campo de la investigación operativa,

una variante de la ascensión de colinas, llamada búsqueda tabú, ha ganado popularidad

(Glover, 1989; Glover y Laguna, 1997). Realizado sobre modelos de memoria limitada

a corto plazo de los humanos, este algoritmo mantienen una lista tabú de k estados, previamente

visitados, que no pueden visitarse de nuevo; así se mejora la eficiencia cuando

se busca en grafos y además

...