Búsqueda limitada por la capacidad de memoria
Métodos de búsqueda respaldados con información: Al contar con información sobre un espacio de estados evitan las búsquedas ciegas.
Búsqueda
preferente por lo mejor
El
conocimiento en que se apoya esta decisión es obtenido desde una función de
evaluación, la cual produce un número que sirve para representar lo deseable.
Cuando los nodos se ordenan de manera tal que se expande primero aquél con
mejor evaluación, entonces se trata de una estrategia denominada búsqueda
preferente por lo mejor.
Se escoge
el nodo que parece ser el mejor, según lo aconsejado por la función de
evaluación. Si ésta es omnisciente, el nodo verdaderamente será el mejor. El
objetivo de esta búsqueda es encontrar soluciones de bajo costo, se utiliza
alguna medida estimada del costo de la solución y se hacen esfuerzos por
reducir esta medida al mínimo. Esta medida no es un búsqueda directa dirigida
a la meta. Para enfocar la búsqueda, en tal medida debe figurar algún tipo del
cálculo del costo de ruta que va de un estado al estado más cercano de la
meta.
Búsqueda Avara
Una de las más sencillas estrategias en la búsqueda preferente por lo mejor consiste en reducir al mínimo el costo estimado para lograr una meta. El nodo cuyo estado se considere el más cercano al estado de la meta es el que siempre se expande primero. La función que se utiliza para calcular tales estimados de costo se conoce como función heurística:
Aquella búsqueda preferente por lo mejor que utiliza h para escoger cuál es el siguiente nodo que se va a expandir es denominada búsqueda avara. El único requisito es que h(n) = 0 cuando n es una meta. Las funciones heurísticas se refieren a problemas específicos, ejemplo la determinación de la ruta que vaya de Arad a Bucarest (Rumania). Una buena función heurística en problemas de determinación de ruta como la anterior corresponde a la distancia en línea recta a la meta.
Para
calcular los valores de hdlr es necesario contar con las coordenadas
de las ciudades de Rumania. Es útil porque una carretera que va de A a B por lo
general tiende a dirigirse más o menos la dirección correcta. Información
como esta es el tipo de información adicional que permite a la heurística
contribuir con la reducción del costo de búsqueda. Los algoritmos por avaricia
tienen un desempeño bastante bueno. Es posible que en una búsqueda avara se
equivoquen las pistas si no se tiene la precaución de detectar estados
repetidos.
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 topen con un
callejón sin salida. Sus deficiencias son las mismas que las de la búsqueda
preferente por profundidad: no es óptima; es incompleta y nunca puede regresar
a probar otras posibilidades.
Búsqueda A*
Esta estrategia
se basa en reducir al mínimo el costo de ruta total. Utiliza dos tipos de búsqueda
combinados: la búsqueda avara y la búsqueda por costo uniforme: f(n) = g(n) +
h(n)
Toma las ventajas de las
dos.
Dado
que con g(n) se calcula el costo de la ruta que va del 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) = costo estimado de la solución más barata
pasando por n.
Lo
interesante de esta estrategia es que es completa y óptima dada una sencilla
restricción de la función h, la restricción consiste en escoger una función
h que nunca sobreestima el costo que implica alcanzar la meta. A tal h se lo
conoce como heurística admisible.
A la búsqueda
preferente por lo mejor, en la que se utiliza f como la función de evaluación
y una función h aceptable se la conoce como búsqueda A*.
Su
complejidad espacial es todavía prohibitiva
Es importante
nombrar que a lo largo de las rutas originadas en la raíz el costo de la función
f nunca disminuye. Esto no es accidental sino que se cumple en casi todas las
heurísticas aceptables.
Monotonicidad:
Es una propiedad que tienen todas las funciones heurísticas. Esta se cumple
cuando la función f crece a medida que se va avanzando en el árbol de búsqueda
por los diferentes nodos, partiendo de la raiz.
Ruta máxima:
Ecuación que define el costo de un nodo como el máximo entre el costo propio
del nodo y el costo de su padre. El utilizar esta ecuación garantiza que f
nunca decrecerá a lo largo de una trayectoria originada en la raíz.
Contornos:
Si f nunca disminuye a través de una ruta que parte de la raíz,
conceptualmente es posible dibujar contornos en el espacio de estados.
Optimamente
eficiente: No existe ningún otro algoritmo óptimo que garantiza que
expandirá menos nodos que A*.
El problema de
la ocho placas ayuda a aclarar la naturaleza de la heurística en general. Se
trata en deslizar las placas horizontal o verticalmente y colocarlas en el
espacio que está vacío, hasta que la configuración de partida sea igual a la
de meta.
Para
encontrar las soluciones más breves hay que tener una función heurística que
nunca sobreestime la cantidad de pasos necesarios para alcanzar la meta:
H1:
cantidad de placas que están en lugar incorrecto.
H2:
suma de las distancias que separa a las placas de sus posiciones meta (distancia
de Manhattan)
Existe la
imposibilidad de obtener una que sea evidentemente “la mejor”. Si para un
problema determinado existe un grupo de heurísticas aceptables, h1,...hm y si
ninguna de ellas domina a las otras, ¿cuál es la que se debe elegir?
Utilizando
información estadística.
En muchas
ocasiones existe la posibilidad de tomar rasgos de un estado que forman parte de
su función de evaluación heurística, aún cuando no sea fácil determinar en
qué consiste tal contribución.
Por
ejemplo, en el ajedrez la meta es dar jaque mate al oponente, y entre los rasgos
característicos figuran la cantidad de piezas de cada tipo que pertenecen a
cada lado, la cantidad de ellas que reciben el ataque de los contrincantes, etc.
Se supone a
la función de evaluación como una combinación lineal de los valores de los
rasgos.
Supóngase un
mapa y la meta es iluminar los países con alguno de los tres colores posibles,
pero con la restricción que países limítrofes no tengan el mismo color.
La idea
intuitiva de resolverlos sin realizar una búsqueda se denomina heurística de
la variable más restringida. Si se realiza una verificación anticipada,
en cada punto de la búsqueda, aquella variable que tenga el mínimo de valores
posibles es la que se escoge para que se le asigne un valor.
La heurística
de la variable más restrictiva es igualmente efectiva. Se intenta la
reducción del factor de ramificación en futuras elecciones asignando un valor
a la variable que está relacionada con el mayor número de restricciones de
otras variables sin valor asignado.
Una vez seleccionada una variable, hay que asignarle un valor. Se denomina heurística del valor menos restrictivo: escoger un valor que gobierne al mínimo número de valores en variables relacionada mediante restricciones con la variable actual.
Búsqueda
limitada por la capacidad de memoria
Algoritmos creados para
conservar la memoria:
Búsqueda A* por
profundización iterativa (A*PI):
Cada
iteración es una búsqueda preferente por profundidad. Se modifica para
utilizar un límite de costo f en vez de un límite de profundidad. En cada
iteración se expanden todos los nodos que están dentro del contorno del costo
f actual, y se hecha un vistazo al contorno para determinar en dónde se
encuentra el siguiente contorno. Una vez concluida 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.
Solo
necesita un espacio de memoria proporcional con la ruta más larga que explore.
En el caso
del agente viajero, por ejemplo, el valor heurístico cambia por cada estado.
A*SRM:
En el caso de la
búsqueda A*PI entre una iteración y la siguiente, se guarda el valor del límite
actual del costo f; entonces no puede recordad su historia y está condenada a
repetirla.
En el caso
de A*SRM (A* acotada por memoria simplificada), se emplea toda la memoria
disponible para efectuar una búsqueda.
Se
caracteriza por lo siguiente:
Uso de toda la memoria disponible.
En la medida que lo facilite la memoria, salto de los estados
repetidos.
Es completo si dispone de suficiente memoria como para guardar la
solución más cercana.
Es óptima si dispone de la memoria para guardar la ruta solución óptina
más cercana. Sino produce la mejor solución disponible con esa capacidad
de memoria.
Si se dispone la capacidad de memoria para todo el árbol de búsqueda,
entonces resultará optimizante eficiente.
Algoritmos de
mejoramiento iterativo.
La idea básica
consiste en empezar con una configuración completa y efectuar modificaciones
para mejorar su calidad. La mejor manera de hacerse con una idea de lo que son
los algoritmos de mejoramiento iterativo es imaginar que todos los estados están
sobre la superficie de un paisaje. La altura de cada uno de los puntos de éste
corresponde a la función de evaluación del estado de ese punto. El objetivo de
una mejora iterativa consiste en explorar el paisaje en busca de las cimas más
altas,es decir, de las soluciones óptimas.
Normalmente
los algoritmos de mejoramiento iterativo se fijan sólo en el estado actual,sin
mirar más allá de los vecinos inmediatos de tal estado.
Estos
algoritmos se dividen en dos clases principales:
Ascenso
de cima, que se esfuerza por efectuar cambios que permitan mejorar el estado
actual.
Endurecimiento
simulado, que a veces con los cambios que producen sólo se logran empeorar
las cosas, por lo menos temporalmente.
Simplemente 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.
Esta
sencilla política tiene tres bien conocidas desventajas:
Máximas locales: un máximo local, contrariamente a un máximo
global, 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.
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.
El algoritmo llega a un punto más alla del cual no se logra ningún avance.
Lo que se hace mediante el ascenso de cima con
reinicio aleatorio:efectúa una serie de búsquedas de ascenso de cima desde
estados iniciales generados aleatoriamente , hasta parar o cuando no se logra
ningún avance significativo.Se guarda el mejor resultado que hasta un momento
dado se haya obtenido en las diversas búsquedas;puede usar un número fijo de
iteraciones,o puede continuar hasta que el mejor de los resultados almacenados
no haya sido mejorado para cierta cantidad de iteraciones.
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. 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 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.
Para
determinar la probabilidad se utiliza un segundo parámetro, T. Cuando los
valores de T son elevados, hay más probabilidad de que se acepten las acciones
“malas”.Conforme T tiende a cero, es menos probable su aceptación, hasta
que se comporte más o menos como el ascenso de cima.
Los problemas
que satisfacen restricciones se pueden resolver recurriendo a métodos de
mejoramiento iterativo: se asignan valores a todas las variables y se aplican
operadores de modificación con el fin de conducir la configuración hacia una
solución.
Algoritmos
que resuelven PSR se llaman métodos de reparación heurística, ya que reparan
las inconsistencias 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
resulta asombrosamente eficiente en muchos PSR:
Resolver el problema
de un millón de reinas utilizando en promedio 50 pasos.
Programar las
observaciones del telescopio Hubble, reducir el tiempo para programar una
semana de observaciones, de tres semanas a aproximadamente diez minutos.
En esta sección no solo tenemos la complejidad en la elección de un método de
búsqueda que sea el mas conveniente para nuestro problema sino también la
confección de una heurística que sea eficiente. Esta desempeñara un papel muy
importante en los algoritmos de búsqueda respaldados con información. El éxito
dependerá de que tan útil y correcto sea el valor devuelto. Con esto quiero
decir que podemos haber escogido el método mas eficiente pero si la heurística
falla no podremos arribar a la solución.