Newsgroup: it.scienza.informatica
Titolo: Euristica minconflicts per la soluzione di CSP.

Salve,
spero di non essere off topic con questo mio post, ma ho letto il 
manifesto e mi pare che si addica bene al gruppo...
Ordunque, mi sto accingendo ad implementare dei "programmilli" per 
l'esame di Intelligenza Artificiale che terrò il prossimo mese, ed uno 
di questi concerne la soluzione del problema delle N regine attraverso 
l'uso dell'euristica minconflicts.
Il problema è che, salvo un madornale (o banale, a seconda dei punti di 
vista) errore da parte mia, ho scoperto che ci sono alcune istanze del 
problema che non riescono ad essere risolte da tale euristica... ora, al 
corso non è stata fatta menzione del fatto che quest'euristica potesse 
fallire, quindi la cosa mi pare alquanto strana... Ho anche trovato su 
internet un sorgente che implementa lo stesso algoritmo, e lo fa in una 
maniera del tutto simile alla mia, ovvero come da "manuale", e 
puntualmente fallisce su particolari istanze del problema.
Ora, le regine vengono piazzate sulla scacchiera su colonne differenti, 
per cui la scacchiera è convenientemente rappresentata da un'array di 
interi, i cui indici rappresentano le colonne, ed i cui elementi 
contengono il numero della riga nella quale si trova la regina 
corrispondente ad una particolare colonna.
Ad esempio, l'array {3, 5, 2, 0, 6, 4, 7, 1} rappresenta la seguente 
scacchiera (la posizione (0,0) è in alto a sinistra, cone nella migliore 
tradizione computeristica ;-) ) :
+-+-+-+-+-+-+-+-+
| | | |o| | | | |
+-+-+-+-+-+-+-+-+
| | | | | | | |o|
+-+-+-+-+-+-+-+-+
| | |o| | | | | |
+-+-+-+-+-+-+-+-+
|o| | | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | |o| | |
+-+-+-+-+-+-+-+-+
| |o| | | | | | |
+-+-+-+-+-+-+-+-+
| | | | |o| | | |
+-+-+-+-+-+-+-+-+
| | | | | | |o| |
+-+-+-+-+-+-+-+-+
Ora, per chi non lo sapesse - e sperando di non sbagliarmi, l'euristica 
minconflicts, una tipica euristica di "riparazione", lavora in questo modo:
1) Si dispongono sulla scacchiera tutte le regine (o, nel caso più
    generale, si assegnano alle variabili del problema dei valori
    qualsiasi, presi dal loro dominio)
2) si procede, iterativamente, a modificare la posizione di ciascuna
    regina che sia in "conflitto" con almeno un'altra regina, dove per
    "conflitto" si intende che si trova in una posizione che non siddisfa
    il vincolo di "non mangiare" un'altra regina. La regina dovrà essere
    spostata nella riga nella quale ci sono meno conflitti possibili.
3) Nel caso in cui più di una posizione produce lo stesso numero di
    conflitti, allora si sceglie a caso tra di esse.
Ecco, sia il libro, sia la prof, sia qualsiasi altra risorsa che io 
abbia avuto modo di consultare dicono che così procedendo si perverrà, 
prima o poi, ad una soluzione del problema. Il punto è, che non è sempre 
così - a meno di miei errori.
Ad esempio, proprio la scacchiera mostrata sopra, non /sembra/ ammettere 
soluzioni tramite l'euristica minconflicts. Provare per credere.
Qualcuno sa darmi qualche delucidazione al riguardo? Confermate che la 
scacchiera di cui sopra non ammette soluzioni tramite minconflicts? 
Quallo che succede è che si crea un loop, e sempre gli stessi pezzi 
vengono mossi sempre nelle stesse posizioni, avanti e indietro, e 
proprio "non se ne esce". Un altro stato iniziale che causa tale 
problema è il seguente: {6, 0, 3, 1, 7, 5, 2, 4 }.
Il mio programma non lo posto, ma posto un link al programma simile al 
mio di cui ho parlato prima: 
http://hackmode.org/~alex/nqueens.c
Speranzoso,
Fabio

