11

Búsqueda en Profundidad

Embed Size (px)

Citation preview

Page 1: Búsqueda en Profundidad
Page 2: Búsqueda en Profundidad

Búsqueda en Profundidad(Depth – First)

Algoritmo:

1. Definir una Lista L con los nodos iniciales. En cualquier momento asumir que L es una lista de los nodos que no han sido examinados.2. Si L está vacía, falla. De otro modo, se toma un nodo N de L.3. Si N es una meta. Regrese el nodo y el trayecto desde el nodo inicial al nodo N.4. Si N no es una meta. Elimine N de L y añada todos los hijos al comienzo/frente de L de N, etiquetándolos con la trayectoria desde el inicio. Retorne al paso 2.

Page 3: Búsqueda en Profundidad

• Se tiene un árbol en un estado inicial y se cuenta con cuatro metas: M1, M2, M3 y M4.

Page 4: Búsqueda en Profundidad

• Se introduce A como primer elemento de la lista.

Page 5: Búsqueda en Profundidad

• A no es la meta así que se saca de la lista.

• Se introducen los hijos de A al frente de la lista guardando siempre el orden de descendencia y empezando de izquierda a derecha.

Page 6: Búsqueda en Profundidad

• Se saca AB de la lista ya que no se llego a ninguna meta.

• Se introducen los hijos de B siguiendo siempre el orden de izquierda a derecha.

• En el frente de la lista quedan ABD y ABE.

Page 7: Búsqueda en Profundidad

• Al no ser ABD una meta se saca de la lista.

• Se introducen los hijos de D al frente de la lista.

• Queda como resultado el estado mostrado.

Page 8: Búsqueda en Profundidad

• No se encuentra una meta en H.

• Se introducen los hijos de H y se puede ver que uno de los hijos es una meta.

Page 9: Búsqueda en Profundidad

• Se comprueba de que P no es una meta y se saca ABDHP de la lista.

Page 10: Búsqueda en Profundidad

• Se comprueba de que M2 es una de las metas y se registra el recorrido completo.

• Se Obtiene el recorrido hacia la meta.

• Existe mas de una meta en el árbol, el algoritmo alcanza el éxito cuando encuentra una meta y no distingue cual de ellas sea

Page 11: Búsqueda en Profundidad

• En el caso hipotético de que M2 no fuese una meta el siguiente paso habría sido sacar ABDHM2 de la lista y analizar el nodo I.

• Como I no es una meta el siguiente estado de la lista seria: L7 = {ABDIQ ABDIR ABDE AC}

• Se comprueba que ni Q ni R son metas y se sacan de la lista hasta llegar al estado de la lista L9 = {ABEJ ABEM1 AC}.

• Se expanden los hijos de J y la lista queda como L10 = {ABEJS ABEJT ABEM1 AC}.

• Ni S ni J son metas así que se sacan de la lista y finalmente se llega al estado meta M1 con la lista L12 = {ABEM1 AC}.

• Se hace el recorrido que lleva desde A hasta M1: A B E M1.