Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

OTTIMIZZAZIONE SU RETI: PROBLEMI TRATTABILI

informatica




Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a WhatsApp - corso di

OTTIMIZZAZIONE SU RETI: PROBLEMI TRATTABILI

1-ALBERI OTTIMI


Problema:

Dato un grafo G=(V,E) ed una funzione costo c:E Z+ ,

trovare un albero T che connetta tutti i vertici (albero ricoprente = spanning tree) di G di costo totale minimo


S c(e)

e E(T)


Algoritmo MST-1 (Kruskal)


Step 1 – Ordina i lati secondo costi non-decrescenti




c(e1) c(e2) c(em)


(m = |E|). Poni E(T) = E’ = F e j = 1


Step 2 – Se E’ non contiene cicli aggiungi ej ad E’;

j := j+1


Step 3 – Se T = (V,E’) è connesso STOP, altrimenti vai

al passo 2


Algoritmo MST-2 (Prim)


Step 1 – Scegli un vertice qualunque v di G come

radice  di T; poni V’ = ; per ogni vertice w diverso da v poni l(w) =    c() (se non esiste poni l(w) = ); E’ := F

Step 2 – Trova un vertice w V\V’ con l(w) minimo e

sia e un lato che connette w a V’ di costo pari

a l(w); aggiungi e ad E’ e w a V’


Step 3 – " w’ V’ poni l(w’) := min ) }


Step 4 – Se V’ = V STOP, altrimenti vai al passo 2


Complessità di MST-2


n-1 iterazioni ciascuna con due operazioni:


operazione A: trova un’etichetta l(w) minima

" w V\V’ < n confronti

operazione B: quando w è inserito in V’ confronta

il costo di con  l(w’) < n confronti


QUINDI: n + (n-1)(n+n) ovvero O(n2) operazioni


ARBORESCENZA DI COSTO MINIMO


DEFINIZIONE un’ arborescenza è un albero che connette tutti i nodi di G, orientato a partire da un nodo radice verso tutti gli altri nodi (o viceversa)


INPUT digrafo G = (N,A)

c(a) costo dell’arco a

radice r N


OUTPUT un arborescenza T radicata in r di costo

minimo che connetta tutti i nodi di G


PROPRIETA’ in un’arborescenza diretta dalla radice

verso gli altri nodi il grado entrante in ogni nodo

diverso dalla radice è uguale ad 1


FORMULAZIONI  Sia Bj l’insieme di archi entranti

nel nodo j (j r) e sia E l’insieme di paia di nodi tra cui esiste almeno un arco di G. Il problema è trovare un sottoinsieme T di A tale che: (1) nel grafo (N,E) identifichi un sottoinsieme S di E senza cicli; (2) |T Bj| = 1 " j r; (3) il costo c(T) sia il più piccolo possibile.


Per esercizio si trovi una formulazione del problema come PLI a variabili binarie xij (=1 se l’arco (i,j) appartiene a T, =0 altrimenti).



Algoritmo (di Edmonds-Bock) O(n2)


k:=1; Dk:=D; S:=F

1.       foreach nodo u, u r, S:=S dove au è un arco di valore minimo entrante in u;

2.       if S non contiene cicli go to 5 else sia C un ciclo di S;

3.       [si costruisce un nuovo grafo D’ che non contiene i nodi di C, ma contiene un nuovo nodo h=n+k e tutti gli altri nodi di Dk]

foreach arco (i,j) di Dk do

if i,j C then (i,j) A(D’);

if i C , j C then D’ contiene l’arco (h,j);

if i C , j C then D’ contiene l’arco (i,h)

enddo;

if k,l h then w’kl=wkl else if k=h then

w’kl=mini C wil else if l=h then w’kl=min dove aj è l’arco di C che entra nel nodo j;

k:=k+1; Dk:=D’; w:=w’

go to 1;

4.       do until k=1

sia (i,j) l’arco corrispondente in Dk-1 all’arco (i,h) di Dk contenuto in S e sia (l,j) l’arco di

Dk-1 entrante nello stesso nodo j nel ciclo C che ha dato origine al nodo h;

S:=S C\;

cancellare h e sostituire (i,h) con (i,j) in S;

k:=k-1

enddo

5. output S



2-CAMMINI MINIMI


