Profundización iterativa
Esta búsqueda ciega se caracteriza por ser una combinación entre la búsqueda por anchura y por profundidad, eso se logra poniendo un limite de profundidad por cada recorrido que se desee hacer, como bien sabemos un árbol tiene muchos niveles, y cada nivel de profundidad es mas extenso.
i = i + 1
El recorrido en profundización iterativa del árbol que se ve en la figura anterior es:
A,B,D,H,I,E,J,K,C,F,L,M,G,N,O
En ese orden de ideas, para poner un ejemplo, deseamos encontrar la solución por profundidad iterativa que vaya de la letra A la letra K, la prueba de escritorio del ejemplo anterior con las condiciones expuestas quedaría de la siguiente manera:
Por lo general el nivel de profundidad como lo dice su nombre es iterativo es decir:
|
L
|
N
|
SUCESORES
|
|
A
|
A
|
B,C
|
|
B,C
|
B
|
D,E
|
|
D,E,C
|
D
|
H,I
|
|
H,I,E,C
|
H
|
NO TIENE SUCESORES
|
|
I,E,C
|
I
|
NO TIENE SUCESORES
|
|
E,C
|
E
|
J,K
|
|
J,C,K
|
J
|
NO TIENE SUCESORES
|
|
K,C
|
K
|
SOLUCION
|
La anterior prueba de escritorio no tiene en cuenta las iteraciones, se hace de una vez, pero lo correcto en la búsqueda por profundidad iterativa, es poner un límite de profundidad e ir avanzando, en el ejercicio que viene a continuación (propuesto en clase), se realizara más detallada la prueba de escritorio.
Teniendo en cuenta eso al observar el siguiente grafo:
Vamos a desarrollar el árbol correspondiente al grafo para saber en qué nivel se encuentra K.
Se desea mediante la búsqueda en profundidad iterativa realizar el recorrido desde el nodo A hasta el nodo B mediante pruebas de escritorio.
Esas son las pruebas de escritorio correspondientes, para la búsqueda por profundidad iterativa el recorrido fue:
A,B,D,F,E,G,H,C,D,F,E,G,E,G,H,C,D,E,F,G,H,E,G,H,I,K
No hay comentarios:
Publicar un comentario