BENEMERITA UNIVERSIDAD AUTONOMA DE PUEBLA

MATERIA: Inteligencia Artificial

PROFESOR: Alfonso Garcés Báez

ESTUDIANTES:

Castañeda luna IsaacGonzález Escamilla MartinFalfan Guarneros José Raúl

TEMA: Búsqueda Preferente Por Profundidad

1

2

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.

3

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.

4

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.

5

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.

6

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.

7

Ejemplo:

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 ]

9

La implementación del algoritmo seria:

Search JLim=3open = [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 JExit

10

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.

11

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.