TIPOS DE
BUSQUEDA
QUE
NO CUENTAN CON INFORMACION F
PREFERENTE
POR AMPLITUD: Primero expande el nodo raíz y luego todos los
nodos generados por éste.
F"En
el caso de la búsqueda preferente por amplitud, el consumo de memoria
es un problema más serio que el del tiempo de ejecución".
F"En
general, los problemas de búsqueda de complejidad exponencial son irresolubles,
sino en las instancias más pequeñas"
DE
COSTO UNIFORME: se modifica la estrategia preferente por amplitud
en el sentido de expandir siempre el nodo de menor costo en el margen, en
vez del nodo de menor profundidad. Es seguro que la primera solución
encontrada será la más barata, siempre y cuando que el costo
de la ruta nunca disminuya conforme se avance por la ruta
PREFERENTE
POR PROFUNDAD: expande uno de los nodos que se encuentre en lo más
profundo del árbol. Solo si la búsqueda conduce a un callejón
sin salida, se revierte la búsqueda y se expanden losnodos de niveles
menos profundos.
-
VENTAJAS:
Lo bueno que el volumen de memoria es modesto ya que solo es necesario guardar
solo la ruta que vaya del nodo raíz al nodo hoja, junto con los nodos
restantes no expandidos, por cada nodo de la ruta.
-
DESVENTAJAS:
Pero tiene la desventaja que si se equivoca de ruta quede estancada y si
el árbol es muy pronfundo (o infitino), la búsqueda proseguirá
siempre en sentido descendente, sin mirar hacia atrás, aún
en el caso de que exista una solución próxima.
F"Cuando
hay árboles de búsqueda conprolongadas o infinitas profundidades
mácimas hay que evitar el empleo de la búsqueda preferente por
profundidad."n
LIMITADA
POR PROFUNDIDAD: Se impone un límite a la profundidad máxima,
con lo que se elimina el problema anterior. Para ello se usa un algoritmo
general de búsqueda con operadores que se informan constantemente de
la profundidad.
POR
PROFUNDIZACIÓN ITERATIVA: esquiva el tema de la elección
del mejor límite de la profundidad probando todos los límites
de profundidad posibles: la primera profunidad 0, luego 2, 3 ... n
F"Por
lo general, la profundización iterativa es el método idóneo
para aquellos casos donde el espacio de búsqueda es grande y se ignora
la profundidad de la solución."
BIDIRECCIONAL:
es una búsqueda simultánea que avanza a partir del estado inicial
y que retrocede a partir de la meta y que se detiene cuando ambas búsqueda
se encuentran en algún punto intermedio.
El
algoritmo define PREDECESORES, ya que una búsqueda hacia atrás
implica la sucesiva generación de predecesores a partir del nodo meta.
Por lo tanto es necesario contar con una manera eficiente de verificar cada
uno de los nodos nuevos para ver si ya están en el árbol de
búsqueda de la otra mitad de la búsqueda y tambien definir que
tipo de búsqueda se realizará en cada una de las mitades.
COMPARACION
DE TIPOS DE BUSQUEDA
Para
evitar los estados repetidos existen 3 formas
- No regresar
al estado del que acaba de llegar.
- No cree rutas
que contengan ciclos.
- No genere ningún
estado que se haya generado alguna vez anteriormente.
F"En
los Problemas que Satisfacen Restricciones (PSR), la prueba de la meta se descompone
en un conjunto de restricciones impuestas a las variables, en vez de funcionar
como una 'caja negra' ."