INPUT              un digrafo G = (V,A);

una funzione che assegna una lunghezza c(a) intera non-negativa ad ogni arco a di G;

un vertice speciale s

OUTPUT                      la lunghezza l(v) di tutti i cammini più corti da s a tutti gli altri vertici v di G



Algoritmo SP (Dijkstra)


Step 1             " v V\ poni l(v) := c((s,v)) (se (s,v) non esiste poni l(v) := ); V’:= ; A’:= F

Step 2             determina un vertice w V\V’ con l(w) minima; sia v un vertice di V’ tale che l(w)= l(v)+c((v,w)); aggiungi (v,w) ad A’ e w a V’

Step3              " w’ V’ per cui (w,w’) in G poni l(w’)=min

Step 4             se V’=V STOP altrimenti vai a Step 2


Esercizio dimostrare che la complessità di SP è la stessa di MST-2 e cioè O(n2). I due algoritmi differiscono solo in un punto: quale ?



NOTA BENE: l’algoritmo SP non funziona quando

gli archi hanno costi anche negativi; infatti in tal

caso il problema non è ben definito dovendosi

specificare se è permesso oppure no di passare più

volte dallo stesso vertice (cioè se si vuole cammini

semplici solamente o no). Il problema resta

risolubile in tempo polinomiale se si sa a priori che

G non contiene cicli di lunghezza totale negativa, ma

l’algoritmo per risolverlo è il seguente di complessità

O(n3) (dimostrare per esercizio):


Algoritmo FORD                     

for each j V do       

begin

l(j) :=

p(j) := -1

end ; l(s) := 0;

for i := 1 to n do



begin

for j := 1 to n do

begin

h l(k) + c((k,j))

:= min ;

if h < l(j) then do

begin

l(j) := h

p(j) := k

end

end

end

output i vettori l e p

3-ACCOPPIAMENTI OTTIMI


DEFINIZIONE Un sottoinsieme M dei lati di un grafo

G = (V,E) è un accoppiamento se ogni vertice di G è incidente al più ad un lato di M. Un accoppiamento si dice perfetto (o completo) se ogni vertice appartiene ad esattamente un lato di M.


APPLICAZIONI

1.       Sia S un insieme di elementi e siano assegnati k sottoinsiemi di S. Trovare k differenti elementi di S tali che l’elemento j appartenga al j-esimo sottoinsieme.

2.       Un insieme di lavori deve essere eseguito da altrettanti addetti. Ogni addetto è capace di eseguire solo un sottoinsieme dato dell’insieme di lavori. Assegnare un addetto al massimo numero di lavori possibile. L’abilità di ogni potenziale addetto se assegnato ad un certo lavoro può essere misurata da un’opportuna quantità: in tal caso si cerca l’assegnamento di lavori ad addetti che massimizzi un’assegnata cifra di merito funzione delle quantità date.


CAMMINI ALTERNANTI E AUMENTANTI


DEFINIZIONE  Un cammino alternante in un grafo G = (V,E) rispetto ad un accoppiamento M è un cammino ( v1, … , vk ) dove tutti i lati ,, … ,, … sono in M oppure sono in M i lati ,, … ,, … Cioè lati di M si alternano con lati di E\M nel cammino.


DEFINIZIONE  Un cammino aumentante è un cammino alternante nel quale entrambi i vertici terminali sono “liberi” (= non incidenti a lati di M).


NOTA BENE: se esiste un cammino aumentante P in G rispetto all’accoppiamento M allora si può ottenere un accoppiamento di cardinalità maggiore eliminando da M i lati di P M ed aggiungendovi i lati di P\M.


TEOREMA        Un accoppiamento M in un grafo G = (V,E) è di cardinalità massima se e solo se non esistono cammini aumentanti P in G rispetto ad M.


DIMOSTRAZIONE        Abbiamo già visto che se P esiste allora M non è di cardinalità massima e quindi resta solo da dimostrare che se M non è di cardinalità massima esiste sempre un cammino aumentante P. Sia M’ un accoppiamento di cardinalità maggiore di M in G e si consideri la differenza simmetrica dei due insiemi M ed M’: D := (M’\M) (M\M’) = M’ M. Nel grafo G’= (V,D) dato che ogni vertice è incidente al più ad un lato di M e ad uno di M’, tutti i vertici hanno grado 0,1 o Dato che tutti i vertici di grado 2 sono incidenti ad un lato di M ed a un lato di M’, tutte le componenti connesse di G’ sono o cammini alternanti o cicli alternanti. Ma dato che M’ è di cardinalità maggiore di M, esiste almeno un cammino P contenente più lati di M’ che di M: P è un cammino alternante con entrambi i vertici terminali non incidenti a lati di M e quindi è un cammino aumentante


