prolog - superiores - Formulación del axioma del efecto

sup(a+b)=supa+supb demostracion

Question

Cómo escribir correctamente el axioma del efecto para la aplicación vacía (b, t) usando el predicado contiene (b, l, t) El predicado evalúa Verdadero, si el cubo b contiene l litros de agua en el tiempo t.

vacío (b, t): vacía por completo el cucharón b en el momento t. El efecto de la transferencia es visible en el tiempo t + 1

transferencia (b, b '', t): transfiere la mayor cantidad posible de agua del cubo b al cubo b'' sin derramar ningún arranque en el instante t. El efecto de la transferencia es visible en el tiempo t + 1.

El cubo 1 está lleno de agua y contiene 7 litros. El cubo 2 está vacío y contiene 3 litros. El estado objetivo es que b2 contiene 1 litro de agua.

Yo diría que la solución correcta es:

to any b,t,l( empty(b,t) -> contains(b,l,t))

¿Sería correcto o debería establecer la cantidad de litros a l = 5, por ejemplo?

Answer 1

Creo que la respuesta sería:

Empty(b,t) => Contains(b,0,t+1)

Answer 2

Para este problema, no es necesario un tiempo explícito, por lo que representaremos el historial como una lista de acciones. Por otro lado, debe representar explícitamente el estado de su sistema, es decir, el contenido actual de los tres segmentos. La razón es que las estructuras de datos de Prolog (es decir, los términos) no se pueden cambiar, una vez que se crean. Dado que hay muchos términos sin sentido, es una buena práctica definir tipos de datos primero a través de un predicado is_type/1 . Como usará aritmética en algún momento (cuando vierte agua de una cubeta a otra), usaré restricciones aritméticas en lugar del antiguo predicado is/2 .

:- use_module(library(clpfd)).

Primero declaramos que hay 3 cubos, representados por los átomos b1, b2 y b3:

is_bucket(b1).
is_bucket(b2).
is_bucket(b3).

Entonces tenemos que definir nuestro estado. Solo usamos un término buckets/3 donde el primer argumento tiene la capacidad de b1 y del mismo modo para los otros dos.

is_state(buckets(X,Y,Z)) :-
    % each bucket contains at least 0 liters
    [X,Y,Z] ins 0 .. sup.

Todos los contenedores pueden no ser negativos, por lo que establecemos su dominio en un rango de cero a infinito (positivo).

Ahora, ¿qué es una acción? Hasta aquí describiste vaciar y verter:

is_action(empty(B)) :-
    is_bucket(B).
is_action(pour(From, To)) :-
    is_bucket(From),
    is_bucket(To).

Para vaciar un cubo, solo necesitamos saber cuál. Si vertimos agua de uno a otro, necesitamos describir ambos. Como ya tenemos un predicado que describe un segmento, podemos simplemente establecer una regla como "Si From y To son segmentos, entonces el pour(From, To) es una acción.

Ahora tenemos que explicar cómo una acción transforma un estado. Esta es una relación entre el estado anterior, el nuevo estado, y porque nos gustaría saber qué sucede, también la historia.

% initial state
state_goesto_action(buckets(7,5,3), buckets(7,5,3), []).

La transición para el estado inicial no cambia nada y tiene un historial vacío (el [] ).

% state transitions for moving
state_goesto_action(buckets(X,Y,Z), buckets(0,Y,Z), [empty(b1) | History]) :-
    state_goesto_action(_S0, buckets(X,Y,Z), History).

Esta regla se puede leer como "Si tuviéramos una acción proveniente de algún estado _S0 condujera a los _S0 de estado buckets(X,Y,Z) con algo de History , entonces podemos realizar la acción empty(b1) continuación, y alcanzaremos el buckets(0,Y,Z) estado buckets(0,Y,Z) ". En otras palabras, el estado se actualiza y la acción se antepone al historial. Una regla simétrica funciona para los otros cubos:

state_goesto_action(buckets(X,Y,Z), buckets(X,0,Z), [empty(b2) | History]) :-
    state_goesto_action(_S0, buckets(X,Y,Z), History).
state_goesto_action(buckets(X,Y,Z), buckets(X,Y,0), [empty(b3) | History]) :-
    state_goesto_action(_S0, buckets(X,Y,Z), History).

¿Cómo podemos verificar si esto tiene sentido? Miremos las historias de longitud 2:

