Smbd

JUEGO: CRUZAR EL RIO
El Problema de los Diablitos y los Sacerdotes:
En este conocido problema hay tres diablitos, tres sacerdotes, un rio y una balsa. Los diablitos, los sacerdotes y la balsa se encuentran en una rivera del rio. Los seis sujetos deben cruzar el rio, pero el bote permite trasladar a lo más dos personas a la vez. Se debe encontrar una secuencia de movimientos de personas en elbote que permita cruzar a los seis individuos de manera segura. No se debe permitir que haya más diablitos que sacerdotes en algún lado del rio en algún momento.
Terminología
Para analizar los problemas de búsqueda usaremos la siguiente terminología:
Estado: Dado un problema, un estado es una configuración del dominio asociado al problema que se está analizando.
Por ejemplo, en el caso de losdiablitos y los sacerdotes, un estado está dado por la posición de los diablitos, sacerdotes y la balsa.
El estado del problema lo representaremos como un símbolo
estado (Di, Si, Dd, Sd, B)
donde los argumentos corresponden a:
Di: Diablitos en la rivera izquierda
Si: Sacerdotes en la rivera izquierda
Dd: Diablitos en la rivera derecha
Sd: Sacerdotes en la rivera derecha
B: Indica en qué ladodel rio se encuentra el bote. Los valores posibles serán izq. y der.
Estado inicial: Dado un problema de búsqueda, existe uno o más estados que se toman como de partida.
Descripción de estado de objetivos: Para un problema de búsqueda pueden haber varios estados que representan una solución al problema de búsqueda.
Estos estados son descritos mediante la definición de un predicado o funciónque, dado un estado, retorna verdadero si el estado es un estado objetivo y falso en otro caso.
En el ejemplo podemos utilizar la función final/1 para identificar estados finales. Así:
Final(estado(0,0,3,3,der)).
Establece que el estado final es uno en el cual todos los diablitos y sacerdotes están al lado derecho del rio.
Solución Óptima: En muchos casos se necesita encontrar un estado óptimo.Es decir, que sea un estado objetivo, pero que además sea mejor, en algún sentido, que todos los estados objetivos alternativos. En este caso, el problema de búsqueda corresponde a un problema de optimización.
Operador: Un operador es una función que, dado un estado, entrega otro estado. Por ejemplo, en el caso de los diablitos y de los sacerdotes, podemos definir de cruce resulta/3 que recibe unestado y genera un estado sucesor.
El predicado resulta(E,A,Er) cuando Er es el estado que se genera al ejecutar la acción A sobre el estado E.
Podemos escribir este predicado de la siguiente manera:
resulta(E1, cruzar(D,S),E2):-
posible(cruzar(D,S),E1),
E1 = estado(Di,Si,Dd,Sd,izq),
Dip is Di-D,
Sip is Si-S,
Ddp is Dd+D,
Sdp is Sd+S,
E2 = estado(Dip,Sip,Ddp,Sdp,der).resulta(E1, cruzar(D,S),E2):-
posible(cruzar(D,S),E1),
E1 = estado(Di,Si,Dd,Sd,der),
Dip is Di+D,
Sip is Si+S,
Ddp is Dd-D,
Sdp is Sd-S,
E2= estado(Dip,Sip,Ddp,Sdp,izq).
Donde posible/2 se define de la siguiente manera:
posible(cruzar(D,S),estado(Di,Si,_,_,izq)):-
D=<Di, S=<Si.
posible(cruzar(D,S),estado(_,_,Dd,Sd,der)):-
D=<Dd, S=<Sd.
SucesorInmediato: Dado un estado y un operador, el estado que se obtiene al aplicar el operador al estado se le llama sucesor inmediato. También se dice que el estado es generado por el operador a partir del estado.
En nuestro ejemplo, podemos encontrar los sucesores de un estado utilizando los siguientes predicados:
sucesor(E1,E2) :- accion(A),
resulta(E1,A,E2),
seguro(E2).accion(cruzar(C,M)):- (C=0 ; C=1 ; C=2),
(M=0 ; M=1 ; M=2),
C+M=<2, C+M>=1.
seguro(estado(Ci,Mi,Cd,Md,_)):- (Ci=<Mi; Mi=0),
(Cd=<Md; Md=0).

Espacio de Búsqueda: El espacio de búsqueda está formado por el o los estados iniciales, junto con todos aquellos estados que se pueden obtener de la aplicación de alguna secuencia de operadores e algún estado inicial. En nuestro...