Algoritmo de Amplitud Iterativa
Se dispone del siguiente grafo:
para poder entender mejor este algoritmo, debemos tener en cuenta la búsqueda en anchura, la cual busca todas las posibles soluciones siempre que las haya expandiendo nivel a nivel el árbol en un orden bien establecido como veremos a continuación:
Acá observamos que los nodos se van generando en un orden a medida que se va avanzando por los niveles del árbol, y los niveles inmediatamente anteriores se van eliminando, aunque es un algoritmo óptimo y complejo, entre mas niveles tenga que avanzar, mas capacidad de almacenamiento deberá tener la maquina y mas demorado sera encontrar una solución al problema planteado. es por esta razón por la cual se implementa la búsqueda de amplitud iterativa o búsqueda en anchura iterativa.
Como se observa en el árbol de la amplitud iterativa, los nodos se van recorriendo en anchura en vez de profundidad, generando solo los primeros nodos hijos para así optimizar el espacio a la hora de correr el algoritmo.
En la amplitud iterativa, aunque se recorren varias veces los nodos, se soluciona el problema del espacio en la búsqueda en anchura, obteniendo un resultado similar, aunque gasta mas tiempo.
Ahora, vamos a aplicar este algoritmo (AI) para la solución del grafo, a continuación mostraremos el grafo en forma de árbol rompiendo ciclos:
Como podemos observar en el árbol, todos los nodos finales llegan a f, para una mejor comprensión del problema, modificaremos el grafo de la siguiente manera:
De tal forma que el nuevo árbol del grafo rompiendo ciclos queda de la siguiente manera:
Ahora, observamos que existe un nodo hoja el cual no contiene la f, ahora, aplicaremos el algoritmo a este árbol de tal forma que se entienda de una mejor manera el funcionamiento de este:
| # | PASOS | C | L | N |
| 1 | 1. Cota anchura c <--1, | 1 | ||
| 2 | 2. Lista L <-- nodo raíz. | A | ||
| 3 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | A | ||
| 4 | 4. si n es objetivo, éxito, stop | A | ||
| 5 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | B | ||
| 6 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | B | ||
| 7 | 4. si n es objetivo, éxito, stop | |||
| 8 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | C | ||
| 9 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | C | ||
| 10 | 4. si n es objetivo, éxito, stop | |||
| 11 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | D | ||
| 12 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | D | ||
| 13 | 4. si n es objetivo, éxito, stop | |||
| 14 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | F | ||
| 15 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | F | ||
| 16 | 4. si n es objetivo, éxito, stop | |||
| 17 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | |||
| 18 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | 2 | ||
| 19 | 2. Lista L <-- nodo raíz. | A | ||
| 20 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | A | ||
| 21 | 4. si n es objetivo, éxito, stop | |||
| 22 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | B,C | ||
| 23 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | C | B | |
| 24 | 4. si n es objetivo, éxito, stop | |||
| 25 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | D,C | ||
| 26 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | C | D | |
| 27 | 4. si n es objetivo, éxito, stop | |||
| 28 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | F,C | ||
| 29 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | C | F | |
| 30 | 4. si n es objetivo, éxito, stop | |||
| 31 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | |||
| 32 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | C | ||
| 33 | 4. si n es objetivo, éxito, stop | |||
| 34 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | B,D | ||
| 35 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | D | B | |
| 36 | 4. si n es objetivo, éxito, stop | |||
| 37 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | |||
| 38 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | D | ||
| 39 | 4. si n es objetivo, éxito, stop | |||
| 40 | 5. Añadir al principio de L los primeros C sucesores de N, etiquetando cada sucesor con su camino desde la raíz. Ir al paso 3 | F | ||
| 41 | 3. Si l vacía, c <--c+1, ir al paso 2. Sino, n <-- extraer-primero(L) | F |
Como observamos en la tabla anterior, se muestra el paso a paso de como se realiza el recorrido del árbol de acuerdo al funcionamiento del algoritmo de búsqueda en amplitud iterativa.
El algoritmo encuentra la solución en los pasos: 15,29,41 suponiendo que el objetivo sea la F.
aunque eficiente en cierto aspecto, este algoritmo presenta un inconveniente, y es que en el caso de no temer un nivel máximo o un nodo máximo al que llegar, entraría en un ciclo infinito en el cual no encontraría nunca la solución.
Comentarios
Publicar un comentario