Ottimizzazione Combinatoria - Domande e Risposte Esame

ALGORITMO DI BELLMAN-FORD

1. Illustrare dettagliatamente l’algoritmo di Bellman-Ford

L’algoritmo di Bellman-Ford viene implementato per trovare l’arborescenza dei cammini minimi e lo fa

utilizzando le condizioni di ottimalità necessarie e sufficienti per il problema di cammino a costo minimo

derivanti dalla condizione di scarto complementare e per tanto dalla teoria della dualità.

Schema dell’algoritmo:

Inizializzazione: per

= 0, = ∞ e () = 0 = 2, … ,

1

Ordina gli archi }

{

= , … ,

1

Repeat:

| For to

= 1 :

| | If è tale che :

(,

= ) > +

| | | poni = +

| | | poni () =

| EndFor

EndRepeat

Inizialmente vengono ordinati gli archi e definita una particolare soluzione iniziale non ammissibile, ma

0 è

semplice da scrivere. Ad ogni iterazione gli archi vengono visitati nell’ordine prefissato e se per un arco

violata l’ammissibilità duale allora si rende ammissibile ponendo . In questo modo dopo un

= +

certo numero di iterazioni, tutte le condizioni di ammissibilità duale saranno soddisfatte. Alla fine è

possibile ricostruire l’arborescenza dei cammini minimi utilizzando il vettore dei predecessori (∙).

L’algoritmo termina fornendo cammini minimi da a tutti gli altri nodi.

1

2. Analizzare la sua complessità computazionale

Dal (=iterazione

momento che il blocco grande) viene eseguito volte, dove è il

{ → }

numero dei nodi. In più ogni iterazione grande è composta da (=numero degli archi) iterazioni piccole,

quindi la complessità computazionale è il numero totale di iterazioni piccole, ossia ().

un esempio numerico di applicazione dell’algoritmo

3. Fornire

Inizializzazione:

(1) = 0, (2) = (3) = (4) = ∞

(2) = (3) = (4) = 0

ordino gli archi:

(1,2), (2,3), (3,1)

= = =

1 2 3

(2,4), (3,4)

= =

4 5

Repeat 1:

= 1: (2) > (1) + → ∞ > 1

12

(2) = 1

(2) = 1, → ∞ > 3

= 2: (3) > (2) + 23

(3) = 3, (3) = 2

= 3: (1) < (3) + → 0 < 4

31

= 4: y(4) > y(2) + c → ∞ > 3

24

y(4) = 3, prec(4) = 2

= 5: y(4) < y(3) + c → 3 < 5

34 18

Repeat 2:

= 1: (2) = (1) + → 1 = 1

12 → 3 = 3

= 2: (3) = (2) + 23

= 3: (1) < (3) + → 0 < 4

31

= 4: y(4) = y(2) + c → 3 = 3

24

= 5: y(4) < y(3) + c → 3 < 5

34

La soluzione ottima è:

(1) = 0, (2) = 1, (3) = 3, (4) = 3

∄(1), (2) = 1, (3) = 2, (4) = 2

19

ALGORITMO DI FLOYD-WARSHALL

1. Scrivere l’algoritmo completo e spiegare cosa risolve

Dati un grafo orientato e connesso e i costi sugli archi l’algoritmo permette di

(ℕ, ) , ∀ ∈ ,

trovare il cammino orientato di costo minimo tra ogni coppia di nodi.

Per implementare tale algoritmo è necessario aggiungere gli archi non appartenendi ad ponendo

Esiste, allora, tra ogni coppia di nodi, un cammino orientato e il problema del cammino minimo

= ∞.

ammetterà sempre una soluzione. Per rappresentare lo schema dell’algoritmo si definiscono i seguenti

elementi:

i. Sia il cammino minimo tra con nodi interni solo ad ;

= , , … , , � con ∈ e

�, 1 2

è il costo associato al cammino minimo ;

ii.

che rappresenta la matrice dei costi del cammino ;

iii. con , = 1, … ,

=

�

�

0 che rappresenta la matrice dei costi associati agli archi del grafo

iv. con , = 1, … , ;

=

�

�

v. la matrice dei costi dei cammini minimi tra con nodi interni all’insieme

e .

Lo schema dell’algoritmo è il seguente:

Inizializzazione:

For = 1 :

| For = 1 :

| | do begin

| | | [, ] ≔ (, )

| | | [, ] ≔

| | end

For ≔ 1 :

For = 1 :

| For = 1 :

| | do begin

| | | if then:

[, ] > [, ] + [, ]

| | | |

| | | | | ≔ [, ] + [, ]

[, ]

| | | | | [, ] ≔ [, ]

| | | | end

| | end

le varie operazioni, in particolare come si inizializzano le strutture dati e la forma di

2. Giustificare

aggiornamento della matrice D 0

L’algoritmo permette di determinare un collegamento diretto dalla matrice alla matrice , cioè quella

finale che si ottiene ispezionando tutti i nodi.

0 1 −1

→ → ⋯ → → ⋯ →

0 ponendo ogni componente uguale al costo del

L’inizializzazione prevede di determinare la matrice (, )

cammino che va da a analogamente costruisco la matrice dei predecessori ponendo

([,

] ≔ [, ]),

il predecessore di nel cammino tra e uguale a Per quanto riguarda le strutture dati,

([,

] ≔ ). .

ovvero il corpo centrale dell’algoritmo, si itera volte con definito come il numero dei nodi interni di

Per ciascuna iterazione è necessario verificare la seguente condizione:

-esima [, ] > [, ] + [, ]

20

Se questa risulta verificata allora si pone e Per passare

[, ] ≔ [, ] + [, ] [, ] ≔ [, ].

−1

−1

dalla matrice (rappresenta la matrice dei costi dei cammini minimi che

con , = 1, … ,

= �

�

(ovvero la matrice dei costi

alla matrice

hanno nodi {1,2, con , = 1, … ,

= … , − 1}) =

�

�

−1

che hanno i nodi si devono distinguere due possibili casi,

dei cammini minimi = {1,2, … , })

scegliendo quello più conveniente tra:

i. non utilizza il nodo

;

utilizza il nodo

ii. .

formula di aggiornamento della matrice è:

La

−1 −1 −1

= min� , +

�

determina il costo minimo nel cammino

Che tra quello passante e quello non per

.

3. Fornire un semplice esempio numerico di applicazione dell’algoritmo

0 1 2 1 1 1

0 0

Inizio: = =

� � � �

−1 0 ∞ 2 2 2

−1 2 0 3 3 3

0 1 2 1 1 1

1 1

= =

= 1: � � � �

−1 0 2 2

−1 0 3 3

0 1 2 1 1 1

2 2

= =

= 2: � � � �

−1 0 1 2 2 1

−1 0 0 3 1 3

0 1 2 1 1 1

3 3

= =

= 3: � � � �

−1 0 1 2 2 1

−1 0 0 3 1 3

21

MASSIMO FLUSSO

1. Dimostrare che un problema di Massimo Flusso può essere formulato come programmazione

lineare

Il problema del massimo flusso (MF) si propone di massimizzare il flusso uscente dal nodo s ed entrante nel

nodo t. I vincoli che devono essere rispettati per il nodo s,t e sono rispettivamente:

{,

∉ }

+ +

− ()� ()� ()�

− � = −� = −()

� +

− −

()� ()� ()�

− � = � = ()

� +

− ()� ()�

� − � = 0

Inoltre il flusso deve essere non negativo e minore della capacità degli archi.

Definiamo Matrice di incidenza di