~\/~ "Fabio" == Fabio  <do...@spam.please> writes:
Fabio> Salve,
Fabio> spero di non essere off topic con questo mio post, ma ho letto
Fabio> il manifesto e mi pare che si addica bene al gruppo...
welcome, ho visto che purtroppo nessuno ti ha risposo.
L'intellienza artificiale che e` collegata dal libro citato dal
prgramma di ~alex da te citato, e` un argomento delicato:
dal 1995 al 2002 sembra frenare, ma dal 2002 noto che riparte con
la presenza di libri statunitensi in versione IE (International Edition)
oltre alla versione limitata per USA e Canada. Se poi contengono infomazioni
"quasi giuste" e` il caso di meditare, posto che se ne abbia voglia.
Fabio> Ordunque, mi sto accingendo ad implementare dei "programmilli"
Fabio> per l'esame di Intelligenza Artificiale che terrò il prossimo
Fabio> mese, ed uno di questi concerne la soluzione del problema delle
Fabio> N regine attraverso l'uso dell'euristica minconflicts.
Fabio> Il problema è che, salvo un madornale (o banale, a seconda dei
Fabio> punti di vista) errore da parte mia, ho scoperto che ci sono
Fabio> alcune istanze del problema che non riescono ad essere risolte
Fabio> da tale euristica... ora, al corso non è stata fatta menzione
Fabio> del fatto che quest'euristica potesse fallire, quindi la cosa
Fabio> mi pare alquanto strana... Ho anche trovato su internet un
Fabio> sorgente che implementa lo stesso algoritmo, e lo fa in una
Fabio> maniera del tutto simile alla mia, ovvero come da "manuale", e
Fabio> puntualmente fallisce su particolari istanze del problema.
Fabio> Ora, le regine vengono piazzate sulla scacchiera su colonne
Fabio> differenti, per cui la scacchiera è convenientemente
Fabio> rappresentata da un'array di interi, i cui indici rappresentano
Fabio> le colonne, ed i cui elementi contengono il numero della riga
Fabio> nella quale si trova la regina corrispondente ad una
Fabio> particolare colonna.
Fabio> Ad esempio, l'array {3, 5, 2, 0, 6, 4, 7, 1} rappresenta la
Fabio> seguente scacchiera (la posizione (0,0) è in alto a sinistra,
Fabio> cone nella migliore tradizione computeristica ;-) ) :
la (migliore) tradizione invece precede la grafica, quindi le
coordinate non sono x,y in random access, ma prima c'e` la riga
poi la colonna, cioe` se devi stampare {3, 5, 2, 0, 6, 4, 7, 1}
su terminale e` piu` diretto per righe (ma e` una finezza)
      0   1   2   3   4   5   6   7
    +- - - - - - - - - - - - - - - - 
3   : 2 : 2 : 2 :#1#: 3 : 1 : 2 : 1 |
    +- - - - - - - - - - - - - - - - 
5   : 2 : 2 : 4 : 3 : 2 :#0#: 1 : 2 |
    +- - - - - - - - - - - - - - - - 
2   : 1 : 4 :#0#: 2 : 3 : 2 : 3 : 2 |
    +- - - - - - - - - - - - - - - - 
0   :#1#: 2 : 2 : 3 : 2 : 3 : 3 : 3 |
    +- - - - - - - - - - - - - - - - 
6   : 2 : 2 : 2 : 2 : 3 : 3 :#0#: 2 |
    +- - - - - - - - - - - - - - - - 
4   : 1 : 2 : 2 : 2 :#0#: 3 : 2 : 2 |
    +- - - - - - - - - - - - - - - - 
7   : 3 : 1 : 2 : 3 : 2 : 2 : 2 :#0#|
    +- - - - - - - - - - - - - - - - 
1   : 1 :#0#: 2 : 2 : 2 : 1 : 3 : 2 |
    +- -+- -+- -+- -+- -+- -+- -+- -+
i cancelletti sono dove c'e` la regina, i numeri al centro delle
caselle sono relativi ai conflitti per uno spostamento orizzontale
della regina sulla riga specifica (colonna per te)
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | | |o| | | | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | | | | | | |o|
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | |o| | | | | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> |o| | | | | | | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | | | | |o| | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | |o| | | | | | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | | | |o| | | |
Fabio> +-+-+-+-+-+-+-+-+
Fabio> | | | | | | |o| |
Fabio> +-+-+-+-+-+-+-+-+
abbiamo le rappresentazioni trasposte, ma il concetto non cambia,
Fabio> Ora, per chi non lo sapesse - e sperando di non sbagliarmi,
Fabio> l'euristica minconflicts, una tipica euristica di
Fabio> "riparazione", lavora in questo modo:
puo` essere
Fabio> 1) Si dispongono sulla scacchiera tutte le regine (o, nel caso
Fabio>    più generale, si assegnano alle variabili del problema dei
Fabio>    valori qualsiasi, presi dal loro dominio)
Fabio> 2) si procede, iterativamente, a
Fabio>    modificare la posizione di ciascuna regina che sia
Fabio>    in "conflitto" con almeno un'altra regina,
Fabio>    dove per "conflitto" si intende che si trova in una posizione
Fabio>    che non siddisfa il vincolo di "non mangiare" un'altra regina.
Fabio>    La regina dovrà essere spostata nella riga nella quale ci sono
Fabio>    meno conflitti possibili.
Fabio> 3) Nel caso in cui più di una posizione produce lo stesso
Fabio>    numero di conflitti, allora si sceglie a caso tra di esse.
Fabio> Ecco, sia il libro, sia la prof, sia qualsiasi altra risorsa
Fabio> che io abbia avuto modo di consultare dicono che così
Fabio> procedendo si perverrà, prima o poi, ad una soluzione del
Fabio> problema.
Procedendo come hai descritto non si arriva sempre "prima o poi"
alla soluzione. Se nel libro e` scritto cosi` e` sbagliato.
Ma d'altra parte dici che e` classificato come metodo euristico
Fabio> Il punto è, che non è sempre così - a meno di miei errori.
non avendo il libro di cui parli non vedo i tui possibili errori
(credo di tua interpretazione della classe di problemi che risolve),
comunque procedendo per righe, le ulteriori configurazioni successive
possibili che l'algoritmo esplora per l'esempio sono in aggiunta solo:
    +- - - - - - - - - - - - - - - - 
