Appunti del corso di Fondamenti di ingegneria elettrica ed elettronica

ALGORITMO:

Procedura in grado di individuare, in PASSI SUCCESSIVI, una SOLUZIONE per una generica ISTANZA di un PROBLEMA.

PROPRIETA’ DI UN ALGORITMO

- CORRETTEZZA: applicato a I I produce sempre F(I)

- EFFICIENZA: in termini di risorse: SPAZIO e TEMPO

Istanza e Soluzione debbono essere opportunamente codificate

SPAZIO: Numero di bit necessari a memorizzare I I e a lavorare fino a produrre F(I)

✓ TEMPO: Numero di passi (finiti) necessari fino a produrre F(I)

✓

TEMPO DI ESECUZIONE = Numero di passi necessari ad un algoritmo per determinare la soluzione associata ad un’istanza

COMPLESSITA’ DI UN ALGORITMO = Numero di passi necessari per determinare la soluzione di una generica istanza di

dimensione size(I)

Dipende dalla:

Dimensione size(I) dell’Istanza (es. # componenti del vettore)

✓ Specifica Istanza (es. valori delle componenti del vettore)

✓

Quindi ci serve una FUNZIONE DELLA SOLA DIMENSIONE : c(size(I))

DIMENSIONE size(I) = Numero di celle necessarie a rappresentare i dati di ingresso (istanza I)

size(I) è una funzione f(x,y,..) dei parametri dell’istanza I

Conviene inoltre utilizzare una approssimazione superiore (UB) facilmente calcolabile g(size(I)) della vera funzione W(size(I)).

Cioè f(x) è ordine di g(x) se, per valori di x abbastanza grandi, il valore di f(x) è definitivamente inferiore a quello di c1* g(x)

Alberi ricoprenti ottimi

- Costruisci una sequenza di foreste H(S,T) con S N

- Inizia con S={} e T={}: foresta in G(N,A)

- Ad ogni passo: a) aggiungi a T l’arco di costo minimo wy A-T

tale che H’(S {w,y},T {wy}) sia aciclico

b) aggiungi ad S i nodi w ed y

- Quando |T|= |N|-1 allora H(N,T) è l’albero di costo minimo

- Costruisci una sequenza di alberi parzialmente ottimi H(S,T), |S|>1

- Inizia con S={u} e T={}: contenuto in ogni albero di costo minimo

- Ad ogni passo: a) aggiungi a T l’arco di costo minimo wy

b) aggiungi ad S il nodo y

[H’(S {y}, Y {wy}) è parzialmente ottimo per il Teorema 5.2.2]

- Quando S=N abbiamo che H(N,T) è l’albero di costo minimo

H(S,T*) è un albero ricoprente di costo minimo di G(N,A) se e solo se per ogni arco pq T*, si ha che,

il taglio definito dalle componenti connesse N’ e N’’ che si ottengono rimuovendo {pq} (detto taglio

fondamentale), è tale che:

c ≤ c per ogni arco {uv}

H(S,T*) è un albero ricoprente di costo minimo di G(N,A) se e solo se per ogni arco pq A-T*, si ha che,

detto P il cammino tra p e q in T*, si ha che:

c ≤ c per ogni arco {uv} P

Flusso Intero a Costo Minimo

■ un grafo orientato G(N,A)

■ una domanda d associata ad ogni nodo i N.

La domanda d risulta positiva se il nodo riceve, negativa se invece fornisce, nulla se è un nodo di solo

transito;

■ un costo w associato ad ogni arco (i,j) A;

■ [una capacità c associata ad ogni arco (i,j) A, rappresentante la massima quantità inviabile lungo

quell’arco]

Trova un flusso x sul grafo (G,c,d) da inviare su ogni arco (i,j) A tale che il costo totale sia

minimizzato [e le richieste di capacità siano rispettate].

Il problema in cui voglio un flusso intero è detto flusso intero di (G,c,d), dove il grafo G è detto grafo capacitato ed è

definito dai vettori capacità c e domanda d.

Dati dei costi w per ogni arco (i, j) A, si vuole trovare un cammino orientato da un nodo origine s ad un