Questo teorema suggerisce naturalmente per trovare un accoppiamento di cardinalità massima il seguente


Algoritmo MM


Step 1 M := F

Step 2 trova un cammino aumentante P in G

rispetto ad M se esiste altrimenti STOP

Step 3 M := (M\(M P)) (P\M); torna al passo 2


L’algoritmo MM è in effetti incompleto finché non si dica come trovare P al passo 2: riportiamo qui di seguito un algoritmo polinomiale per fare ciò nei grafi bipartiti, ma che non funziona se applicato a grafi qualunque. Sia G un grafo bipartito: indichiamo con V e W le due “sponde” di vertici e con E l’insieme dei suoi lati.


Algoritmo APM


Step 1             Etichetta con “no” tutti i vertici di W e tutti i vertici di V incidenti a lati di M; etichetta con “si” tutti i vertici di V non accoppiati; sia S l’insieme di questi ultimi vertici e T l’insieme dei vertici di W aventi etichetta “si” (cioè per adesso l’insieme vuoto)

Step 2 Assegna etichetta “si” a tutti quei vertici di W aventi etichetta “no” che sono connessi a un vertice v di S tramite un lato non appartenente ad M; aggiungi tutti questi vertici a T e poni S uguale all’insieme vuoto

Step 3 Se uno qualunque dei vertici w di T non è accoppiato allora abbiamo trovato P; altrimenti tutti i vertici di V con etichetta “no” connessi ad un vertice w di T con un lato di M ottengono etichetta “si” e vengono aggiunti ad S; T := F

Step 4 STOP se P è stato trovato oppure se S è vuoto, altrimenti vai al passo 2

GENERALIZZAZIONI


A.       Grafi qualunque: c’è bisogno di un’etichettatura molto più complicata (Edmonds ’65)

B.       Caso pesato: trovare un accoppiamento di peso massimo. Se G è bipartito si può usare il metodo ungherese (Kuhn ‘5?) oppure risolvere il problema trasformandolo semplicemente in uno di flusso di costo minimo (vedi più oltre). Se G non è bipartito si può usare l’algoritmo blossom (Edmonds ’65) di complessità O(n3)

C.       Un accoppiamento perfetto può anche definirsi come un sottografo con gradi tutti uguali ad 1. Una generalizzazione è quindi quella di imporre gradi x diversi da 1. Il problema si riconduce al precedente sostituendo ad ogni vertice di G un grafo bipartito completo avente una sponda di cardinalità pari al grado d del vertice in G, l’altra di cardinalità pari a d-x e inserendo i lati di G fra nodi delle sponde più numerose. Naturalmente questa trasformazione è molto inefficiente ed esistono algoritmi ad-hoc

D.       Se si vuole trovare un cammino di lunghezza minima in un grafo non-orientato con lati di costo negativo, ma senza cicli negativi, non possiamo sostituire ad ogni lato due archi in sensi opposti dello stesso costo, come si può nel caso di costi tutti positivi perché si creano cicli di costo totale negativo e nessuno degli algoritmi visti in precedenza può funzionare. Invece si può trasformare il problema in una versione pesata del problema di cui al punto C

PROBLEMA DEL POSTINO (CINESE)

(un applicazione del problema dell’accoppiamento non-bipartito ottimo)


INPUT             un grafo connesso G = (V,E) e una funzione che assegna ad ogni lato e un costo non-negativo c(e)

OUTPUT          un sottoinsieme S di lati di G da aggiungere ad E di costo totale minimo tale che il grafo G’ = (V,E S) sia Euleriano (cioè sia possibile partire da un vertice qualunque e transitare da ogni lato una volta ed una sola tornando al vertice di partenza, percorrendo ciò che appunto si indica come ciclo Euleriano e che corrisponde a quello che un postino deve fare per consegnare la posta lungo ogni strada della zona a lui assegnata)


