Appunti lezione Intelligenza artificiale - parte 2

I HG(I) G(I)

Se ogni istanza binaria(arità 2

) allora . Nel caso di

=

I HG(I) G(I)

vincoli binari ipergrafi e grafo primale coincidono.

In base alla struttura il problema può essere risolto in maniera più efficiente. Caso

estremo: Sottoproblema indipendente.

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 59/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

T lo trattiamo a parte. Se riuscissimo a trovare dei sottoproblemi con al massimo c

variabili, allora il costo di calcolare uan soluzione sarebbe un fattoriale di , dove

c

d

è il dominio, se riesco a dividere problemi indipendenti sarebbe .

d n/c

Esempio

= {A,

V B, C, D, E}

= {r (

C A, B, C),

1

R ​ ​

(

r A, B, D),

2 ​

(

r D, E)}

3 ​

Ipergrafo

Grafo Primale

, il vincolo ABC ha tre variabili chiaramente nell’ipergrafo si vede

meglio che la clique abc viene dallo stesso vincolo e non da vincoli binari (A,B),

(B,C), (C,D). In alcuni casi può fare la differenza, perché gestire sttruttura ad

ipergrafo è più facile.

CSP-Struttura del grafo

Ciclicità

Quando un ipergrafo si dice aciclico?

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 60/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Aciclicità grafo → non ci sono cicli nel grafo, quello dell’esempio è ciclico

Aciclicità Ipergrafo → esistono diverse nozioni di aciclicità. La definizione potente

è . Esistono anche ecc. Questa è la più generale.

− ˋ

α aciclicita β

Alpha-ciclicità

Consideriamo un grafo = (V ,

HG H).

− >

V vertici

>

H− iperarchi

è aciclico se esiste un JOINTREE per .

HG HG

Cos’è un JOINTREE?

= (H,

T E)

L’insieme dei vertici dell’albero, è l’insieme degli archi dell’ipergrafo. Posso

organizzare gli iperarchi sottoforma di albero.

Esempio precedente.

Che proprietà deve avere questo albero per essere definito JOINTREE?

Possiamo costruire un albero che rappresenta l’ipergrafo, mantenendo le

connessioni in maniera continua.

Deve essere vero che

• ∀p, ∈ se ∧ =



q(vertici) H(insieme), p q

. Connectedness condition.

∅, occorre in tutto il path da p a q in T

x

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 61/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Se c’è una variabile in due vertici dell’albero questa deve comparire in

tutto il percorso. Se ho una variabile che compare in un pezzo del path, o

la troviamo negli adiacenti o se scompare è finita. .

• ∀x ∈ il sottografo indotto GI(T,x) ˋ

e connesso

V

Cos’è il sottografo indotto? Tutti i vertici in cui compare . Vedo tutti i vertici

x

dove compare x e vado a vedere il sottografo, se è connesso allora è ok.

Questo non sarebbe un jointree.

Ma in questo caso non sappiamo se l’ipergrafo è aciclico, perché troviamo un join

tree allora è aciclico, ma solo se non ne troviamo nessuno allora possiamo dire

che è ciclico.

Quanto mi costa capire se un ipergrafo è aciclico? Esiste un algoritmo Gram che

ci dice: fai questo processo di eliminazione, se si svuota è aciclico altrimenti

ciclico. Processo eliminazione:

⁠

⁠

s

e ci sono archi inclusi negli iperarchi eliminali;

• ⁠

s

e ci sono variabili incluse in un solo iperarco (orecchie) eliminali.

•

Algoritmo quasi lineari, faccio un numero di passi pari al numero di variabili,

che ad ogni passo cancello o una variabile o un iperarco. Ogni passo costa

. Senza particolari accorgimenti è quadratico.

O(n)

Esempio complesso

Questo ipergrafo è ciclico o aciclico?

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 62/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

E’ aciclico. L’iperarco verde raccoglie tutti i gli altri ipergrafi. Tutte le informazioni

delle 3 variabili sono contenute negli altri.

Costruzione JOINTREE

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 63/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Così non sarebbe un JOINTREE.

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 64/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 65/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Qual’è la complessità di riconoscere se un ipergrafo è aciclico? E’ polinomiale.

Questo problema è . Lo possiamo risolvere con un

−

Logspace complete

algoritmo che utiizza spazio logaritmico.

Quando l’ipergrafo è aciclico, possiamo risolvere questo problema in maniera

efficiente. Come? Possiamo risolvere il problema dell’omomorfismo che è

Resta parallelizzabile.

−

LOGCF L complete.

Programmazione Dinamica

Algoritmo di Napsack.

Contesto: Usata quando il backtracking è inefficiente, perché esplora uno

• spazio di ricerca esponenziale.

Problema: Spesso si ricalcolano più volte gli stessi sottoproblemi.

