Tip:
Highlight text to annotate it
X
Dada la suboptimalidad de la búsqueda en profundidad,
¿por qué alguien escogería usarla?
Bueno, la respuesta tiene que ver con los requisitos de almacenaje.
Aquí he ilustrado un espacio de estado
que consiste de un árbol binario muy grande o hasta infinito.
Mientras descendemos los niveles 1, 2, 3, hasta el nivel n,
el árbol se hace más y más grande.
Ahora, consideremos la frontera para cada uno de estos algoritmos de búsqueda.
Para la búsqueda de primero-anchura, sabemos que una frontera parece así,
así que cuando llegamos hasta el nivel n, necesitaremos un espacio de almacenaje del
2 al n de pase en una búsqueda de primero-anchura.
Para una búsqueda primero-barato, la frontera será mas complicada.
Más o menos va a resolver este contorno de costo,
pero tendrá un número total de nodos similar.
Pero para búsqueda en profundidad, mientras bajamos por el árbol, comenzamos a bajar por este ramo,
y luego retrocedemos, pero en cualquier punto, nuestra frontera tendrá solo n nodos
en vez de 2 al n nodos, así que ese es un ahorro substancial para búsqueda en profundidad.
Ahora, claro, si al mismo tiempo vamos tomando en cuenta la serie explorada,
entonces no logramos tantos ahorros.
Pero sin el conjunto explorado, la búsqueda en profundidad tiene una enorme ventaja
en cuanto a espacio ahorrado.
Una propiedad más de los algoritmos que hay que considerar
es la propiedad de plenitud, lo cual significa si hay una meta en algún lado,
¿podrá el algoritmo encontrarlo?
Ahora bien, pasemos de los árboles muy grandes a los árboles infinitos,
y digamos que hay alguna meta escondida en algún lado muy abajo en ese árbol.
Y la pregunta es, ¿son cada uno de estos algoritmos completos?
Es decir, ¿es garantizado que encontrarán un camino a la meta?
Seleccione la casilla para los algoritmos que, en este sentido, son completos.