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.