• Soluzione: La programmazione dinamica adotta un approccio bottom-up

:

• risolve prima i sottoproblemi più piccoli e poi li combina per costruire soluzioni

più grandi.

Svantaggi: Rischio di risolvere dei sottoproblemi che potrebbero non interessarmi

dopo.

Vantaggi: Evita calcoli ridondanti e riesco ad arrivare efficacemente alla

soluzione.

Approccio per Problemi Aciclici

1. Si verifica che il problema sia aciclico.

2. Si costruisce un join tree

.

3. Si risolve il problema partendo dalle foglie del join tree fino alla radice

(

bottom-up

).

4. Qualunque sia la root, il problema può essere risolto con questa tecnica.

Algoritmo di Yannakakis

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 66/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Supponiamo di avere più vincoli con attributi in comune.

1. Eliminazione verso il basso:

a. Si visitano i nodi del join tree partendo dalle foglie

b. Si esegue un semijoin tra ogni foglia e il suo padre, per rimuovere tuple

che non contribuiscono al join finale. Così da ridurre la cardinalità dei

vincoli.

2. Costruzione verso l’alto:

a. Dalla radice verso le foglie si eseguono i join veri e propri in ordine

bottom_Up, ma ora su insiemi più piccoli e “ripuliti”

Se rimane qualcosa nella root del join-tree allora quella è una soluzione.

Chi ci garantisce di non violare i vincoli del problema?

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 67/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Sicuramente dopo aver eseguito Yannakakis, il figlio della root non può essere

violato perché abbiamo eseguito una semijoin locale, mentre tutti gli altri figli? I

vincoli degli altri figli non vengono violati per la proprietà di connessione dei join

tree

, se un valore non viola il vincolo per un padre localmente questo non

dovrebbe violare nemmeno il vincolo del figlio.

La proprietà di connessione fa si che una soluzione parziale può essere estesa

come soluzione totale

, una volta ottenuto il filtraggio di Yannakakis.

Complessità

Questo algoritmo lo possiamo vedere come un algoritmo WDP (With Polynomial

Delay)

, cioè un algoritmo enumerativo che costruisce la prima soluzione in tempo

polinomiale, e tra una soluzione e l’altra impiega solo tempo polinomiale, termina

dopo aver prodotto tutte le soluzioni

.

❗ Anche se il numero totale di soluzioni può essere esponenziale

l’intervallo di tempo tra una soluzione e la successiva è polinomiale

Dopo aver utilizzato l’algoritmo di Yannakakis per filtrare i valori, possiamo

costruire una soluzione efficiente del problema utilizzando un algoritmo

backtracking. Questo processo a differenza del backtracking normale non fallisce

mai perché tutte le tuple fanno parte delle soluzioni. Provo più soluzioni per

visitare più soluzioni.

Questo algoritmo bottom-up e top-down garantisce la consistenza locale tra

coppie di vincoli e anche la consistenza totale

. Questa proprietà viene chiamata

Generalized Arc Consistency

, che differisce dall’

Arc Consistency perché è

definita eliminando valori dal dominio delle singoli variabili, mentre in quella

generalized togliamo tuple di costanti, cioè togliamo coppie di costanti

simultaneamente

.

Mentre l’

Arc Consistency costa , la Generalized Arc Consistency di un

2 2

⋅

n d

problema CSP con:

: numero vincoli

• m

: la massima cardinalità di un vincolo

• r : insieme di input (tutti i vincoli)

• I

L’idea è:

Ordinare le relazioni rispetto alle variabili comuni → costa .

• ⋅

O(r log r)

Filtrare →

• O(r)

Si fa per ogni ramo dell’albero dei vincoli → rami

.

• − 1

m

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 68/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Si fa in salita e in discesa → 2 volte.

•

Totale:

⋅ ⋅ ) = ⋅ )

O(m r log O(∣∣I∣∣ log

r r

​ ​

Cosa abbiamo ottenuto? Nel caso di istanze acicliche, la local consistency, che

nel caso CSP era un Euristica, risolve già il problema in modo efficiente.

Aciclicità

Cosa succede se non abbiamo dei grafi/ipergrafi aciclici?

Se prendiamo in esame questa struttura binaria, questa è ciclica. Vorremmo

utilizzare gli algoritmi visti in precedenza, per i problemi aciclici, per risolvere

questi problemi ciclici. Quindi dovremmo rendere aciclici queste strutture, come?

https://www.notion.so/Riassunto-Intelligenza-Artificiale-feace89408714f189378d1b2d1983bce 69/164

15/06/2025, 11:08 (1) Riassunto Intelligenza Artificiale

Togliere un nodo

.

• Fissiamo la variabile ad un valore , per far scomparire la variabile , cosa

d D

1

vuol dire allora questo per il mio problema? Dobbiamo andare a propagare la

​

scelta, quindi filtriamo tutte le istanze che non