Ranas y sapos

Formalizaciòn de problemas (ranas y sapos) 

El problema de los sapos y las ranas consiste en tres ranas y tres sapos que están ubicados en unos nenúfares,  con un nenúfar vació en el intermedio, el objetivo consiste en pasar las ranas al lugar de los sapos y viceversa. 

Para formalizar este problema como un problema de búsqueda se hace lo siguiente: 

Hay que establecer un estado inicial y un estado final. 


Estado Inicial 

Estado final

Espacio de estados: 

El espacio de estados como su nombre lo indica son todos los estados posibles que se pueden obtener al hacer algún movimiento, en este caso seria de cuantas formas posibles las ranas van a acomodarse. 

como tenemos 7 espacios, la formula seria: 

7! = 5040, 5040 son los estados posibles que pueden tener las ranas en este problema. 

Operadores

Los operadores son instru

cciones que se encargan de cambiar de un estado a otro, Cada operador debe contar con una premisa o condición. 

Los operadores para este ejercicio son los siguientes: 

Si el espacio esta vació una rana puede saltar al espacio y en sentido a la izquierda.

Si el espacio esta vació y hay un sapo al lado de la rana, la rana puede saltar sobre ella. 

Si el espacio esta vació un sapo puede saltar a este y en sentido hacia la derecha

Si el espacio esta vació y hay una rana al lado del sapo, el sapo puede saltar sobre ella. 

Solución en búsqueda por anchura. 

1) R1 R2 R3 V S1 S2 S3 

2) R1 R2 V R3 S1 S2 S3

3) R1 R2 S1 R3 V S2 S3 

4) R1 R2 S1 R3 S2 V S3

5) R1 R2 S1 V S2 R3 S3

6) R1 V S1 R2 S2 R3 S3 

7) V R1 S1 R2 S2 R3 S3 

8) S1 R1 V R2 S2 R3 S3 

9) S1 R1 S2 R2 V R3 S3 

10) S1 R1 S2 R2 S3 R3 V

11) S1 R1 S2 R2 S3 V R3 

12) S1 R1 S2 V S3 R2 R3 

13) S1 V S2 R1 S3 R2 R3

14) S1 V S2 R1 S3 R2 R3

15) S1 S2 V R1 S3 R2 R3

16) S1 S2 S3 R1 V R2 R3

17) S! S2 S3 V R1 R2 R3 

Tiempo utilizado en hallar la solucion

1+b+b^2+.........+b^d = b^d 

T=  2^16 = 65.536

Espacio utilizado en hallar la solución 

E = 2^16 = 65536