Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

15 settembre 2010

Esercizio (8 punti)

Data una lista di interi L, è facile calcolare qual è la distanza minima fra due elementi di L. Ad esempio, nella lista [3,8,1,5,11], la distanza minima è 2, che si ottiene con 3-1, oppure con 5-3.

Dati in ingresso due naturali N e Num, si scriva un programma CLP(FD) che genera una lista di N numeri compresi fra 1 e Num che massimizza la distanza minima fra gli elementi della lista (si supponga N≥Num).

Soluzione

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

go(L,N,Num,M):-
    length(L,N),
    L :: 1..Num,
    all_min_dist(L,M),
    MenoM #= -M,
    M :: 0..Num,
    fd_global:alldifferent(L), % Vincolo ridondante, migliora l'efficienza
    minimize(
    (
        labeling([M|L])
    ),MenoM).

all_min_dist([],_).
all_min_dist([H|T],M):-
    all_min_dist_loop(T,H,M),
    all_min_dist(T,M).

all_min_dist_loop([],_,_).
all_min_dist_loop([H|T],X,M):-
    (H-X #>= M #\/ X-H #>= M),
    all_min_dist_loop(T,X,M).