BÚSQUEDA POR PROFUNDIDAD

Teniendo en cuenta el siguiente algoritmo de busqueda por profundidad:
1. Lista L <- NODO RAIZ.
2. Si L pertenece a vacio FALLO STOP
   Sino  N<- extrae el primero 
3.Genera los sucesores de N. Si alguno  es solucion STOP
   Sino adiciona al inicio de L todos los sucesores 
4. Ir a 2


PRUEBA DE ESCRITORIO:

Se tienen 3 sapos y 3 ranas, cada no de ellos  puede saltar por encima de otro solo si el lugar esta vacío.

S1	S2	S3		R1	R2	R3
ROCA	ROCA	ROCA	ROCA	ROCA	ROCA	ROCA

1	R	R	R		S	S	S
2	R	R		R	S	S	S
3	R	R	S	R		S	S
4	R	R	S		R	S	S
5	R	R	S	S	R		S
6	R	R	S	S		R	S
7	R	R	S		S	R	S
8	R			R	S	R	S
9		R	S	R	S	R	S
10	S	R	S	R	S	R	S
11	S	R	S	R		R	S
12	S	R	S	R	S	R
13	S	R	S	R	S		R
14	S	R	S		S	R	R
15	S		S	R	S	R	R
16	S	S		R	S	R	R
17	S	S	S	R		R	R
18	S	S	S		R	R	R

¿Cuantos nodos genero?

 4^18 (4 son los primeros estados posibles y 18 son el numero de estados generados en la mejor solución)



¿Cuantos nodos se expandieron?

 4^17 (4  son los primeros estados posibles y 17 son los nodos expandidos)



FACTOR DE RAMIFICACIÓN: 4.

ESTADOS POSIBLES: 7!