5 : : 2 : 2 : 2 : 1 : 3 :#1#: 2 : 1 |  * cambiamento solo in questa riga
    +- - - - - - - - - - - - - - - - 
5 : : 2 : 2 : 3 : 2 : 2 :#1#: 2 : 2 |
    +- - - - - - - - - - - - - - - - 
2 : : 1 : 3 :#0#: 2 : 3 : 2 : 3 : 3 |
    +- - - - - - - - - - - - - - - - 
0 : :#0#: 2 : 3 : 2 : 2 : 4 : 2 : 3 |
    +- - - - - - - - - - - - - - - - 
6 : : 2 : 3 : 2 : 1 : 3 : 4 :#0#: 1 |
    +- - - - - - - - - - - - - - - - 
4 : : 2 : 2 : 2 : 1 :#0#: 4 : 2 : 2 |
    +- - - - - - - - - - - - - - - - 
7 : : 3 : 1 : 2 : 2 : 2 : 3 : 2 :#0#|
    +- - - - - - - - - - - - - - - - 
1 : : 1 :#0#: 2 : 1 : 2 : 2 : 3 : 2 |
    +- -+- -+- -+- -+- -+- -+- -+- -+
    +- - - - - - - - - - - - - - - - 
7 : : 2 : 2 : 2 : 1 : 3 : 1 : 2 :#1#|  * cambiamento solo in questa riga
    +- - - - - - - - - - - - - - - - 
5 : : 2 : 2 : 3 : 2 : 1 :#0#: 2 : 3 |
    +- - - - - - - - - - - - - - - - 
2 : : 1 : 3 :#0#: 1 : 3 : 2 : 3 : 3 |
    +- - - - - - - - - - - - - - - - 
0 : :#0#: 2 : 2 : 2 : 3 : 3 : 2 : 4 |
    +- - - - - - - - - - - - - - - - 
6 : : 2 : 2 : 2 : 2 : 3 : 3 :#0#: 2 |
    +- - - - - - - - - - - - - - - - 
4 : : 1 : 2 : 3 : 1 :#0#: 3 : 2 : 3 |
    +- - - - - - - - - - - - - - - - 
7 : : 3 : 2 : 2 : 2 : 2 : 2 : 2 :#1#|
    +- - - - - - - - - - - - - - - - 
1 : : 2 :#0#: 2 : 1 : 2 : 1 : 3 : 3 |
    +- -+- -+- -+- -+- -+- -+- -+- -+
dove nella prima riga la regina passa dalla posizione 3 alla 5 e alla 7
per parita` di conflitti (1), tutte le altre regine "_pare_ sconveniente
spostrle orizzontalmente" perche` sono nella posizione di minimi conflitti,
l'algoritmo minconf (senza accorgimenti) da te descritto non le sposta.
Fabio> Ad esempio, proprio la scacchiera mostrata sopra, non /sembra/
Fabio> ammettere soluzioni tramite l'euristica minconflicts. Provare
Fabio> per credere.
confermo (senza il "sembra")
Fabio> Qualcuno sa darmi qualche delucidazione al riguardo?
Fabio> Confermate che la scacchiera di cui sopra non ammette soluzioni
Fabio> tramite minconflicts?
La configurazione iniziale ha la speialita` di essere in conflitto
_solo_ in una diagonale, quindi qualunque spostamento di una regina
per righe o colonne avra` almeno un conflitto su riga o colonna,
piu` eventuali altri conflitti in diagonale. Bisognerebbe passare per
configurazioni con un numero maggiore conflitti per uscire dall'enpasse.
Fabio> Quallo che succede è che si crea un loop, e sempre gli stessi
Fabio> pezzi vengono mossi sempre nelle stesse posizioni, avanti e
Fabio> indietro, e proprio "non se ne esce". Un altro stato iniziale
Fabio> che causa tale problema è il seguente: {6, 0, 3, 1, 7, 5, 2, 4 }.
Fabio> Il mio programma non lo posto, ma posto un link al programma
Fabio> simile al mio di cui ho parlato prima:
Fabio> 
http://hackmode.org/~alex/nqueens.c
Fabio> Speranzoso, Fabio
il problema alla base della logica di minconf e` che
falso AND falso   non e` "piu` falso" di
falso
(pensato sul rispetto dei vincoli)
quando i vincoli sono dipendenti da configurazioni "sperimentali"(ossia
non soluzioni definitive) cioe` sono del tipo che modificando la
configurazione per far rispettare un vincolo, se ne possono violare
altri, e` un azzardo euristico cercare di aggiustare la soluzione
limitandosi a quella immediatamente piu` "vicina" (vicina nel senso sbagliato
ma intuitivo che commette un numero inferiore di violazioni dei vincoli).
Saluti,
MARco
-- 
xref: 
http://mar.i.am/~u16613.26157/it.scienza.informatica/8regine,it
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14