CLP 12 lug 07
Applicazioni di Intelligenza Artificiale - CLP
Prof. Marco Gavanelli
12 Luglio 2007
Esercizio (8 punti)
Si vuole generare una matrice binaria (cioè i cui elementi sono 0 o 1) N ×M tale che:
- le righe siano ordinate in ordine lessicografico (ovvero secondo l'ordine alfabetico, supponendo che 0 venga prima di 1);
- si vuole massimizzare la minima distanza di Hamming fra righe consecutive.
1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 0 |
sono a distanza 2 (hanno 2 bit diversi).
Ad esempio, dati N=4 e M=3 una soluzione ottima è data dalla matrice:
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Suggerimento Si vedano sul manuale di ECLiPSe la libreria matrix_util
ed il vincolo lexico_le
della libreria fd_global
.
Soluzione
:- lib(fd).
:- lib(matrix_util).
:- lib(fd_global).
codice(N,M,Matr):-
matrix(N,M,Matr),
flatten(Matr,Flat),
Flat :: 0..1,
distanze(Matr,LDistanze),
minlist(LDistanze,DistMin),
% Devo calcolare il massimo, ma il predicato ECLiPSe mi permette solo di trovare il minimo
% allora cambio il segno prima di minimizzare
Dneg #= -DistMin,
min_max(labeling(Flat),Dneg).
% Crea una lista di distanze fra le righe consecutive
distanze([_],[]).
distanze([A,B|T],[D|LD]):-
dist(A,B,D),
lexico_le(A,B),
distanze([B|T],LD).
dist([],[],0).
dist([HA|LA],[HB|LB],D):-
HA #\= HB #<=> Diversi,
D #= Diversi+D1,
dist(LA,LB,D1).