?- state_goesto_action(_,S1,[H1,H2]).
S1 = buckets(0, 3, 5),
H1 = H2, H2 = empty(b1) .

Ah, bueno, si ambas acciones están empty(b1) , el primer cubo está vacío y los otros intactos. Veamos otras soluciones:

S1 = buckets(0, 0, 5),
H1 = empty(b1),
H2 = empty(b2) ;

S1 = buckets(0, 3, 0),
H1 = empty(b1),
H2 = empty(b3) ;

S1 = buckets(0, 0, 5),
H1 = empty(b2),
H2 = empty(b1) ;

S1 = buckets(7, 0, 5),
H1 = H2, H2 = empty(b2) ;

S1 = buckets(7, 0, 0),
H1 = empty(b2),
H2 = empty(b3) ;

S1 = buckets(0, 3, 0),
H1 = empty(b3),
H2 = empty(b1) ;

S1 = buckets(7, 0, 0),
H1 = empty(b3),
H2 = empty(b2) ;

S1 = buckets(7, 3, 0),
H1 = H2, H2 = empty(b3).

Parece que tenemos todas las posibilidades de vaciar los cubos (y nada más :-)). Ahora necesita agregar reglas para verter de un depósito a otro. ¡Buena suerte!

(Editar: errores tipográficos, error en la segunda regla)

Answer 3

Dejo la respuesta anterior porque deja algunas partes en las que pensar (y la pregunta es sobre implementar solo la acción vacía). Solo para proporcionar una implementación completa también:

:- use_module(library(clpfd)).

bucket_capacity(b1,7).
bucket_capacity(b2,3).
bucket_capacity(b3,5).

% projections to a single bucket
state_bucket_value(buckets(X, _, _),b1,X).
state_bucket_value(buckets(_, Y, _),b2,Y).
state_bucket_value(buckets(_, _, Z),b3,Z).

% state update relation by a single bucket
state_updated_bucket_value(buckets(_, Y, Z), buckets(X0, Y,  Z ), b1, X0).
state_updated_bucket_value(buckets(X, _, Z), buckets(X,  Y0, Z ), b2, Y0).
state_updated_bucket_value(buckets(X, Y, _), buckets(X,  Y,  Z0), b3, Z0).


% initial state
state_goesto_action(S0, S0, []) :-
    S0 = buckets(X,Y,Z),
    bucket_capacity(b1,X),
    bucket_capacity(b2,Y),
    bucket_capacity(b3,Z).
% state transition for emptying
state_goesto_action(S1, S2, [empty(Bucket) | History]) :-
    state_updated_bucket_value(S1, S2, Bucket, 0),
    state_goesto_action(_S0, S1, History).
% state transition for pouring
state_goesto_action(S1, S3, [pour(From,To) | History]) :-
    bucket_capacity(b1,Max),
    state_bucket_value(S1,From,X),
    state_bucket_value(S1,To,Y),
    From0 #= min(X+Y, Max),
    To0 #= max(X-Y, 0),
    state_updated_bucket_value(S1, S2, From, From0),
    state_updated_bucket_value(S2, S3, To, To0),
    state_goesto_action(_S0, S1, History).

Para averiguarlo, si podemos encontrar un cubo con exactamente un litro, podemos enumerar todas las historias:

?- length(L,_), state_bucket_value(S,_,1), state_goesto_action(_, S, L).
L = [pour(b1, b3), pour(b1, b2), empty(b1), pour(b1, b3)],
S = buckets(5, 0, 1) ;
L = [pour(b1, b3), pour(b1, b2), pour(b1, b1), pour(b1, b3)],
S = buckets(5, 0, 1) ;
L = [pour(b1, b3), pour(b1, b2), pour(b2, b1), empty(b1)],
S = buckets(7, 0, 1) ;
L = [pour(b1, b3), pour(b1, b2), pour(b2, b1), pour(b1, b1)],
[...].

Y solo para verificar si el predicado es reversible:

?- L = [pour(b1, b3), pour(b1, b2), empty(b1), pour(b1, b3)], state_goesto_action(_, S, L).
L = [pour(b1, b3), pour(b1, b2), empty(b1), pour(b1, b3)],
S = buckets(5, 0, 1) ;
false.

Editar: se eliminaron las restricciones de dominio para acelerar el cálculo (comenzamos con un estado fijo, por lo que las restricciones siempre se basarán y se pueden propagar sin etiquetar).