Explicación búsqueda en amplitud y profundidad
Enviado por Christian Munar Benitez • 21 de Febrero de 2022 • Trabajo • 541 Palabras (3 Páginas) • 73 Visitas
Problema 1.1 Tomado del libro problemas resueltos de Inteligencia artificial, búsqueda y representación de Severino Fernández Galán (pág 27).
Dado el árbol de la figura donde B y L son los dos únicos nodos meta y A es el nodo inicial:
[pic 1]
Indique el orden en que se visitan los nodos, distinguiendo los que sólo se han generado
de aquéllos que se han elegido en el proceso de búsqueda de la solución, para cada uno
de los procedimientos siguientes:
BÚSQUEDA EN AMPLITUD.
1) Los primero que se debe hacer es crear una lista de nodos llamada abierta, esta lista contendrá el nodo raíz (en este caso el nodo [pic 2]
[pic 3]
2.1) Luego se asigna el primer nodo de la lista a una letra que actuará como variable para ver cual es el nodo actual en el que se encuentra la búsqueda (cada que se asigna un nodo a , este debe ser retirado de la lista).[pic 4][pic 5]
[pic 6][pic 7]
2.2) Posteriormente en un bucle, se generan los sucesores del nodo actual, se les asigna un apuntador hacia para saber cual es el padre, y finalmente los nodos sucesores son almacenados en la lista abierta, de modo que tendríamos lo siguiente.[pic 8]
[pic 9]
[pic 10]
[pic 11]
2.1) Luego del paso anterior repetimos el paso 2.1 con el siguiente nodo (el primero que aparece en la lista del paso 2.2).
[pic 12]
2.2) Nuevamente miramos los sucesores del nodo actual, se le asignan los punteros y finalmente son guardados en la lista abierta.
[pic 13]
[pic 14]
[pic 15]
2.1) El siguiente nodo es .[pic 16]
[pic 17]
2.2) Apuntadores y lista para los sucesores de (aunque en los anteriores pasos no se hizo, luego al asignar los apuntadores, siempre se verifica si nodo es un nodo meta, de esta manera el algoritmo sabe cuando detenerse).[pic 18]
[pic 19]
[pic 20]
[pic 21]
2.1) EL siguiente nodo es [pic 22]
[pic 23]
2.2) Apuntadores y lista para los sucesores de . [pic 24]
[pic 25]
[pic 26]
[pic 27]
2.1) El siguiente nodo es [pic 28]
[pic 29]
2.2) Apuntadores y lista para los sucesores de [pic 30]
[pic 31]
[pic 32]
Como es un nodo meta el proceso se detiene y se obtiene la solución rastreando los apuntadores.[pic 33]
[pic 34]
[pic 35]
El recorrido que se haría para encontrar la anterior solución sería el siguiente (todos los nodos que han pasado por la lista abierta)
...