Concatenazione all'indietro del primo ordine
La concatenazione all'indietro del primo ordine è l'applicazione della tecnica di ricerca basata sulla concatenazione all'indietro sui problemi della logica del primo ordine. È un algoritmo di ricerca in profondità. A partire da un'ipotesi di partenza, l'algoritmo di ricerca inferenziale ricostruisce a ritroso le premesse che la rendono possibile. Se l'algoritmo trova tutte le premesse, l'ipotesi è vera. Viceversa, se non trova tutte le premesse vere, allora l'ipotesi è falsa ( o non confermabile ). Mentre nella ricerca a concatenazione in avanti l'algoritmo inizia l'elaborazione dalle premesse iniziali per giungere progressivamente alle conseguenze logiche finali ( conclusioni ), nella concatenazione all'indietro accade esattamente l'opposto. L'algoritmo parte dalla conclusione finale ( ipotesi ) e verifica a ritroso se le premesse sono o meno soddisfacibili nella base di conoscenza. Il seguente schema mostra la rappresentazione ad albero logico del processo di inferenza a concatenazione all'indietro ( backward chaining ) del primo ordine, dall'alto ( ipotesi ) verso il basso ( premesse ). Ogni livello di profondità rappresenta un ciclo di iterazione dell'algoritmo.
La concatenazione all'indietro è un forma di ricerca AND/OR. Per confermare la veridicità di un'ipotesi iniziale, tutti i congiunti della formula logica che la rendono vera devono essere soddisfatti ( AND ). In caso contrario, l'ipotesi iniziale è falsa ( non vera ). L'algoritmo della concatenazione iniziale verifica la soddisfacibilità di ogni singolo congiunto tramite l'unificazione delle formule della base di conosocenza ( OR ), sostituendo alle variabili i relativi termini ground accettabili ( dominio della variabile ). Ad esempio, riprendendo l'esempio già visto nella concatenazione in avanti del primo ordine, in una query si chiede alla base di conoscenza se l'attività di Caio è legale o meno. La base di conoscenza iniziale è la seguente:
Nella prima iterazione l'algoritmo cerca nella base di conoscenza la formula in grado di affermare se un'attività è legale o meno. La conseguenza logica della formula Legale(x) coincide con l'obiettivo della ricerca. Una volta trovata, verifica se ciascuna clausola ( congiunto ) è soddisfacibile tramite la base dati.
Nella prima clausola l'algoritmo cerca tutte le cose (y) vendute da Tizio e le persone a cui le ha vendute (z). Nella base di conoscenza è presente una regola in base alla quale tutto ciò che Tizio possiede ( vodka ) è stato venduto da Caio. Nella seconda clausola verifica se qualcosa la vodka (y) è considerato un alcolico. Essendo vera, la seconda clausola viene subito soddisfatta. Nella terza clausola, infine, l'algoritmo verifica se l'acquirente Tizio è minorenne. Anche l'ultima formula viene soddisfatta. È pertanto possibile rispondere affermativamente alla domanda, ossia l'attività di Caio è illegale.
Esiste una stretta relazione tra l'algoritmo della concatenazione all'indietro e i problemi del soddisfacimento dei vincoli CSP. A partire da un'ipotesi iniziale, l'algoritmo ricostruisce la formula che la rende possibile, verificando se ogni suo componente è soddisfacibile tramite la base di conoscenza. Tutto ciò si traduce in una serie di vincoli e di variabili. Per ciascuna variabile è analizzato il dominio della variabile, ossia i valori che può assumere nel rispetto dei vincoli.
-
Non completezza. L'algoritmo della concatenazione all'indietro concentra l'analisi soltanto sul fatto da verificare. È quindi una forma di ragionamento logico non completa, poiché esclude dalla computazione tutte le formule che non hanno un immediato nesso logico con l'obiettivo della ricerca. Soltanto una ricerca con concatenazione in avanti può far emergere nuovi nessi altrimenti non visibili. Per questa ragione gli algoritmi a concatenazione all'indietro e in avanti sono spesso utilizzati congiuntamente.
