Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

22 luglio 2010

Esercizio (8 punti)

Un problema di number partitioning è definito come segue.

Il problema consiste nel partizionare i numeri da 1 a N in due insiemi A e B tali che

• A e B hanno la stessa cardinalità
• la somma dei numeri in A è uguale alla somma dei numeri in B
• la somma dei quadrati in A è uguale alla somma dei quadrati in B

Si scriva un programma CLP(FD) che risolve il problema, dato il valore N.

Nota Il problema ha soluzione solo per alcuni valori di N.

Soluzione

:- lib(fd).
:- lib(fd_global).

numpart(L,N):-
    length(L,N),    length(LA,N),
    L ::0..1, % 0= insieme A, 1=insieme B
    LA::0..1, % 0= insieme B, 1=insieme A
    vincolo_ab(L,LA),
    % A e B hanno stessa cardinalita`
    CardA*2 #= N,
    sumlist(L,CardA),
    % Somma numeri in A = Somma numeri in B
    sum_el(LA,N,TermA),
    sum_el(L ,N,TermB),
    TermA #= TermB,
    % Somma quadrati in A = Somma quadrati in B
    sum_sq(LA,N,TermSqA),
    sum_sq(L, N,TermSqB),
    TermSqA #= TermSqB,
    labeling(L).

% Gli elementi della lista LA sono il negato degli elementi della lista LB
vincolo_ab([],[]).
vincolo_ab([A|LA],[B|LB]):-
    A #= 1-B,
    vincolo_ab(LA,LB).

sum_el([],_,0).
sum_el([X|T],N,X*N+Term):-
    N1 is N-1,
    sum_el(T,N1,Term).

sum_sq([],_,0).
sum_sq([X|T],N,X*N*N+Term):-
    N1 is N-1,
    sum_sq(T,N1,Term).