• Non ci sono risultati.

Consistenza e soluzione di un CSP in PA

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Consistenza e soluzione di un CSP in PA"

Copied!
3
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 3 pagine )

Testo completo

(1)
(2)
(3)

Consistenza e soluzione di un CSP in PA

1. Trasforma i vincoli: x = y in x ≤ y e y ≤ x, x > y in y < x, x ≥ y in y ≤ x 2. Crea grafo G diretto dei vincoli omettendo x ≠ y (solo relazioni <, ≤)

3. Se G è un DAG il CSP è consistente: usa DFS per trovare ordinamento delle variabili (attraverso ordinamento topologico di G) e deriva soluzione

4. Se G ha cicli (non è un DAG):

a. Calcola gli SCC di G

b. Se esiste un SCC con due nodi x e y collegati da < o nel CSP c’è x ≠ y: CSP Inconsistente c. Altrimenti collassa ogni SCC in un singolo nodo generando un DAG G’. [FARE ESEMPIO di

collassamento]

d. Trova ordinamento variabili attarverso ordinamento topologico di G’ (DFS) e soluzione

NB: se non so che G è un DAG passo da 2 direttamente a 4.a

Riferimenti

Scarica adesso ( PDF - 3 pagine - 10.02 MB )

Documenti correlati

Problema 1. Data g (x) ∈ C ([0,∞))) , tale che g (x) = 0 per x ≥ 2, trovare una soluzione del problema

Prima di inviare la soluzione TRAMITE CELLULARE lo studente contatta il docente, il docente controlla il foglio della soluzione, se neces- sario fará una foto.. Solo dopo lo

2 Classificazione degli algoritmi di ordinamento

• ogni cammino dalla radice a una foglia è la sequenza di confronti necessaria a riordinare una delle possibili permutazioni di lunghezza n, che è diversa per ogni permutazione, e

Ordinamento Ordinamento

– Ogni algoritmo basato su confronti può essere sempre descritto tramite un albero di decisione. – Ogni albero di decisione può essere interpretato come un algoritmo

Soluzione Scrivo e bilancio la reazione N2 (g

Atomo centrale S con 6 elettroni sul livello di valenza, l’ossigeno, quando è atomo terminale, non conta nel calcolo delle coppie strutturali, 4 elettroni dai 4 atomi

Soluzione Esercizio 2

Poich´ e l’attrito tra il carrello e il binario ` e trascurabile, la risultante delle forze esterne agenti sul sistema carrello-persona ` e nulla lungo la componente parallela

2 Soluzione del problema

Infatti, nei casi pratici, i volumi di produzione sono tali da richiedere un numero elevato di tondini tagliati secondo un determinato schema di taglio e pertanto, una buona

Ordinamento e Ricerca Ordinamento e Ricerca

 Per trovare il prossimo minimo, si visitano (n - 1) elementi Per trovare il prossimo minimo, si visitano (n - 1) elementi + 2 visite per lo scambio. + 2 visite per

N Soluzione N 26 (2)Commenti alla soluzione

Nota Bene: nella procedura devono comparire almeno una volta tutte le variabili dichiarate (A, B, C, D, E, H, K, M). Scrivere la soluzione nella