Salta ai contenuti. | Salta alla navigazione

Strumenti personali

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.
La distanza di Hamming fra due sequenze di bit è il numero di bit diversi nella stessa posizione. Ad esempio, le due sequenze
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
Si scriva un programma ECLiPSe che genera tale matrice.

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).