Errata y método de búsqueda en profundidad progresiva
PREGUNTA:
Soy alumno de la UNED, matriculado
en esta asignatura, y desearia comentarles un par de cuestiones relativas
con la asignatura.
En el último párrafo de la página 119 del libro, donde
se habla de la complejidad espacial del método de búsqueda
en profundidad, se dice que la complejidad de este método pertenece
a O(p+r). Debido a que para cada nodo considerado en un nivel se deben
guardar en ABIERTA todos sus nodos sucesores ¿no deberia ser perteneciente
a O(p*r)?
Por otra parte, del método de profundidad progresiva (pág. 124)
se dice que "consiste en realizar una búsqueda en profundidad por
niveles, de forma que el límite de exploración aumenta en
una unidad por cada nivel analizado". Si
es así, en realidad se está haciendo una búsqueda
en amplitud, ya que para un límite de profundidad n, todos los nodos
de los niveles n-1 ya estaran explorados y, en esa vuelta, se exploraran
todos los nodos del nivel n. Según
lo entiendo yo, este método tiene sentido si se establece un nivel
de exploración lp>1. Entonces se hace una búsqueda en profundidad
(de profundidad máxima lp) a partir de la raiz. Cada vez que se
obtiene un nodo de nivel lp, éste se guarda. Cuando haya terminado
la exploración de todo el árbol de nivel lp, se continua
con el mismo método de búsqueda a partir de cada uno de los
nodos de nivel lp generados en la búsqueda anterior. Desearia que me comentaran si es así
o, por lo contrario, lo entiendo mal.
RESPUESTA:
Tiene usted razón en ambas apreciaciones. La primera es un error de
imprenta, donde aparece un + debería aparecer un *.
En cuanto a la búsqueda en profundidad progresiva, efectivamente,
permite realizar un recorrido en profundidad pero con la garantía de
encontrar la solución óptima, ya que cuando la profundidad es n, ya se
han investigado todos los de nivel n-1. Este hecho se verifica cuando el
lp>1.