AMPLITUD ITERATIVA

AMPLITUD ITERATIVA

Como se observo la clase pasada la búsqueda por profundidad iterativa combina la búsqueda en profundidad y en anchura recorriendo el árbol por niveles y ramas, ahora se describirá la amplitud iterativa, la cual realiza una pequeña exploración de cada porción del árbol, lo que genera un ahorro de tiempo. La búsqueda por anchura iterativa propone mejorar la calidad de la búsqueda por profundidad iterativa. 

Su funcionamiento es el siguiente:

Lo primero que el algoritmo realiza es crear un nodo raíz, si no encuentra solución en el nodo raíz, entonces creara un hijo, si no encuentra la solución en el nodo hijo creara dos nuevos sucesores, hasta este momento se encuentran 4 nodos en memoria.  Si la solución no se encontrara en en los 4 nodos generados el algoritmo pedirá que se retorne el camino hasta el primer nodo y este creara otro hijo en, lo que quiere decir que el nodo raíz tendrá dos ramas desde ese momento. Al no encontrar la solución en el primer hijo de la segunda rama creara 2 sucesores, si no encuentra la solución en estos dos sucesores el algoritmo dirá que el camino se retorne hasta los nodos hoja de la primera rama creara un sucesor para cada nodo hoja y otro sucesor para el nodo padre de los nodos hoja, este es el proceso que seguirá el algoritmo hasta que encuentre la solución.

A continuación se muestran gráficos que harán mas fácil el entendimiento del funcionamiento del algoritmo búsqueda en anchura iterativa.

Imagen tomada de : https://intartificialblog.wordpress.com/2016/09/05/amplitud-iterativa/

Imagen tomada de:http://www.iiia.csic.es/~pedro/busqueda1-ciega

En resumidas palabra podemos decir que el algoritmo de búsqueda por anchura iterativa aumenta en 1 la cantidad de nodos hijos que tiene. es decir, d(b-1)+1

.