TEOREMA (Eulero 1736) Un (multi)grafo G è Euleriano se e solo se è connesso e tutti i suoi vertici hanno grado pari


OSSERVAZIONI            (a) l’insieme di vertici di grado dispari V’ in G ha cardinalità pari; (b) tutti i vertici di V’ devono avere grado dispari nel grafo (V,S) mentre i rimanenti vertici devono avere grado pari affinché, per il teorema precedente, il grafo risultante sia Euleriano; (c) (V,S) non contiene cicli dato che potrebbero essere eliminati senza aumentare il costo di S e continuando a soddisfare al teorema, nel senso di lasciare inalterata la parità dei vertici; (d) allora S è un insieme di cammini che connettono paia di vertici di V’.


Algoritmo CP


Step 1 Trova tutti i vertici di grado dispari V’ di G

Step 2             Determina i cammini minimi fra tutte le coppie di vertici di V’

Step 3             Costruisci il grafo completo H con vertici V’ dove il peso di un lato è uguale alla lunghezza del cammino minimo tra v e w in G (determinata al passo precedente)

Step 4             Trova un accoppiamento perfetto M di peso totale minimo in H

Step 5             Per ogni lato di M ricostruisci il corrispondente cammino minimo e aggiungi i suoi archi a G (duplicandoli) ottenendo un multigrafo G’



Step 6             Trova un ciclo Euleriano in G’


Complessità    O(n) + O(|V’|3) O(n3)


4-PROBLEMA DEL FLUSSO MASSIMO


Input   - digrafo G=(N,A) con n nodi e m archi

- nodo di origine s e di destinazione t

- capacità c(a) (intera) positiva per ogni arco  

a di A

Output matrice X=[xij] di valori del flusso associato a ciascun arco (i,j) tale che


0 xij cij                                  "(i,j) A                                 (1)

Si=1,…,nxij - Sk=1,…,nxjk = 0 se j s,t

= v se j=t (2)

= -v se j=s


con valore totale del flusso v massimo


DEFINIZIONE 1 un arco (i,j) è detto saturo se xij=cij


DEFINIZIONE 2 un arco (i,j) con xij=0 si dice scarico


DEFINIZIONE 3 sia P un cammino non-orientato da s a t (cioè un cammino ottenuto ignorando la direzione degli archi). Un arco (i,j) in P diretto da s a t si dice in avanti, mentre si dice a ritroso nel caso contrario. P è un cammino aumentante (sottinteso del valore del flusso v) rispetto ad X se tutti i suoi archi in avanti non sono saturi e tutti quelli a ritroso non sono scarichi.


DEFINIZIONE 4 un (s,t)-taglio è identificato da un insieme S N tale che s S e t T=N\S (l’ insieme complemento di S rispetto ad N). La capacità del taglio (S,T) è data da

c(S,T) = Si S Sj T cij                  (3)


LEMMA 1 per ogni (s,t)-taglio (S,T)

v = S xij - S xij (4)

(i,j) FS        (i,j) BS

dove FS è l’insieme di archi in avanti e BS quello degli archi a ritroso del taglio (S,T).


Dimostrazione dalla (2) v = S S xij - S xjk )

j T i=1,…,n k=1,…,n

cioè

v = S [ S xij + S xijS xjk - S xjk ]

j T i S        i T k S k T


= S [ S (xij – xji ) + S (xij – xji ) ]

j T i S             i T


= S S (xij – xji ) = S xij - S xij

j T i S            (i,j) FS        (i,j) BS


LEMMA 2 per ogni (s,t)-taglio (S,T) e flusso X ammissibile di valore v,


c(S,T) v.                                 (5)


Dimostrazione dalla (4) e dalla (1)


v =       S xij - S xij S cij - 0

(i,j) FS (i,j) BS i S,j T


TEOREMA 1 (del cammino aumentante) il valore v del flusso X è massimo se e solo se non esistono cammini aumentanti da s a t rispetto ad X.


Dimostrazione (la parte “solo se” è ovvia) sia X un flusso che non ammette cammini aumentanti da s a t ed S l’insieme di nodi che ammettono un cammino aumentante con origine in s. Allora per tutti gli indici j S e k T si ha che tutti gli archi (j,k) sono saturi oppure tutti gli archi (k,j) sono scarichi. Dal Lemma 1, v = c(S,T) e dal Lemma 2 v deve essere massimo.        


