Il Forum di Orebla.it

Benvenuto nella community di Orebla.it
Oggi è dom 16 feb, 2020 7:57 pm

Tutti gli orari sono UTC + 1 ora




Apri un nuovo argomento Rispondi all’argomento  [ 2 messaggi ] 
Autore Messaggio
Messaggio da leggereInviato: mar 08 giu, 2010 1:28 am 
Non connesso
super-guru
super-guru
Avatar utente

Iscritto il: mar 28 dic, 2004 6:54 pm
Messaggi: 300
Località: Pisa
Un CSP (Constraint Satisfaction Problem) è un problema riconducibile a un algoritmo per la risoluzione che, dati in ingresso un insieme di variabili (se ad esempio prendiamo un sudoku, ogni cella è una variabile a sé stante), un insieme di domini (sempre nel caso del sudoku, nel caso 3x3x3 il dominio di ogni cella è l'insieme di numeri da 1 a 9) e un insieme di vincoli (nel caso del sudoku, i vincoli sono rappresentati dalla regola secondo la quale ogni riga, colonna e griglia non deve presentare due cifre uguali), calcola la soluzione, una o più possibili, se esiste, assegnando a ogni variabile un sottoinsieme del dominio che soddisfa tutti i vincoli del problema. Nel caso del sudoku, date le variabili, i domini e i vincoli, un algoritmo per la risoluzione del CSP calcolerà, se esiste, la soluzione del sudoku, ovvero i sottoinsiemi dei domini delle singole variabili che soddisfano i vincoli di integrità del problema stesso.

Questo tipo di problemi sono molto comuni nell'ambito dell'intelligenza artificiale, ma finora, almeno che io sappia, non esiste un software all-purpose che consenta di gestire tutto questo insieme di algoritmi allo stesso modo, ma ci sono perlopiù algoritmi modellati a misura sulle singole richieste del problema. Questa è una pecca non indifferente, perché il programmatore perde di vista il suo obiettivo principale, che dovrebbe essere la risoluzione del problema dando in pasto a una "scatola nera" le variabili, i domini e i vincoli e ottenendone i sottodomini di validità.

Ho quindi sviluppato questa piccola libreria in C++, completamente templatizzata (e quindi teoricamente compatibile con ogni tipo di variabili nel problema, primitivi, composti o oggetti), che consente di calcolare i sottodomini di validità del problema forniti i dati di partenza in modo estremamente semplice. L'interfaccia per il programmatore è mantenuta estremamente pulita e intuitiva. Il numero di variabili del problema viene specificato nel costruttore, i domini settati semplicemente come vettori, e i vincoli sono funzioni booleane che il programmatore scrive per il suo specifico problema e che può settare, appendere o rimuovere dall'oggetto CSP richiamando il metodo specifico. Allo stesso modo il programmatore può restringere il problema settando una specifica variabile a un determinato valore e ricalcolando i sottodomini di validità in funzione di quel cambiamento, o rimuovendo il valore settato, e si può anche configurare la libreria in modo che, se una certa variabile ha un sottodominio di validità contenente un solo elemento, quest'elemento viene automaticamente settato come valore della variabile stessa, in quanto unico possibile. È ovviamente possibile sapere se il problema, in funzione delle variabili, dei domini, dei vincoli e degli assegnamenti forniti, è possibile (ammette un'unica soluzione), indeterminato (ammette più di una soluzione, e i dati forniti non sono sufficienti per stabilirne univocamente una) o impossibile (ogni configurazione viola i vincoli di integrità del problema).

L'uso è molto semplice (basta includere il file csp++/csp++.h all'interno dei propri sorgenti), una documentazione completa dei metodi è fornita nella directory doc/ autogenerata da doxygen, sia in formato HTML che in formato LaTeX, e all'interno della directory sono presenti due esempi di uso, che si possono compilare o pulire rispettivamente dando `make examples' e `make examples-clean'. Per installare la libreria basta dare un `make install' dalla directory di base come root, e i file verranno automaticamente copiati in /usr/local (basta modificare il Makefile se si vuole copiarli in un'altra locazione).

I due esempi forniti sono:

- fourcolours.cpp. Una semplice applicazione che consente all'utente di assegnare interattivamente dei colori a un insieme di Stati europei. Gli Stati rappresentano le variabili del problema, i colori sono i rispettivi domini (si hanno solo 4 colori, in quanto per il teorema cromatico dei grafi 4 colori sono il numero minimo sufficiente per colorare una cartina geografica rispettando i vincoli di adiacenza) e il vincolo di integrità è che due Stati adiacenti non possono avere lo stesso colore. A ogni scelta dell'utente vengono ricalcolati i sottodomini di validità degli Stati rimanenti, in modo che all'inserimento successivo vengano presentate solo le opzioni valide di colore in funzione dei vincoli di integrità e della configurazione attuale del problema. Se uno Stato può avere un solo colore in funzione della configurazione corrente, tale colore viene scelto automaticamente senza chiederlo all'utente. Se a un certo punto esiste una sola configurazione che può risolvere il problema, allora questa configurazione viene scelta automaticamente senza chiedere l'inserimento interattivo dei dati da parte dell'utente. Esempio di uso:

