Risposte alle domande esame

ES.

N1 N2

N3 N4

costi:

N1N2 4

N1N3 2

N1N4 1

N3N1 -1

N3N2 1

N4N3 2

D0: 0

pred: 4

D1: 0

pred: 4

D2: 0

pred:

D3: 0

pred: 4

D4: 0 Algoritmo greedy

def algortimo:procedura in grado di individuare, in passi successivi,una soluzione per una

generica istanza di un problema. La complessità nel caso peggiore corrisponde al numero

di passi da fare per determinare una soluzione con l'istanza più difficili da risolvere di

dimensione size(I).questa viene molto utlizzata perchè il caso migliore si ottiene in

situazioni molto favorevoli e poco probabili, mentre il caso peggiore pur presentandosi in

istanze patalogiche riesce comunque a rappresentare prudenzialmente la complessità

dell'algoritmo.Per poter essere ancora più sicuri di non prendere sotto-casi particolari

nella maggior parte delle volte si prende una approssimazione superiore g(size(I)) di

W(size(I)) la cui complessità si indica con O(g(size(I)).

Avendo a disposizione un insieme base E={1,2,...,n} e avendo modo di verificare se una

soluzione fa parte dell'insieme ammissibile S={F ,F ,....,F } F⊆ E,inoltre se H⊆ F allora

1 2 m

H è una soluzione parziale che può diventare una soluzione ammissibile aggiugendo

elementi. L'idea che mette in piedi l'algoritmo di greedy è la seguente:

1. Bisogna prima di tutto costruire una sequenza di soluzioni parziali H H H H

0 1 2 3

2. Partendo dall'insieme vuoto ovveosia la soluzione parziale H 0

3. A ogni iterazione aggiungiamo l'elemento che in quel momento genera la soluzione

parziale di costo minimo ( poiché tale algoritmo non ritorna sulle sue decisioni non

garantisce di trovare la soluzione ottima).

4. L'algoritmo finisce i suoi passi quando la soluzione parziale corrente è diventata una

soluzione ammissibile.

Il suo flow-chat è il seguente:

osservazioni sul greedy:

Poichè a ogni iterazione la scelta ( non più modificale in seguito) dell'algoritmo è molto

veloce, questa sua velocità può essere pagata durante le scelte future poiché potrebbe

trovarsi davanti a scelte davvero poco vantaggiose.

Quindi se da un lato questo algoritmo ha la peculiarità di essere molto veloce, dall'altro

lato può dar luogo a soluzioni molto scandenti.

E un euristica costruttica nel senso che costruisce una soluzione.

Ampl

Tale linguaggio serve per risolvere problemi di PL, PL intera, PL01, o anche problemi

di programmazione non lineare e si deve scrivere il problema di ottimizzazione in

modo che sia di facile comprensione da parte del solutore. In realtà non è Ampl che

risolve, ma i solutori a esso associati ad esempio Cplex è uno di questi che risolve in

maniera molto efficiente problemi di PL e PLI è un linguaggio algebrico. E

soprattutto non richiede all'utilizzatore di scrivere l'algoritmo dal momento che è gia

implementato dai solutori.

File .mod

set OGG:=1...n;

param costi{OGG,OGG};

param b1;

param n:=4

param b2;

var x{OGG,OGG} binary;

maximize fo: sum{i in OGG, j in OGG}x[i,j]*costi[i,j];

s.t. vinc1{i in OGG}:sum{j in OGG}x[i,j]>=b1;

s.t. vinc1{j in OGG}:sum{i in OGG}x[i,j]>=b2;

File .dat

param n:=4;

param b1:=2;

param b2:=3;

param c: 1 2 3 4:=

1 1 2 3 4

2 2 4 1 3

3 3 1 4 2

4 4 3 2 1;

Nel file run si possono scrivere i comandi da eseguire

L'algoritmo di Bellman Ford

L'algoritmo di Bellman Ford serve per trovare l'arborescenza dei cammini minimi

vale a dire a partire da un nodo trova i cammini minimi che lo portano a tutti gli altri

nodi del grafo.

L'algoritmo in primo luogo inizializza il vettore y ovvero la soluzione duale a delle

componenti non ammissibili, ma facili da scrivere.

Dopodicchè gli archi vengono visitati in un ordine predefinito in quanto stabilito

all'inizio; se il vincolo per ogni arco non è soddisfatto viene posta l'uguaglianza per

renderlo tale (es. se abbiamo yi>yj+cij, si pone yi=yj+cij) e si scrive il nodo coda di

quell'arco nel vettore predecessori(prec)., in caso contrario si lascia inalterato.

L'algoritmo si conclude quando non si può più migliorare e genera l'alborescenza dei

cammini minimi grazie proprio al vettore dei predecessori che memorizza i

predecessori di ogni nodo in maniera tale che si può risalire facilmente al nodo

iniziale e cosa importante tutto ciò è svolto in tempo finito.

L'iterazione grande è eseguita al massimo tante volte quanti sono i nodi, mentre

quelle piccole sono tante quanti sono gli archi( devo farlo il for per tutti gli archi).

Perciò l'algoritmo è di complessità polinomiale

Es.

N1 N2

N3 N4

Costi:

N1N2 1

N2N3 2

N2N4 3

N3N4 5

N4N2 -2

inizializzo y(1)=0

y(2)=y(3)=y(4)=∞

Organizzo archi:

e1=(1,2)

e2=(2,3)

e3=(3,4)

e4=(2,4)

e5=(4,2)

Repeat 1

Iter1 y(2)=∞>y(1)+1 1uindi y(2)=y(1)+1=1

Iter2 y(3)=∞>y(2)+2 quindi y(3)=3 prec(3)=2

Iter3 y(4)=∞>y(3)+5 quindi y(4)=8 prec(4)=2

Iter4 y(4)=8>y(2)+3 quindi y(4)=4 prec(4)=3

Iter5 y(2)=1<=y(4)-2 prec(4)=2

R2

Iter1 y(2)=1<=y(1)+1

Iter2 y(3)=3 <=y(2)+2=3

Iter3 y(4)=4 <=y(3)+5

Iter4 y(4)=8<=y(2)+3

Iter5 y(2)=1<=y(4)-2

Quindi:

prec(4)=2

prec(3)=2

prec(2)=1

prec(1) non esiste

Cammino minimo e ammissibilità duale

Complessita computazionale

def algortimo:procedura in grado di individuare, in passi

successivi,una soluzione per una generica istanza di un problema.

La complessità nel caso peggiore corrisponde al numero di passi

da fare per determinare una soluzione con l'istanza più difficili da

risolvere di dimensione size(I).questa viene molto utlizzata

perchè il caso migliore si ottiene in situazioni molto favorevoli e

poco probabili, mentre il caso peggiore pur presentandosi in

istanze patalogiche riesce comunque a rappresentare

prudenzialmente la complessità dell'algoritmo.Per poter essere

ancora più sicuri di non prendere sotto-casi particolari

nella maggior parte delle volte si prende una approssimazione

superiore g(size(I)) di W(size(I)) la cui complessità si indica con

O(g(size(I)).

La complessita computazionale studia le risorse minime

necessarie (tempo e spazio) per la risoluzione di un problema.

Quindi i vari problemi sono divisi in classi di complessita in base

all'efficienza del miglior algoritmo noto che sia in grado di

risolvere quel problema. La classe di complessità indica un

insieme di problemi di una certa complessita. Le classi di

complessità si dividono in base ai tempi in cui i problemi possono

essere risolte sulla macchina di Turing e sono:

-P ovvero problemi risolubili in tempo polinomiale su macchina

deterministica

-NP ovvero problemi risolubili su macchina non deterministica in

tempi polinomiali

-Expt ovvero problemi risolubili in tempo esponenziale su

macchina deterministica

I problemi di tipo P sono abbastanza semplici ovvero si risolvono

in tempo ragionevole, mentre per i problemi NP si risolverebbero

in in tempo ragionevole su un MdT che però purtroppo non

siamo in grado di costruire. Mentre gli Expt sono problemi che si

risolvono in un tempo maggiore di qualsiasi problema

polinomiale su MdT.

Oggi si sa solo che PC=NP ma non si è riusciti a dimostrare se

P=NP o se PCNP. E finchè non si dimostrerà i problemi di tipo NP

si dovranno risolvere in tempo esponenziale su macchine di

TUring deterministiche.

Esiste anche un'altra classe di complessità facente sempre capo a

NP e sono i problemi NP-hard ovvero difficili almeno quanto un

problema NP; mentre i problemi NP-completi sono i problemi che

stanno sia in NP che in NP-hard

Descrizione del problema di costo minimo

Dato un grafo G(N,A);

Due nodi speciali s e t;

l'esistenza di un cammino da s ad ogni nodo u app.N

costi Wuv per ogni uv app A

Si vuole trovare il cammino orientato che vada da s a t avente costo minimo.

Un cammino si può rappresentare attraverso il suo vettore di incidenza che vale 1 se

quell'arco fa parte del cammino 0 altrimenti.

Le proprietà di tale vettore sono:

-La somma dei flussi entranti in s è 0 mentre quella dei flussi uscenti è 1 ovvero da s

esce un solo arco del cammino

- La somma dei flussi entranti in t è 1 mentre quella dei flussi uscenti è 0 ovvero da t

entra un solo arco del cammino

-In ogni arco nodo che non sia s o t numero degli archi del cammino che entrano è

uguale al numero di archi del cammino che escono.

E' un problema di flusso a costo minimo dove la rete si può considerare di capacità

infinita e la domanda dei nodi è -1 per il nodo di partenza, 0 per tutti gli altri e 1 per

il nodo di arrivo.

La formulazione di Qst è la seguente:

Qst={x:Mx=d,x>=0} ovvero il poliedro dei cammini che vanno da s a t.

Dove d sono le domande dei nodi e M la matrice che esprime le relazioni tra i flussi

in rapporto alla domanda. Tale formulazione è ottima in quanto tutti i vertici di Qst

sono proprio dei cammini dal momento che la matrice M è Totalmente

unimodulare( si può dimostrare vedi domanda flusso a costo minimo).

FLUSSO DI COSTO MINIMO

Un problema di flusso a costo minimo è caratterizzato da(G,c,d):

-Una domanda 'di' associata a ogni nodo i pari a quanto il nodo richiede; se la

domanda è negativa è pari a quanto il nodo fornisce e nullo se il nodo è solo di

transito.

-un costo wij ovvero il costo per trasportare una unità dall'arco i all'arco j e ce ne è

uno per ogni arco (i,j) in tal casp il grafo si chiama rete

-una capacita cij ovvero la massima quantità inviabile su quell'arco e ce ne è una per

ogni arco ij.

-Si vuole trovare un flusso xij da mandare su ogni arco in modo da minimizzare il

costo e tenere fede alle richieste fatte(non superare le capacità e rispettare le

domande). Dal momento molte volte il semplice passaggio è indipendente dalla

quantità trasportata(si vedano i pedaggi autostradali o l'affitto di mezzi di trasporto)

allora ci potrebbe essere un ulteriore richiesta che il flusso sia intero.

La formulazione del poliedro Q di tale problema dopo aver accorpato in matrici è:

min wtx

Mx<=d

Mx>=d insieme a quello sopra sono ricavati dai vincoli per la domanda dove per ogni

nodo la merce entrante meno quella uscente deve essere uguale alla domanda

Ix<=c non posso trasprtare più di quanto l'arco mi può offrire

x>=0 non trasporto quantita negati