nodo destinazione t tale che la somma dei costi degli archi che lo compongono sia minima (o massima).

È un problema di flusso intero in cui la rete è non capacitata e la domanda è -1 per l’origine, 1 per la

destinazione e 0 per gli altri nodi.

Dati un nodo sorgente s avente solo archi uscenti, un nodo pozzo t con soli archi entranti e delle capacità

c per ogni arco (i, j) A, si vuole trovare il massimo flusso ammissibile uscente da s e entrante in t, detto

flusso s-t.

È un problema di flusso intero in cui ho un arco immaginario da t ad s di capacità infinita e costo -1,

mentre tutti gli altri archi hanno costo 0.

Richiami Dualità ▪

Massimo Flusso

Trovare il massimo flusso f* che è possibile inviare da s a t rispettando le capacità degli archi

FLUSSO MASSIMO f* ≤ Capacità di ogni taglio s-t

FLUSSO MASSIMO f* = capacità minima di un taglio s-t

La rete incrementale tiene conto della possibilità di:

aumentare il flusso sugli archi non saturi, che danno origine

ad archi diretti con capacità residua non nulla;

diminuire il flusso sugli archi non scarichi, che danno origine

ad archi inversi di capacità residua non nulla.

Un cammino s-t nella rete incrementale G’(N,A’) individua la possibilità di aumentare il valore del flusso corrente f(x).

Tale cammino viene detto cammino aumentante e comporta la NON ottimalità di x.

A ogni cammino aumentante della rete incrementale corrisponde nella rete originale una sequenza di archi diretti

(lungo cui aumentare il flusso) ed archi inversi (lungo cui diminuire il flusso).

PASSO 0:

x = 0, f = 0, OTTIMO = false

repeat

Costruisci la rete incrementale G’ associata a x;

Trova, se esiste, un cammino aumentante P da s a t in G’

If P Then OTTIMO = true

∄

Else aggiorna flusso :

Δ = min {c’uv : (u,v) P}

Per ogni arco arco (u,v) P

If (u,v) A Then x := x + Δ

Else x := x - Δ

until (OTTIMO = true)

Cammino Minimo

Il cammino orientato P* da s a t avente COSTO MINIMO è tale che:

P*: w(P*) < w(P) cammino orientato P da s a t di G(N,A)

il problema del Cammino Minimo è un problema di flusso intero in cui

la rete è non capacitata e la domanda è -1 per l’origine, 1 per la

destinazione e 0 per gli altri nodi.

I cammini da s a t sono i vertici (SBA) del poliedro

x* VETTORE DI INCIDENZA DI UN CAMMINO P* è OTTIMO

se e solo se esiste una soluzione duale y* tale che:

y* = y* + w per ogni uv A con x* =1 (cioè per ogni uv P*)

Un cammino orientato P da s a t in G(N,A) ha costo minimo se e solo se esiste una soluzione duale

y’ con la proprietà che P è un cammino orientato da s a t nel grafo ridotto G(y’)

1. SCEGLI una soluzione duale y’ e costruisci G(y’)

2. Cerca un qualsiasi cammino orientato da s a t in G(y’)

3. Se esiste è ottimo. Se non esiste AGGIORNA y’ Inizialmente vengono ordinati gli archi e definita una

particolare soluzione duale iniziale y che non è ammissibile

ma è facile da scrivere.

A ogni iterazione gli archi vengono visitati nell’ordine

prefissato:

se per un arco (u,v) si ha y > y + w violando l’ammissibilità

duale, si rende la variabile ammissibile ponendo

y = y + w

Alla fine è possibile ricostruire l’arborescenza dei cammini minimi

utilizzando il vettore dei predecessori prec.

Il Problema Duale ammette soluzioni (il Problema Primale non è

illimitato) se e solo se il grafo G(N,A) non ha cicli orientati di costo

totale positivo.

A ogni iterazione gli archi vengono visitati nell’ordine

prefissato:

se per un arco (u,v) si ha y < y +w violando l’ammissibilità

duale, si rende la variabile ammissibile ponendo

y = y + w