Newsgroup: it.comp.ia
Titolo: Euristica minconflicts per la soluzione di CSP.

Salve,
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



 l'uso dell'euristica minconflicts.
[Snip]
Ciao
hai provato a inserire nel tuo codice un controllo anti-ciclaggio?
dopo un certo numero di iterazioni "cicliche", fai in modo
che il programma prenda un'altra strada tra quelle possibili (ad
esempio,
invece che prendere la posizione che da meno conflitti, ne prendi 
un'altra che non soddisfa questa regola). Questo potrebbe consentirti
di uscire dallo stallo.
Non conoscevo l'euristica minconflicts, ma il fatto che un'euristica 
fallisca mi sembra abbastanza "normale", nel
senso che in genere le euristiche sono basate sul buon senso, e quindi
non è detto che funzionino sempre (non è un'equazione di 2° grado 
per intenderci, per la quale le regole di risoluzione ci sono e valgono
sempre).
Ciao
R
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 hai provato a inserire nel tuo codice un controllo anti-ciclaggio?
In verità, no. Non l'ho fatto per il semplice fatto che non è stata 
fatta menzione della sua necessità, nè sul libro, nè al corso, ma visto 
che mi son ritrovato in questo problema, io stesso sono pervenuto alla 
conclusione che il MC hill-climbing non è proprio quello che mi serve.
Con una ricerca più dettagliata in rete poi ho trovato questo: 
http://kti.ms.mff.cuni.cz/~bartak/constraints/stochastic.html
Discute proprio del fatto che il MC, assolo, non riesce ad uscire dai 
minimi locali, e quindi bisogna adottare qualche altra strategia.
Grazie!
Fabio

 minimi locali, e quindi bisogna adottare qualche altra strategia.
Con una semplicissima modifica al mio algoritmo ho implementato l'MC 
Random-Walk, è il tutto ha magicamente funzionato! :-)
Fabio