Búsqueda iterativa en profundidad - Resolución del grafo

Para empezar habremos de explicar de qué se trata el problema con grafos. El ejercicio es el siguiente:

Un niño necesita recorrer desde el punto A hasta el punto H sin importar si hay demora o no. El camino se debe encontrar mediante búsqueda ciega iterativa en profundidad. El algoritmo es el siguiente:

1. Cota de profundidad C<--1
2. Lista L <--Nodo raíz
3. Si L € { } --> C=C+1. Ir al paso 2. Si no, N<- Extraer  primer nodo de L
4. Si Profundidad(N)<C -> genera sucesores de N. Si hay alguna solución, termina.
5. Si no, añadir al comienzo (L) los sucesores de N. En cualquier caso, ir a paso 3.

nOperaciones:

a)      Extraer: -Al comienzo –Al final

b)      Añadir: -Al comienzo –Al final

c)       Sucesores: -Todos –Unos pocos.

Esta es la prueba de escritorio:

Respuestas a las preguntas formuladas:

• ¿Cuántos nodos se generaron?: 8
• ¿Cuántos nodos se expandieron?: 57
• Costo de memoria:171 unidades