Post on 06-Feb-2018
Intelligenza Artificiale
marco ernandesemail: ernandes@dii.unisi.it
Gennaio – Aprile 2007
Intelligenza Artificiale - CSP 1/52
Constraint SatisfactionConstraint Satisfaction
Intelligenza Artificiale - CSP 2/52
PS vs. CSPNel PS tutto ruota intorno al concetto di stato.
Nel PS tutto è problem-specific (o state-specific) SCS(n), g(n), h(n), t(n), S0.
Gli stati sono dei veri “black box” senza struttura interna.
La terminazione controlla se lo stato COINCIDECOMPLETAMENTE con uno degli stati finali.
Il CSP invece cerca di “aprire” gli stati e generalizzarnela rappresentazione interna.
Intelligenza Artificiale - CSP 3/52
Il CSP si occupa, tipicamente di Problemi di assegnazione CONSTRAINT SATISFACTION PROBLEMS
Nei problemi di assegnazione non c’è l’interesse di ottenere un percorso risolvente non c’è (generalmente) un costo associato ad ogni passo non si possiede uno stato obiettivo (possedere uno stato
obiettivo coincide con l’aver risolto il problema)
Il PS fornisce un framework per affrontare problemi dipercorso, il CSP fornisce tecniche per problemi diassegnazione: CONSTRAINT SATISFACTION PROGRAMMING
CSP vs. PS
Intelligenza Artificiale - CSP 4/52
Esempi di CSP
T
U
N
O
NF
I
5
43
21
otto+ due
dieci Diritto privatoStoria 111:00-12:00
Storia 2Diritto pubblico9:00-10:00
Diritto privato
1A
Politica comp.10:00-11:00
2A aulaora
Intelligenza Artificiale - CSP 5/52
CSP(problems & programming)
CSP
CS-ProgrammingMetodo per formalizzare eattaccare un problema CS.
CS-ProblemsTipologia di problemi (CS)
La differenza tra PS e CSPpuò essere sfumata: un CSP
può al limite essereformalizzato come PS e
attaccato di conseguenza.
Intelligenza Artificiale - CSP 6/52
Definizione di CSPUn problema di CSP (soddisfacimento vincoli) èdefinito da: un set di variabilivariabili: X1, X2,…, Xn
un set di vincolivincoli (constraints): C1, C2,…, Cm
ogni variabile Xi è associata ad un dominio Di divalorivalori ammissibili v
ogni vincolo Ci agisce su di un subset di variabili especifica le combinazioni di assegnamenti legali.
La soluzione di un CSP è data da un assegnamentocompleto (per ogni variabile Xi c’è un valore estrattoda Di) senza violazione dei vincoli.
Intelligenza Artificiale - CSP 7/52
Variabili: 64 Xij con i = da 1 a 8, j = da 1 a 8
Dominio delle variabili D = {1,0}
Vincoli: Xij = 1 SE Xik = 0 per tutti k da 1 a 8, k ≠ j () Xij = 1 SE Xkj = 0 per tutti k da 1 a 8, k ≠ i () Xij = 1 SE Xi+h,j+h = 0, Xi-h,j-h = 0 per tutti i±h ()
da 1 a 8, h ≠ 0
CSP es: 8-Regine (I)
x1,jx2,jx3,jx4,jx5,jx6,j
x7,jx8,j
xi,1 xi,2 xi,3 xi,4 xi,5 xi,6 xi,7 xi,8
Intelligenza Artificiale - CSP 8/52
Variabili: 8 Xi con i = da 1 a 8
Dominio delle variabili D = {1,2,…,8}
Vincoli: Xi = k SE Xj ≠ k per tutti j da 1 a 8, j ≠ i ()
Xi = k SE Xi±h ≠ k±h per tutti i±h da 1 a 8, h ≠ 0 ()
CSP es: 8-Regine (II)
x1x2x3x4x5x6
x7x8
D = 1 2 3 4 5 6 7 8
Intelligenza Artificiale - CSP 9/52
Variabili: WA, NT, Q, NSW, V, SA, T
Domini Di = {red, green, blue}
Vincoli: regioni adiacenti devono averecolori diversi:
es 1: color(WA) ≠ color(NT), es 2: color(WA,NT) da
{(red,green), (red,blue), (green,red),(green,blue), (blue,red), (blue,green)}
CSP es: Colorazione Mappe
Intelligenza Artificiale - CSP 10/52
CSP es: Criptoaritmetica
two+ two
four
Variabili: F, T, U, W, R, O (+ Xd, Xc, Xm, i riporti)
Domini Di = {1,2,3,4,5,6,7,8,9,0}
Vincoli: ogni lettera deve essere associata ad un valorediverso e la somma tra due lettere in colonna (+ il riportodella somma precedente) deve essere uguale al valoredella lettera “risultato”
Alldiff(F, T, U, W, R, O) O+O = R +10 * Xd
Xd +W+W = U + 10 * Xc
Xm = F
Intelligenza Artificiale - CSP 11/52
CSP es: Soddisfacibilità (SAT)
(x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ ¬x2 )
Variabili: x1,x2,x3
Domini Di = {true,false}
Vincoli: il valore di ogni clausola deve essere TRUE
(x1 ∨ x2 ∨ x3) = TRUE (¬x1 ∨ x2 ∨ x3) = TRUE (x1 ∨ ¬x2) = TRUE
Intelligenza Artificiale - CSP 12/52
CSP e vincoliConstraint Network (CN): la rete di relazioni checoinvolge vincoli, variabili e valori.
Arità dei vincoli k(C) Vincoli unari: k(C) = 1, il vincolo agisce solo su una variabile Vincoli binari: k(C) = 2, il vincolo agisce su una coppia di variabili Vincoli n-ari: k(C) = n, il vincolo agisce su più variabili
contemporaneamente (es: N-Regine ogni variabile con valore ≠)
CSP-binari possiedono al max. vincoli binari e sipossono descrivere con un grafo dei vincoli.
I CSP di ordinemaggiore si
descrivono conipergrafi.
Intelligenza Artificiale - CSP 13/52
CSP e complessità
CSP finiti: dominio finito di valori
CSP infiniti: dominio infinito di valori(problemi affrontati dalla programmazione lineare)
SAT: il SAT è un problema CSP finito e ogniCSP è riducibile al SAT, quindi:
La complessità dei CSP finiti è esponenziale(es: Knapsack Problem 2n)
Intelligenza Artificiale - CSP 14/52
Intro al CS-ProgrammingIl Constraint Programming: insieme di metodologie che miranoalla risoluzione dei CSP e richiede 3 scelte progettuali
modello (definito con framework CSP) algoritmo euristica
Ognuna di queste scelte influenza l’efficienza della risoluzione(es: il modello fa aumentare o diminuire le dimensioni della CN).
Gli algoritmi si dividono in 2 categorie:
Metodi Costruttivi Metodi Riparativi
Intelligenza Artificiale - CSP 15/52
Metodi CostruttiviSi parte da uno stato privo di assegnamenti e si cercadi immettere valori senza violare i vincoli.
In questo caso si formalizza un CSP come un PS e sirisolve attraverso tecniche di Search.
Stato: assegnamento di valori dal dominio Di a variabili Xi
X0: assegnamento vuoto {} Successor function: un valore per ogni var non
assegnata consistente con quelle già assegnate Goal test: assegnamento completo senza violazione di
vincoli Costo di cammino: costante per ogni step
Intelligenza Artificiale - CSP 16/52
Metodi Costruttivi – vantaggiCommutatività del CSP: l’ordine degli assegnamenti èindifferente (non interessa il percorso), quindi: SCS: genera nodi da una sola variabile (qualsiasi) Non c’è bisogno di memorizzare il cammino Non c’è bisogno di calcolare il costo di cammino
La profondità dell’albero è finita e conosciuta: d = numero di variabili da assegnare Gli algoritmi depth-first sono i più usati
Le soluzioni proposte non violano i vincoliGrosso problema: le grandi dimensioni che puòassumere Di che definisce il branching factor
… e svantaggi
Intelligenza Artificiale - CSP 17/52
Backtracking SearchE’ una ricerca Depth-First (per problemi CSP)in cui si espande facendo assegnamenti aduna sola variabile per volta.
E’ l’algoritmo base per i CSP.1. assignment = {};2. STACK.insert(assignment);3. do
if (STACK.isEmpty()) return failure;assignment = STACK.remove();if (complete(assignment)) return assignment;STACK.insertAll (expand(assignment));
while (true);
Intelligenza Artificiale - CSP 18/52
Backtracking - simulazioneEmpty assignment
1st variable
2nd variable
3rd variable
Assignment = {}Assignment = {(X1=v11)}Assignment = {(X1=v11),(X2=v21)}Assignment = {(X1=v11),(X2=v21),(X3=v31)}Assignment = {(X1=v11),(X2=v21)}Assignment = {(X1=v11),(X2=v21),(X3=v32)}Assignment = {(X1=v11),(X2=v21)}Assignment = {(X1=v11)} Assignment = {(X1=v11),(X2=v22)}
Intelligenza Artificiale - CSP 19/52
Migliorare il backtracking (I)
Il framework CSP permette di ottenereeuristiche generali problem-independentconsiderando il concetto di espansione.
Espandere vuol dire assegnare dei valoriad una variabile a scelta senza violare ivincoli.
La ricerca Depth-First semplice non è molto efficiente.(Come già visto in PS).
Nel PS si introduce un’informazione problem-specific(euristiche) per migliorare le prestazioni della ricerca.
Intelligenza Artificiale - CSP 20/52
Dal concetto di espansione:
La scelta della variabile da espandere è determinante! L’ordine d’inserimento dei valori nello STACK è
determinante!
Le euristiche general-purpose del Constraint Programmingrispondono quindi alle seguenti domande:
1. Quale variabile scegliere per l’espansione?2. In che ordine provare i valori?3. E’ possibile scoprire in anticipo dei fallimenti?
Migliorare il backtracking (II)
Intelligenza Artificiale - CSP 21/52
Scelta della Variabile (I)Minimum Remaining Values (MRV) Heuristic: Si sceglie la variabile con il minor numero di valori legali
rimanenti.
MRV è anche detta: Most Constrained Variable Heuristic Fail First Heuristic Cheapest First Heuristic
Vantaggi: Riduce il branching factor (da cui cheapest first) Porta più facilmente ad un fallimento superficiale (da cui fail
first) con conseguente backtracking e quindi aiuta a potarel’albero.
Intelligenza Artificiale - CSP 22/52
Scelta della Variabile (II)Allo stato X0 di questo esempio ogni variabile ha lostesso numero di valori legali.
In questo caso conviene scegliere la variabile coinvoltain più vincoli
Riduce il branching factor delle scelte future
Si chiama Degree Heuristic ed è spesso associata aMRV (funge da tie-breaker).
Intelligenza Artificiale - CSP 23/52
Scelta del ValoreLeast Constraining Value (LCV) Heuristic:
Preferisci i valori che lasciano il più grande sottoinsieme divalori legali per le variabili non assegnate.
E’ il criterio di ordinamento dell’espansione
L’idea è che si danno maggiori possibilità alla ricercadi trovare futuri assegnamenti legali.
Mantiene 1 valore per SA
Mantiene 0 valori per SA
Intelligenza Artificiale - CSP 24/52
Evitare i fallimentiLa LCV Heuristic richiede il controllo previo delnumero di valori rimanenti per variabile.
Per fare questo si adotta il forward checking.
Il Forward checking può essere utilizzatocontemporaneamente per anticipare i dead-end.
Per ogni variabile non-assegnata si tiene tracciadel subset di valori ancora legali.
Ogni volta che v è assegnato a Xi: per ogni variabile non ass. Xj connessa a Xi da un
vincolo si cancella dal dominio Dj ogni valoreinconsistente con v
Intelligenza Artificiale - CSP 25/52
E’ applicabile all’interno dell’algoritmo di backtrackingcome tecnica per stabilire quando tornare indietro.
Ogni volta che si raggiunge uno stato non-consistente(con almeno una variabile priva di valori rimasti node-consistency) si effettua il backtracking.
Forward Checking
Intelligenza Artificiale - CSP 26/52
RGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Forward Checking(es: colorazione grafo)
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 27/52
RGBRGBRGBRGBRGBRGBRRGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Forward checking rimuove il RED da NT e da SA
Forward Checking(es: colorazione grafo)
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 28/52
RGBGBRGBRGBGGBRRGBGBRGBRGBRGBGBRRGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Forward Checking(es: colorazione grafo)
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 29/52
RGBBBRBGBRRGBBRGBRBGBRRGBGBRGBRGBRGBGBRRGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Forward Checking(es: colorazione grafo)
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 30/52
RGBGBRGRGBGGBRRGBGBRGBRGBRGBGBRRGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Forward Checking(es: colorazione grafo)
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 31/52
TWA
NT
SA
Q
NSW
V
Forward Checking(es: colorazione grafo)
RGBBGRBGBRRGBBRGBRBGBRRGBGBRGBRGBRGBGBRRGBRGBRGBRGBRGBRGBRGBTSAVNSWQNTWA
TWA
NT
SA
Q
NSW
V
Nell’esempio nonvengono adottatele altre euristiche
Intelligenza Artificiale - CSP 32/52
Arc Consistency(Waltz, ’72)
Forward Checking stabilisce un criterio di stop, ma nonprevede i fallimenti con anticipo.In figura, per esempio, NT e SA sono entrambe Blu:nessuna soluzione è raggiungibile!Arc-consistency: per evitare di dead-end ci dobbiamoassicurare che, per ogni vincolo, rimanga un insieme divalori assegnabili alle variabili vincolate.
Intelligenza Artificiale - CSP 33/52
Contraint PropagationArc-consistency può essere usato come controllo asupporto del backtracking dopo ogni assegnamento.Individua i dead-end prima di Forward Checking.
Contraint Propagation: L’approccio può però esseregeneralizzato facendo ripetutamente il controllo di arc-consistency, rimuovendo i valori che non la garantiscono.
Intelligenza Artificiale - CSP 34/52
Contraint PropagationArc-consistency può essere usato come controllo asupporto del backtracking dopo ogni assegnamento.Individua i dead-end prima di Forward Checking.
Contraint Propagation: L’approccio può però esseregeneralizzato facendo ripetutamente il controllo di arc-consistency, rimuovendo i valori che non la garantiscono.
Intelligenza Artificiale - CSP 35/52
Algoritmi di Arc Consistency
Invece di affrontare un CSP facendo search sullevariabili, si effettua un search sui vincoli (gli archidella CN). Si parte da una configurazione con i domini delle variabili
“pieni”. Se un arco è inconsistente lo si rende consistente
rimuovendo i valori inconsistenti. L’arco xi xj (arco diretto) è definito consistente
iff: ∀v ∈ Di ∃v’ ∈ Dj cioè per ogni valore di Vi esiste unassegnamento legale di Vj.
Quando si è reso consistente ogni arco allora si ritornal’assegnamento delle variabili come soluzione.
Intelligenza Artificiale - CSP 36/52
AC-3(Mackworth, ’86)
ARCS = {tutti gli archi della CN};while (!ARCS.isEmpty())
(Xi,Xj) ARCS.remove();if (REMOVE-INC-VALUES(Xi,Xj)==true)
for all Xk in NEIGHBORS[Xi]ARCS.put(Xk, Xi);
boolean removed = false;for all v in DOMAIN(Xi)
if no value v’ in DOMAIN(Xj) satisfies (Xi,Xj)DOMAIN(Xi).remove(v);removed = true;
return removed;
REMOVE-INC-VALUES(Xi,Xj)
AC-3
Intelligenza Artificiale - CSP 37/52
K-ConsistencyGeneralizzazione del concetto di arc-consistency da coppie a gruppi di variabili:
Un grafo è K-consistente se per ogni assegnamento legale diK-1 variabili esiste sempre un valore legale per ogni K-esimavariabile Vk nel grafo dei vincoli.
Strong k-consistency = i-consistency per ogni i da 1 a k Node-consistency = strong 1-consistency Arc-consistency = strong 2-consistency Path-consistency = strong 3-consistency
Un CSP con N variabili che sia strongly N-consistent, èrisolvibile senza backtracking.
Un CSP strongly K-consistent, è risolvibile senza backtrackingse si trova l’ordinamento di variabili appropriato.
Intelligenza Artificiale - CSP 38/52
Abbiamo sin qui visto tecniche di look-ahead chemirano ad evitare i dead-end (profondi).
Possiamo anche migliorare il backtracking contecniche di look-back: Backjump Constraint recording
Backtracking: si torna indietro alla variabileprecedentemente assegnata
Backjumping: si torna indietro direttamente allavariabile che a creato problemi.
Migliorare il backtracking (III)
Intelligenza Artificiale - CSP 39/52
BackjumpingMotivazione: il motivo di un fallimento non si trova per forzanell’ultima coppia di assegnamenti, ma in assegnamentiprecedenti.
Backjumping = non-chronological backtracking.
87654321
x8
x7
x6
x5
x4
x3
x2
x1
Fare backtracking a x5 non cambianiente. Si rimane in un dead-end.
Per un backtracking efficace vascelta un’altra variabile (secondo uncriterio a scelta es: conflict set).
Intelligenza Artificiale - CSP 40/52
Conflict SetSi tiene traccia in CS[xi] delle variabili assegnate, ancheuna sola, che entrano in conflitto con qualche valorepresente in Di. Nogood variables.
Directed-conflict Backtracking
torna direttamente all’assegnamento (+ recente) causa deldead-end.
si rimuovono le decisioni intermedie e si aggiorna CS[]
1
11111
8765432x8
x7
x6
x5
X4
x3
x2
x1
3213423{1,2,3,4}
3212{1,2,3}
1{1}
2
2
4
2
312{1,2,3,4}
1{1,2}
{} 13524
Directed-conflictBacktracking
Ha il vantaggiodi accelerare il
processo dibacktracking
Intelligenza Artificiale - CSP 41/52
Dynamic Backtracking(Ginsberg, ’90, ’92)
E’ un non-chronological backtracking (backjumping) che: torna alla variabile nogood causa del dead-end NON rimuove le decisioni intermedie, ma ricostruisce
l’albero eliminando un solo assegnamento
X1 = 1
X2 = 3
X3 = 5
X4 = 2
X5 = 4
X1 = 1
X2 = 3
X3 = 5
X5 = 4
Stabilire la variabile“effettivamente”
causa del dead-endnon è sempre ovvio
Intelligenza Artificiale - CSP 42/52
Dynamic Backtracking(es: crossword generation)
LUNI
5
43
21NI
5
43
21
LUN
FI
5
43
21
NUL
NUT
SAG
NAG
2D
ATLAIS
DOIFTOTADIN
NOITGOFUNAS
4D1D5A3A1A
5
43
21
LUN
NFI
5
43
21
TUN
NFI
5
43
21
O1A 2D 1D 2A 5A
Intelligenza Artificiale - CSP 43/52
Dynamic Backtracking(es: crossword generation)
(Ginsberg, ’90) ha usato: euristica MRV (cheapest-first):
euristica LCV nella formula: min-look = 10 sul backtracking Schema di hashing (degli ingressi del dizionario) per
calcolare rapidamente il dominio (matching dei pattern)
Schemi grandi (15x15) riempiti in pochi secondi!…
……00010001001…00000000011…C
……10001100000…00000001100…B
…01001000001…00100010100…11110000000…A
4° position3° position2° position1° position 10001100000… ilvalore k è alto sel’ingresso k del dizionariocontiene la data lettera ialla data posizione j
x! argmini=1"N
#Di
w ! argmaxw!Dx
#cons (Dy,w)y! cross(x)
%
Intelligenza Artificiale - CSP 44/52
Euristiche e “discrepanze”In molti problemi reali lo spazio di ricerca è talmentevasto che si deve far ricorso a delle euristiche: Suggeriscono un assegnamento da fare Dipendono strettamente dal problema (es: nella generazione
di cruciverba → preferire le parole con vocali o lettere comuni).
Gli algoritmi devono gestire l’errore dell’euristica: seguire sempre l’euristica può portare ad una inconsistenza gli errori si verificano più spesso nelle prime fasi della ricerca Il numero di errori dell’euristica è tipicamente ridotto
Si usa il concetto di “discrepanza”: assegnamento peril quale non viene seguito il suggerimento dell’euristica. L’idea è che seguendo le indicazioni dell’euristica, tranne in
poche occasioni (discrepanze), si può arrivare rapidamente aduna soluzione.
Intelligenza Artificiale - CSP 45/52
Limited Discrepancy Search(Harvey, Ginsberg ‘95)
LDS è un algoritmo iterativo.
Ad ogni iterazione vieneassociato un numeromassimo di discrepanze d.Se ad una iterazione non èstato possibile trovare unasoluzione, la soglia didiscrepanze d vieneaumentata e si riparte.Ad ogni iterazione sieffettuano tutte le ricerchecon d discrepanze, iniziandocon quelle che hanno lediscrepanze più superficiali.
Euristica = “go left”
Intelligenza Artificiale - CSP 46/52
Metodi Riparativi(Ricerca Locale)
Si parte da uno stato “pieno”: cioè con tutte le variabiliassegnate.
Per rientrare nel framework CSP: Si consentono stati con violazione dei vincoli Gli operatori sono di riassegnamento di valori a variabili e non
di assegnamento.
Si usano tecniche di ottimizzazione locale: Min-Conflicts Hill-climbing Tabu Search Simulated annealing Algoritmi Genetici
Intelligenza Artificiale - CSP 47/52
Metodi Riparativi vs. Costruttivi
Gli algoritmi costruttivi funzionano bene soprattutto suCSP-binari (o con pochi vincoli e pochi valori): Es: complex di AC-3 = O(nk3) dipende da k=valori e n=archi
Diventano poco gestibili con Constraint Networks adarità maggiore e con molti valori. Es: N-regine con N > 106.
Gli algoritmi riparativi, locali, forniscono meno garanzieteoriche, ma nel caso di problemi molto complessirisultano efficienti nella pratica.
Gli algoritmi riparativi non sono completi. Si tratta infattidi algoritmi “locali”.
Intelligenza Artificiale - CSP 48/52
Min-Conflicts(Minton, ‘92)
Si sceglie una configurazione iniziale (random)Ripeti: Prendi una variabile xi in conflitto (random) Assegna a xi il valore che minimizza il numero di conflitti Se la configurazione è valida allora RETURN
ASSEGNAZIONE, altrimenti CONTINUE
12
33223
22
22
202
Intelligenza Artificiale - CSP 49/52
Min-Conflicts - vantaggiE’ estremamente efficace per problemi come quello delle n-regine.Risolti problemi di milioni di regine (con solo ~50 iterazioni partendoda assegn. random!). Con algoritmi costruttivi è impossibile.
E’ estremamente utile (ed efficace) in problemi CSP “reali”, comequelli di scheduling:
Perché se c’è una variazione nei vincoli (es: cambio di orario di unprofessore nel problema del Class Scheduling) non si devericominciare da capo.
E’ quindi un sistema che può far fronte ad un ambiente dinamico:online-CSP.
Ha risolto il problema dello scheduling delle osservazioni delTelescopio Hubble.
Può essere usato in forma iterativa o in associazione con algoritmilocali come simulated-annealing
Intelligenza Artificiale - CSP 50/52
Simulated AnnealingL’approccio di riparazione ha due modelli puri opposti: Hill-climbing: si segue uno schema di costante ascesa. Migliora gli
stati ma si ferma nei massimi locali (si può ricominciare da uno statoiniziale diverso: Iterative Hill-Climbing)
Random Walk: è completo, ma non cerca di migliorare gli stati.
Simulate Annealing: generalizzazione che combina l’hill-climbingcon il random walk per ottenere completezza ed efficenza:
Invece di fare la migliore scelta se ne fa una random. IF la scelta migliora lo stato attuale allora si accetta. ALTRIMENTI la scelta è accettata con una probabilità < 1 La probabilità è relata al peggioramento prodotto: exp(-Δ/T) Δ è dato dalla differenza di valore degli stati (peggioramento). T è la “temperatura” = se è alta si accettano molti peggioramenti Si tende a far decrescere la temperatura durante la ricerca.
Intelligenza Artificiale - CSP 51/52
Generalizzazione del CSP
Variabili, valori, vincoli (modello o “constraint network”)potrebbero avere pesi diversi:
1) Rilassamento peso vincoli (libertà di violare).2) Rilassamento peso variabili (libertà di non istanziare)3) Rilassamento peso valori (alcuni preferibili).
Questo si presenta quando:
casting di un problema dal mondo reale al dominio dei CSP non vi sono soluzioni con una constraint network hard-valued.
V-CSP: un peso su ogni elemento del modello
Crossword Solving = P-CSP (sottoinsieme di V-CSP)
Intelligenza Artificiale - CSP 52/52
RiassumendoMotivazioni per il framework CSPDefinizione e formalizzazione dei CSPComplessità dei CSPAlgoritmi Costruttivi Backtracking Search MetaEuristiche:
MRV, LCV Forward checking, consistency search
Backjumping Dynamic Backtracking Discrepancy Search: LDS
Algoritmi Riparativi Minimization Conflicts Simulated Annealing