BENEMERITA UNIVERSIDAD AUTONOMA DE PUEBLA
MATERIA: Inteligencia Artificial
TEMA: Búsqueda Preferente Por Profundidad
ESTUDIANTES:
Castañeda luna Isaac
González Escamilla Martin
Falfan Guarneros José Raúl
PROFESOR: Alfonso Garcés Báez
1
DEFINICION BUSQUEDA PREFERENTE
POR PROFUNDIDAD
Este método representa una forma sencilla de hallar una
trayectoria, consiste en tomar uno de los hijos en cada
nodo que se visita y avanza a partir de ese hijo. Otras
alternativas del mismo nivel se ignoran por completo, en
tanto haya posibilidades de alcanzar la meta mediante la
selección original.
2
DESVENTAJAS
•La desventaja de la búsqueda preferente por profundidad es la
posibilidad de que se quede estancada al avanzar por una ruta
equivocada. En muchos problemas, los árboles de búsqueda son muy
profundos, o hasta infinitos, por lo que en una búsqueda preferente
por profundidad nunca será posible recuperarse de alguna
desafortunada opción en uno de los nodos que están cerca de la parte
superior del árbol. La búsqueda proseguirá
•Siempre en sentido descendente, sin hacia atrás, aún en el caso de
que exista una solución próxima
•Por lo tanto, o se queda atorada en un bucle infinito y nunca es
posible regresar al encuentro de una solución, o a la larga encontrará
una ruta de solución más larga que la solución óptima.
3
Algoritmo de Búsqueda Preferente
Por Profundidad
• Para llevar a cabo una búsqueda en profundidad,
1. Inserte en una pila el elemento raíz (nodo de partida)
2. Hasta que el elemento tope sea el nodo meta, o se
vacié la pila
1. Si nodo tope tiene hijos, insertar el hijo siguiente aun no
visitado, según ordenamiento.
2. Si no, entonces eliminar nodo tope.
3. Si el nodo meta se alcanza, mencione éxito, de lo
contrario, notifique el fracaso.
4
Búsqueda Limitada Por Profundidad
• Se eliminan las dificultades que conlleva la búsqueda preferente por
profundidad al imponer un límite a la profundidad máxima de una
ruta. Para implantar tal límite se utiliza un algoritmo especial de
búsqueda limitada por profundidad, o utilizando el algoritmo
general de búsqueda con operadores que se informan
constantemente de la profundidad.
• Los operadores garantizan que, de existir, se encontrará la solución;
lo que no se garantiza es que la primera solución encontrada sea
necesariamente la más breve: la búsqueda limitada por
profundidad es completa, pero no óptima. Incluso al escogerse un
límite de profundidad excesivamente pequeño, la búsqueda
limitada por profundidad ni siquiera será completa.
5
Algoritmo de Búsqueda Limitada por
Profundidad
• Para realizar una búsqueda limitada por profundidad,
1. Inserte en una pila el elemento raíz (nodo de partida) con
profundidad igual a 1
2. Hasta que el elemento tope sea el nodo meta, o se vacié la
pila
1. Si nodo tope tiene hijos y profundidad es menor o igual a limite,
insertar el hijo siguiente aun no visitado con profundidad igual a
profundidad padre+1.
2. Si no, entonces eliminar nodo tope.
3. Si el nodo meta se alcanza, mencione éxito, de lo contrario,
notifique el fracaso.
6
Ejemplo:
7
La implementación del algoritmo seria:
Search J
open = [A]; closed = [ ]
open = [B,C,D]; closed = [A]
open = [E,F,C,D]; closed = [B,A]
open = [K,L,F,C,D]; closed = [E,B,A]
open = [S,L,F,C,D]; closed = [K,E,B,A]
open = [L,F,C,D]; closed = [S,K,E,B,A]
open = [T,F,C,D]; closed = [L,S,K,E,B,A]
open = [F,C,D]; closed = [T,L,S,K,E,B,A]
open = [M,C,D]; closed = [F,T,L,S,K,E,B,A]
open = [C,D]closed = [M,F,T,L,S,K,E,B,A]
open = [G,H,D ]; closed = [C,M,F,T,L,S,K,E,B,A ]
open = [N,H,D]closed = [G,C,M,F,T,L,S,K,E,B,A ]
open = [H,D]; closed = [N,G,C,M,F,T,L,S,K,E,B,A ]
open = [O,P,D]; closed = [H,N,G,C,M,F,T,L,S,K,E,B,A ]
open = [P,D]closed = [O,H,N,G,C,M,F,T,L,S,K,E,B,A ]
open = [U,D]; closed = [P,O,H,N,G,C,M,F,T,L,S,K,E,B,A ]
open = [ D]closed = [U,P,O,H,N,G,C,M,F,T,L,S,K,E,B,A ]
open = [I,J]; closed = [D,U,P,O,H,N,G,C,M,F,T,L,S,K,E,B,A]
open = [Q,J]; closed = [I,D,U,P,O,H,N,G,C,M,F,T,L,S,K,E,B,A ]
open = [J]; closed = [Q,I,D,U,P,O,H,N,G,C,M,F,T,L,S,K,E,B,A]
open = [R]; closed = [J,Q,I,D,U,P,O,H,N,G,C,M,F,T,L,S,K,E,B,A ]
La implementación del algoritmo seria:
Search J
Lim=3
open = [A(1)]; closed = [ ]
open = [B(2),C(2),D(2)]; closed = [A]
open = [E(3),F(3),C(2),D(2)]; closed = [B,A]
open = [F(3),C(2),D(2)]; closed = [E,B,A]
open = [C(2),D(2)]; closed = [F,E,B,A]
open = [G(3),H(3),D(2)]; closed = [C,F,E,B,A]
open = [H(3),D(2)]; closed = [G,C,F,E,B,A]
open = [D(2)]; closed = [H,G,F,E,B,A]
open = [I(3),J(3)]; closed = [D,H,G,F,E,B,A]
open = [J(3)]closed = [I,D,H,G,F,E,B,A]
open = []; closed = [J,I,D,H,G,F,E,B,A ]
Found J
Exit
9
Ejercicio:
Dado el árbol donde A es el nodo inicial y C el nodo final, indicar el
resultado aplicando el algoritmo de búsqueda preferente por
profundidad.
10
CONCLUSIONES
•Esto quiere decir que la búsqueda preferente por profundidad ni es la más
completa ni la más óptima. Por ello, cuando hay árboles de búsqueda con
prolongadas o infinitas profundidades máximas hay que evitar el empleo de la
búsqueda preferente por profundidad.
•Si la cantidad de soluciones de un problema es excesiva, la búsqueda
preferente por profundidad será mucha más rápida que la búsqueda
preferente por amplitud, puesto que tiene más probabilidades de poder
encontrar una solución luego de explorar tan sólo una pequeña porción de
todo el espacio. En el peor de los casos la búsqueda preferente por
profundidad se reduce a una búsqueda preferente por amplitud.
11
Descargar

definicion busqueda preferente por profundidad