Intelligenza Artificiale - Parte A

Algoritmo di consistenza d'arco GAC-3

Y Y Y Y1 1 k k 2 −GAC. Ad esempio, consideriamo il vincolo Y = X Z con il dominio uguali per tutti di [0, 9], possiamorendere X GAC riducendo il suo dominio a [0, 4], ma per gli altri valori non c’è speranza di soddisfare ilvincolo. Quindi in questo caso il CSP non è GAC.Il più noto algoritmo di consistenza d’arco si chiama GAC-3 ed è descritto nella pagina a seguire.Molto importante è notare il fatto che l’algoritmo ritorna o true oppure false in caso in cui sia statatrovata un’inconsistenza. In questo modo, eseguendo prima della ricerca questo algoritmo, è possibilesubito vedere se l’assegnamento parziale è incosistente e di conseguenza eliminare dalla ricerca qualsiasialtro affinamento di tale assegnamento. In oltre GAC-3 andando a diminuire il dominio dei valori peruna variabile è possibile che lo vada totalmente a cancellare, in questo modo non può esistere alcunassegnamento per quella variabile e di conseguenza nessun

function GAC-3(csp) {
  let Q = [];
  let XQ = [];
  
  // Inizializzazione della coda Q con i vincoli del CSP
  for (let i = 0; i < csp.length; i++) {
    let X = csp[i][0];
    let c = csp[i][1];
    Q.push([X, c]);
    XQ.push(X);
  }
  
  while (Q.length > 0) {
    let [X, c] = Q.shift();
    let i = XQ.indexOf(X);
    
    if (rimuoviValoriInconsistenti(csp, X, c)) {
      if (csp[i][1].length === 0) {
        return false;
      }
      
      XQ[i] = X;
      csp[i][1] = c;
      
      for (let j = 0; j < csp[i][1].length; j++) {
        let var = csp[i][1][j];
        let vincolo = csp[i][1][j];
        
        Q.push([var, vincolo]);
        XQ.push(var);
      }
    }
  }
  
  return true;
}

function rimuoviValoriInconsistenti(csp, X, c) {
  let rimossi = false;
  
  for (let i = 0; i < csp.length; i++) {
    let Y = csp[i][0];
    let D = csp[i][1];
    
    if (Y !== X && csp[i][1].length === 1 && csp[i][1][0] === c) {
      csp[i][1] = csp[i][1].filter(val => val !== c);
      rimossi = true;
    }
  }
  
  return rimossi;
}