TEOREMA 2 (del flusso intero) se tutte le capacità cjk sono intere, esiste un flusso ammissibile X intero di valore massimo.


Dimostrazione supponendo di iniziare con un flusso nullo e di trovare successivamente gli opportuni cammini aumentanti, il flusso dei vari archi viene sempre aumentato di una quantità intera, arrivando quindi ad una soluzione ottima data dalla matrice X con componenti tutte intere.                 


TEOREMA 3 (del massimo flusso e minimo taglio) il valore massimo di un flusso da s a t è uguale alla capacità di un (s,t)-taglio di capacità minima.


Dimostrazione il risultato segue dai Teoremi 1 e 2 e dlla (5) per tutte le reti con capacità dsate da numeri razionali, fatta eccezione (a rigore) per il fatto che ancora dobbiamo dimostrare che ogni rete ammette un flusso massimo: questo fatto viene dimostrato dall’esistenza dell’algortimo MAXFLOW riportato più oltre.                     


Osservazione: la versione di MAXFLOW riportata in seguito fa uso di un grafo incrementale. Da ogni arco (i,j) di A possono originarsi al massimo due archi di tale grafo: a+= (i,j) se xij < cij e a-= (j,i) se xij > 0. Ad ogni arco del primo tipo si associa (se richiesto) una lunghezza pari a cij - xij mentre ad ogni arco del secondo tipo si associa una lunghezza pari ad xij. Per evitare situazioni ambigue, il grafo di partenza non deve contenere coppie di archi uno in un senso ed uno in senso opposto fra gli stessi nodi. Se questo accadesse basta inserire un nuovo nodo fittizio h a metà di uno dei due archi in questione che viene quindi sdoppiato in due archi in serie (i,h) e (h,j) entrambi della stessa capacità dell’arco (i,j).


Procedure MAXFLOW (N,A,s,t,C,X,v):

1.       A F

2.       foreach (i,j) A

3.       if xij < cij then do

4.       A := A lij := TRUE ; lij:=cij-xij ;

enddo ;

5.       if xij > 0 then do

6.       A := A lij := FALSE ; lij:=xij ;

enddo ;

7.       AUGPATH (N,A,s,t,l,P) ;

8.       if P=F then output X,v [optimum] else do



9.       e := min ;

10.            foreach (i,j) P if lij then xij:=xij+e

else xij:= xij + e

11.            v:=v+e

12.            MAXFLOW (N,A,s,t,C,X,v)


Osservazioni

  • Se G contiene archi non orientate è spesso possibile sostituirli con archi della stessa capacità uno da ia j e uno da j ad i.
  • Se anche i nodi di G sono capacitati, si può ricondursi al caso di capacità assegnate solo agli archi introducendo al posto del nodo i due nodi i’ e i” con l’arco (i’,i”) di capacità pari a quella del nodo i.
  • Se si vuole un flusso di valore assegnato v* basta aggiungere il nodo t* e l’arco (t,t*) di capacità v*.

COMPLESSITA’ DI MAXFLOW


Dipende ovviamente da come viene realizzata la subroutine AUGPATH.

1.       Se si sceglie un qualunque cammino da s a t nel grafo incrementale, l’algoritmo può addirittura non essere polinomiale.

2.       Sembra promettente l’idea di cercare il cammino che assicura il massimo incremento di flusso: ciò si ottiene cercando nel grafo incrementale un cammino da s a t avente lunghezza dell’arco di lunghezza minima, massima. Una semplice modifica dell’algoritmo di Dijkstra risolve questo problema in O(n2).

3.       La terza opzione è quella di scegliere un cammino da s a t con il minor numero di archi, indipendentemente dalla loro lunghezza. Ciò può farsi in O(m).


Nel caso 2 MAXFLOW avrà una complessità O(n2log v) mentre nel caso 3 diventa O(m2n) (Edmonds & Karp 1972).



5- FLUSSO DI COSTO MINIMO


Formulazione:

min S dijxij

(i,j) A


con i vincoli 0 xij cij

Si=1,…,n xij - Sk=1,…,n xjk = 0 se j s,t

= v se j=t

