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

Problema de búsqueda en profundidad con grafos.

 Para empezar, es necesario aclarar de qué se trata el problema. Se ha planteado un grafo en el cual hay que llegar desde el punto A hasta el F con el camino posible. Como esto se realiza con búsqueda ciega, no hay necesidad de buscar un camino óptimo sino el primero que se encuentre.

La solución se encuentra de esta manera:

Para desarrollar este problema de búsqueda en anchura, se utilizará el siguiente algoritmo en pseudocódigo.

1. L <- Lista de nodos iniciales del problema. Si L € { } -> Fallo, detener. 
2. Si no N<- Extraer nodo de L
3. Generar sucesores de N. Si un sucesor es solución, retorna camino a L, detener
4. Si no, añadir sucesores de N a L, retornar a paso 2)

Operaciones:

a)      Extraer: -Al comienzo –Al final

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

c)       Sucesores: -Todos –Unos pocos.

Prueba de escritorio:

Paso	Lista L	Estructura N	Sucesores N	Observación
1	A			Asigna nodo A a L
2		A		Asigna nodo A a N
3			B,C	Expansión Nodo, 1): A, No hay solución.
4	B,C			Añadir sucesores de N a L
5		B		Añadir nodo a N
6			A,C,D	Expansión nodo 2): B, No hay solución.
7	C, A,C,D			Añadir sucesores de N a L
8		C		Añadir nodo a N
9			A,B,E	Expansión nodo 3): C, No hay solución.
10	A,C,D,A,B,E			Añadir sucesores de N a L
11		A		Añadir nodo a N
12			B,C	Expansión nodo 4): A, No hay solución.
13	C,D,A,B,E,B,C			Añadir sucesores de N a L
14		C		Añadir nodo a N
15			A,B,E	Expansión nodo 5): C, No hay solución.
16	D,A,B,E,B,C,A,B,E			Añadir sucesores de N a L
17		D		Añadir nodo a N
18			B	Expansión nodo 6): D, No hay solución.
19	A,B,E,B,C,A,B,E,B			Añadir sucesores de N a L
20		A		Añadir nodo a N
21			B,C	Expansión nodo 7): A, No hay solución.
22	B,E,B,C,A,B,E,B,B,C			Añadir sucesores de N a L
23		B		Añadir nodo a N
24			A,C,D	Expansión nodo 8): B, No hay solución.
25	E,B,C,A,B,E,B,B,C			Añadir sucesores de N a L
26		E		Añadir nodo a N
27			C,F	Expansión nodo 9): E, Solución encontrada: F

Solución a las preguntas:

¿Cuántos nodos se generaron?: 6

¿Cuántos nodos se expandieron?: 9

Gasto de memoria: 27 unidades.