Applicazioni di Intelligenza Artificiale CLP - Compito A

Prof. Marco Gavanelli

14 Marzo 2007

Esercizio (8 punti)

Un bambino ha due collezioni di N blocchi numerati da 1 a N e vuole mettere i blocchi in sequenza in modo che:

• i due blocchi '1' abbiano 1 blocco che li separa
• i due blocchi '2' abbiano 2 blocchi che li separano
• ...
• i due blocchi 'N' abbiano N blocchi che li separano.

Ad esempio, una soluzione per N=4 è la seguente:

Si scriva un programma CLP per ECLⁱPS^e che, dato un numero N, risolve questo problema.

Suggerimento: Si noti che non è richiesto che l'output sia fornito nello stesso formato indicato in precedenza: lo studente è libero di mostrare l'output come preferisce.

Soluzione

Il suggerimento dato nel testo dice che non è necessario che l'output sua dato nello stesso formato dato in precedenza, quindi non è necessario che la lista che viene data in uscita per N=4 sia [4,1,3,1,2,4,3,2]: l'importante è che dai risultati che fornisce il programma sia univocamente determinabile qual è la soluzione.

Decidiamo allora di utilizzare un modello CSP con 2N variabili. Queste variabili hanno come dominio le possibili posizioni (gli indici) in cui un blocco viene posizionato

Viene creata una lista di lunghezza 2N, che contiene

• Nelle prime due posizioni le posizioni nella sequenza finale dei numeri '1'
• Nelle successive due posizioni le posizioni nella sequenza finale dei numeri '2'
• ...

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

langford(L,N):-
    N2 is N*2,
    length(L,N2),
    L :: 1..N2,
    vincoli(L,1),
    fd_global:alldifferent(L),
    labeling(L).

vincoli([],_).
vincoli([X,Y|T],N):-
    X-Y #= N+1,
    N1 is N+1,
    vincoli(T,N1).

questo significa che

• i blocchi '1' sono nelle posizioni 4 e 2
• i blocchi '2' sono nelle posizioni 8 e 5
• i blocchi '3' sono nelle posizioni 7 e 3
• i blocchi '4' sono nelle posizioni 6 e 1

Una rappresentazione dei blocchi per questa soluzione è quindi la seguente:

Se si desidera avere l'output in questo formato a partire dalla lista fornita in uscita dal programma, è possibile scrivere un semplice predicato, che comunque non è richiesto dal testo e che viene lasciato allo studente come esercizio.