i j'aggiungi (X , c ) a Q10 jreturn true1112 Xfunction Rimuovi - Valori - Inconsistenti ( csp , , c ) return true o false13 irimosso <- false14 Y , . . . , Y X<- le variabili coinvolte in c eccetto15 1 ik ∈v Dfor each do16 X Xi i × · · · ×∈ D= v , . . . , Y = v Dif nessuna tupla di valori (Y )17 Y1 1 Yk k 1 k' , Y = v , . . . , Y = v= v ) soddisfa c thene tale che (X18 1 1i X k kiv Drimuovi da19 i irimosso <- true20 return rimosso21

Consistenza di camminoLa consistenza d'arco può fare molto per ridurre i domini delle variabili, talvolta trovando una soluzione(riducendo ogni dominio alla dimensione 1) e talvolta determinando la non risolubilità del CSP. Per altriproblemi di soddfisfacimento di vincoli, tuttavia, la consistenza d'arco non consente di effettuare inferenzasufficienti. Consideriamo il problema della colorazione della mappa dell'Australia, ma con due soli coloriammessi: rosso e blu.

La consistenza d'arco non serve a nulla, perché ogni variabile è già arco-consistente: ognuna può essere rossa con il blu dell'altro estremo dell'arco, o viceversa. Ma qui è chiaro che non c'è soluzione al problema: poiché Western Australia, Northern Territory e South Australia confinano tutte tra loro, ci servono almeno tre colori solo per queste. Per fare progressi nella colorazione delle mappe ci serve una nozione di consistenza più forte. La consistenza di cammino restringe i vincoli binari utilizzando vincoli impliciti che sono inferiti considerando triplette di variabili.

Un insieme di due variabili, X e Y, è cammino-consistente rispetto ad una terza variabile Z se, per ogni assegnamento X = a, Y = b consistente con i vincoli su X e Y, se esiste un assegnamento Z = v tale che (a, v) soddisfa i vincoli su X e Z e (v, b) soddisfa i vincoli su Z e Y.

Forme più potenti di propagazione possono essere...

Definite usando il concetto di k-consistenza. Un CSP è k-consistente se, per ogni insieme di k-1 variabili e ogni loro assegnamento consistente, è sempre possibile assegnare un valore consistente a ogni k-esima variabile. La 1-consistenza significa che, dato l'insieme vuoto, possiamo rendere consistente ogni insieme di una sola variabile; è il caso della consistenza di nodo. La 2-consistenza corrisponde alla consistenza d'arco. Per reti con vincoli binari, la 3-consistenza corrisponde alla consistenza di cammino.

Un CSP si dice fortemente k-consistente se è k-consistente e anche (k-1)-consistente, (k-2)-consistente,... fino a 1-consistente. Ora supponiamo di avere un problema CSP con n nodi e di renderlo fortemente n-consistente. Allora è possibile risolvere quel problema come segue: per prima cosa scegliamo un valore consistente per X. Dato che il grafo è 2-consistente saremo certamente in grado di scegliere un valore per X, ma anche per X vale lo stesso discorso.

Algoritmo per la rilevazione di un vincolo non soddisfacibile

Se un vincolo ha un dominio con un solo valore, tale valore deve essere rimosso dai domini di tutte le altre variabili coinvolte nel vincolo. Questo processo viene ripetuto finché ci sono variabili con domini a un solo valore. Se in qualsiasi momento un dominio rimane vuoto o ci sono più variabili che valori rimasti, si è scoperta un'inconsistenza.

Possiamo applicare questo metodo per rilevare l'inconsistenza dell'assegnamento parziale A = r, NSW = r. Notate che le variabili SA, NT e Q sono effettivamente collegate al vincolo dato all-different, che richiede che ogni coppia di variabili sia di un colore diverso. Dopo aver applicato GAC-3 all'assegnamento parziale, il dominio di ogni variabile è ridotto a un solo valore. Tuttavia, abbiamo tre variabili e solo due colori rimasti, quindi il vincolo è violato.

Vincolo non soddisfacibile

Se un vincolo ha complessivamente n possibili valori distinti, e m > n, allora il vincolo non può essere soddisfatto.

Backtracking con propagazione dei vincoli

Finora abbiamo visto come GAC-3 e altri algoritmi possano inferire riduzioni del dominio di variabili prima di iniziare la ricerca. Ma l'inferenza risulta molto più efficace nel corso di una ricerca: ogni volta che scegliamo un valore per una variabile abbiamo un'opportunità del tutto nuova di inferire nuove riduzioni di dominio sulle variabili adiacenti. Nella ricerca con backtracking aggiungiamo che per ogni sottoalbero di ricerca viene eseguita una propagazione che lo rende GAC-3. Se tale propagazione porta ad incosistenza allora rimuovo le inferenze create in quanto sono locali solo a quel specifico sottoalbero, altrimenti aggiungo l'inferenza all'assegnamento, calcolo il risultato e al termine, se il risultato fallisce, non viene ritornato e l'inferenza viene comunque rimossa essendo locale. Questo perché non vogliamo che la propagazione effettuata su un sottoalbero vada a creare inferenze in altri sottoalberi.

function BACKTRACKING(csp) return una soluzione / fallimento
    return BACKTRACKING-PROP({}, csp)

function BACKTRACKING-PROP(assegnamento, csp) return soluzione / fallimento
    if assegnamento è completo then return assegnamento
    var <- SCEGLI-VARIABILE-NON-ASSEGNATA(csp)
    for each valore in dominio di var do
        if valore è consistente con assegnamento dati i vincoli then
            aggiungi { var = valore } a assegnamento
            inferenze <- Propagazione(csp, var, valore)
            if inferenze fallimento then
                aggiungi inferenze ad assegnamento
                risultato <- BACKTRACKING-PROP(assegnamento, csp)
                if risultato fallimento then return risultato
                rimuovi { var = valore } e inferenze da assegnamento
    return fallimento