= -v se j=s


dove dij è il costo unitario di flusso sull’arco (i,j)


GRAFO INCREMENTALE

Da ogni arco a=(i,j) di A possono nascere al più due archi del grafo incrementale: uno diretto come a di costo d(a) e uno diretto in senso opposto di costo –d(a). Il primo se a non è saturo, il secondo se a non è scarico.


Il costo di un cammino da s a t nel grafo incrementale è dato dalla somma dei costi dei suoi archi e lo stesso vale per i cicli (semplici).


TEOREMA 4 Un flusso X di valore v è di costo minimo se e solo se non ammette cicli di costo strettamente negativo nel corrispondente grafo incrementale.


TEOREMA 5 Aumentando un flusso v di costo minimo di una quantità d tramite un cammino aumentante P di costo minimo fornisce un flusso di valore v+d ancora di costo minimo.


Dimostrazione Per il Teorema 4 non devono esistere cicli di costo negativo né prima né dopo l’aumento di flusso. Per assurdo supponiamo ne esista uno C dopo tale aumento. Allora esso deve contenere almeno un arco b=(i,j) di P. Ma allora l’insieme di archi P C\ deve contenere un cammino aumentante di costo strettamente inferiore a quello di P, che non sarebbe stato un cammino di costo minimo.


Un poco di storia del Flusso di Minimo Costo


Anno                            Autore(i) Complessita’


1961                Busacker & Gowen < n3 C

1967                Klein < n3 C

1972                Edmonds & Karp mn2 logC

1980                Rock mn2(log n) logD

1984                Tardos m4

1984                Orlin m2(log n)(m+n log n)

1985                Fujishige m3(log n)

1986                Galil & Tardos n2(log n)(m+n log n)

1987                Goldberg & Tarjan log(nD)min


dove                D massimo costo

C massima capacità

m numero archi

n numero nodi


Metodi Semplificati (pseudo-polinomiali)



1 Repeat aumentare v cercando ad ogni iterazione il

cammino s-t di costo minimo nel grafo

incrementale.


O(n3C)


2                      Repeat           nella rete formata dagli archi di costo

nullo del grafo incrementale, trovare un

flusso massimo; aggiornare flussi e costi.


O(n2D m log n)


3                      trovare il flusso massimo (con MAX FLOW)

Repeat            trovare ciclo di costo negativo nel grafo

incrementale; cambiare i flussi (almeno un arco diventa saturo).


O(nm log n + mC n3)


Applicazioni del Flusso di Costo Minimo


Problema di Trasporto


Nei problemi di trasporto si ha un insieme di nodi “sorgente” S, un insieme di nodi di “destinazione” D, e un insieme di nodi di “transito” T. Il flusso totale uscente da un nodo i di S non può essere maggiore di ai , quello entrante in un nodo j di D non può essere maggiore di bj , mentre il flusso totale entrante in un nodo di T è sempre uguale a quello uscente. Perché il problema sia ammissibile la sommatoria degli ai deve essere non inferiore a quella dei bj . Tale problema si trasforma in uno di Flusso di Costo Minimo aggiungendo: un nodo sorgente s con archi verso tutti i nodi di S di capacità ai e costo nullo, un nodo destinazione t a cui si arriva da tutti i nodi di D con archi di capacità bj e costo nullo.


Problema di Assegnamento


Nella versione classica è il problema di assegnare n lavori a n operatori a costo totale minimo (o profitto massimo). I vincoli esprimono il fatto che ogni lavoro deve essere assegnato ad un solo operatore e che un operatore può essere assegnato ad un solo lavoro. E’ facile vedere che anche questo problema è un particolare problema di flusso di costo minimo: in effetti è un problema di trasporto con T=F, S un insieme di nodi rappresentanti gli operatori, D un insieme dello stesso numero di nodi rappresentante i lavori, ogni arco indicante se un operatore può essere assegnato ad un certo lavoro e con quale costo, con gli archi tutti di capacità uguale ad 1.


Cammino Minimo


Basta porre nella formulazione generale le capacità uguali ad 1 ed il valore v del flusso richiesto uguale a n-1. Da notare che il metodo di Dijkstra lavora sul problema duale di quello ottenuto con questa formulazione.








Privacy

Articolo informazione


Hits: 15
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2020