Codice:
Insert a colour for country 'Italy' between
        [ red, green, blue, yellow ]: red
Insert a colour for country 'Switz.' between
        [ green, blue, yellow ]: green
Insert a colour for country 'Denmark' between
        [ red, green, blue, yellow ]: red
Insert a colour for country 'Germany' between
        [ blue, yellow ]: blue
Setting colour yellow for Austria
Setting colour yellow for France
Insert a colour for country 'Spain' between
        [ red, green, blue ]: red
Insert a colour for country 'Portugal' between
        [ green, blue, yellow ]: green
Insert a colour for country 'Belgium' between
        [ red, green ]: red
Setting colour green for Luxemb.
Insert a colour for country 'Holland' between
        [ green, yellow ]: green

Domain for variable 'Italy':    [ red ]
Domain for variable 'Switz.':   [ green ]
Domain for variable 'Denmark':  [ red ]
Domain for variable 'Germany':  [ blue ]
Domain for variable 'Austria':  [ yellow ]
Domain for variable 'France':   [ yellow ]
Domain for variable 'Spain':    [ red ]
Domain for variable 'Portugal': [ green ]
Domain for variable 'Belgium':  [ red ]
Domain for variable 'Luxemb.':  [ green ]
Domain for variable 'Holland':  [ green ]

The CSP has a solution
The solution is unique


- sudoku.cpp. Un'applicazione interessante che risolve automaticamente un sudoku fornito da un file di testo (nella directory sono già presenti alcuni sudoku di esempio, uno 2x2x2, uno facile, uno medio e uno difficile, se si vuole che l'applicazione risolvi un nuovo sudoku basta creare un file che lo contenga sullo schema di quelli forniti come esempio e passarlo come argomento al programma). Esempio di sessione:

Codice:
(blacklight@wintermute ~/prog/c++/libcsp++ $)> time ./sudoku sudoku-easy.txt
Sudoku to be solved:

  6 . 8   . . .   9 . 4
  2 . .   . 1 4   . 5 .
  . . 7   9 8 3   . . .

  . 2 .   5 . .   . . 9
  . 3 9   4 . 8   5 1 .
  8 . .   . . 9   . 7 .

  . . .   3 9 2   7 . .
  . 5 .   7 4 .   . . 8
  9 . 4   . . .   3 . 6

Solving ... step 1
Solving ... step 2
Solving ... step 3
Solving ... step 4
Solving ... step 5
Solving ... step 6


  6 1 8   2 7 5   9 3 4
  2 9 3   6 1 4   8 5 7
  5 4 7   9 8 3   2 6 1

  4 2 1   5 3 7   6 8 9
  7 3 9   4 6 8   5 1 2
  8 6 5   1 2 9   4 7 3

  1 8 6   3 9 2   7 4 5
  3 5 2   7 4 6   1 9 8
  9 7 4   8 5 1   3 2 6

This sudoku has a solution and the solution is unique
./sudoku sudoku-easy.txt  18,63s user 0,02s system 94% cpu 19,704 total


Nessuna dipendenza è richiesta a parte la libreria C++ standard e un compilatore C++, il file .cpp viene compilato ogni volta insieme all'applicazione (in quanto l'implementazione dei template in C++ è fottutamente buggata e non è possibile fare in modo diverso), quindi basta includere l'header senza linkare nessuna libreria ai propri sorgenti e tutto fila liscio (la compatibilità per diversi ambienti di sviluppo e sistemi operativi dovrebbe quindi essere universale).

Link a GitHub:
http://github.com/BlackLight/libCSP--

Link diretto:
http://0x00.ath.cx/prog/libcsppp.tar.gz
http://blacklight.devio.us/libcsppp.tar.bz2

_________________
Immagine
Immagine


Top
 Profilo  
 
Messaggio da leggereInviato: mer 09 giu, 2010 1:36 pm 
Non connesso
Amministratore
Amministratore
Avatar utente

Iscritto il: lun 27 dic, 2004 10:32 am
Messaggi: 2614
Località: Ferrara
Ottima libreria Black!
Ma sopratutto ben tornato, è veramente tanto tempo che non ci si sente!

_________________
I'm so happy because today
I've found my friends ...
They're in my head

[NIRVANA - LITHIUM]
Il Blog del disperato: http://blog.orebla.it


Top
 Profilo  
 
Visualizza ultimi messaggi:  Ordina per  
Apri un nuovo argomento Rispondi all’argomento  [ 2 messaggi ] 

Tutti gli orari sono UTC + 1 ora


Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite


Non puoi aprire nuovi argomenti
Non puoi rispondere negli argomenti
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi inviare allegati

Cerca per:
Vai a:  
cron
Powered by phpBB® Forum Software © phpBB Group
Traduzione Italiana phpBBItalia.net basata su phpBB.it 2010
phpBB SEO