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.

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

• Se introduce A como primer elemento de la lista.

• 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.

• 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.

• 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.

• 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.

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

• 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

• 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.