Appunti di Ricerca operativa

Algoritmo per il calcolo del cammino minimo in un grafo numerato topologicamente

F.L'algoritmo termina e questo grafo ora è numerato topologicamente: qualunque arco vado a considerare l'origine ha un numero più piccolo della destinazione. A questo punto per definire il cammino minimo posso utilizzare un banalissimo ciclo for:

Continuando con l'esempio di prima, posso etichettare l'etichetta del nodo origine [0,-1] (il primo elemento è il costo, il secondo elemento è come sono arrivato nel nodo corrente, -1 significa che sono partito proprio da tale nodo).

Nel nodo 2 posso arrivarci soltanto partendo dal nodo 1 [4,1]: il cammino minimo vale 4, e il secondo numero sta ad indicare che sono partito dal nodo 1.

Nel nodo 3 ci posso arrivare o dal nodo 2 o dal nodo 1, ma non essendoci l'arco 2-3, associo l'etichetta [3,1].

Nel nodo 4 ci posso arrivare sia da 2 che da 1 che da 3, per cui considero il minimo tra (4+3,2,3+2): allora l'etichetta sarà [2,1].

Nel nodo 5 faccio il minimo tra (4+1,2+5): allora...

l'etichetta sarà [5,2]

Nel nodo 6 posso arrivare in modo analogo da 4 e da 3 : [5,4].

Analogo discorso per il nodo 7.

Se leggo a ritroso questo grafo, posso sapere qual è il cammino minimo.

L'albero dei cammini minimi è fatto da questi archi rossi.

Se inizialmente non mi accorgo di avere un grafo aciclico, succede che ad un certo punto numero un nodo, lo elimino, sul sotto-grafo restante non c'è nessun nodo senza archi entranti : concludo dicendo che il mio grafo è un grafo ciclico e non posso continuare con quest'algoritmo (analogodiscorso se ci fossero stati archi con costi negativi).

Grafi ciclici

L'altro caso è quello in cui voglio lavorare su .

Utilizzo quello che viene chiamo algoritmo di Dijkstra : è un label setting su reti anche acicliche che non presentano archi di costo negativo.

Vediamo come funziona con un esempio. La rete è ciclica (2-6-5-2) ma ha tutti costi positivi.

La prima cosa che fa

l'algoritmo è quella dietichettare in modo definitivo il modo origine [0,-1]. Poi considero tutti i nodi raggiungibili da 1 con un solo arco: posso arrivare solo in 2 e in 3. In 2 ci arrivo con un costo pari a 7, in 3 con un costo pari ad 1. A questo punto posso porre l'etichetta di 3[1,1]: il cammino minimo per andare da 1 a 3 è fatto proprio dall'arco 1-3 con costo pari ad 1, perché posso concludere ciò? Perché tra le ipotesi c'è quella che ci dice che nella mia rete non ci sono archi di costo negativo e questa cosa mi basta, perché qualsiasi altro scelgo per arrivare in 3 devo considerare l'arco 1-2 (che costa già 7) e poi devo attraversare altri archi che hanno costo maggiore di 0 e quindi il totale avrà un costo maggiore dell'arco 1-3.

Considero tutti i nodi collegati ad 1 e 3 con un unico arco: 2,5,6. In 2 il modo più conveniente per arrivare è arrivarci da 3 (ho un costo...

6, minore di 7 che è l'arco1-2). In 5 ci arrivo con un costo di 3. In 6 ci arrivo o con 1-3-6 o con 1-2-6. Il valore minimo è quello in 5: Il cammino minimo per arrivare da 1 a 5 è proprio 1-3-5. Possiamo generalizzare il ragionamento: Esempio: Associo ad 1 [0,-1]. Considero i nodi 2,3,4 (li raggiungo con un unico arco). L'insieme S=1. Raggiungo 2 con un costo 10; raggiungo 3 con un costo 7; raggiungo 4 con un costo 5. Il minimo è 5. Quindi il cammino minimo per arrivare in 4 è 1-4, con costo 6. [5,1] L'insieme S=1,4. Posso raggiungere dall'insieme S con un unico arco 2,3,6. Raggiungo 2 con un costo di 10, raggiungo 3 con un costo di 6, raggiungo 6 con un costo di 14. Il minimo è 6. Quindi il cammino minimo per arrivare in 3 è 1-4-3. [6,4] L'insieme S=1,4,3. Posso raggiungere dall'insieme S con un unico arco 2,5,7,6. Raggiungo 2 con un costo minimo di 8, raggiungo 5 con un costo minimo di 6+4=10, raggiungo 7 con 6+9=15, raggiungo

6 con 14. Il minimo è 2. Quindi il cammino minimo per arrivare a 2 è 1-4-3-2. [8,3] L'insieme S=1,4,3,2. Ripeto lo stesso ragionamento: per 5 ho [9,2], per 6 ho [12,5] per 7 ho [15,3]. Posso schematizzare quanto fatto con questo macro-codice: 2 La complessità di quest'algoritmo è O(n): ad ogni iterazione ogni nodo può essere collegato con tutti gli altri nodi. (c'è il file .mos che implementa il codice) Esistono algoritmi più sofisticati che consentono di ridurre la complessità. Vediamo ora degli esempi che hanno anche costi negativi. Vediamolo con un esempio: ad ogni iterazione abbiamo bisogno di una soluzione e quindi come prima soluzione vado a prendere, a partire dal nodo 1, tutti i percorsi fatti da un unico arco (1-2, 1-3, tutto il resto+infinito). Nella seconda iterazione il mio scopo è quello di trovare il valore dei cammini minimi fatti al massimo da 2 archi: per fare questo, dico che l'etichetta di 4

La posso migliorare o passando per il nodo 2. Per cui l'etichetta di 4 diventerà [0,2]. Posso migliorare l'etichetta di 6, diventerà [-2,3]. Non riesco a migliorare l'etichetta di 5 [+infinito].

Nella terza iterazione devo calcolare i cammini minimi nella condizione in cui questi possono contenere al massimo 3 archi: l'unica etichetta migliore che riesco ad ottenere è quella di 5, [-3,6]. Per tutti gli altri nodi non riesco a migliorare niente.

Nella 4 iterazione vado a vedere se riesco a migliorare qualcosa usando percorsi di 4 archi: la nuova etichetta di 2 sarà [0,5], la nuova etichetta di 4 sarà [-1,5].

Nella 5 iterazione vedo se ci sono percorsi di 5 archi migliori di quelli già trovati: no.

A questo punto mi fermo perché posso andare avanti fino all'iterazione pari al numero di archi-1 (in questo caso ho 6 archi, quindi 6-1=5 iterazioni).

Questa è la soluzione.

ATTENZIONE
Il cammino rosso 1-2, non deve essere in rosso.

È un errore. (Altri esempi nelle slides) Questo è il macro-codice dell'algoritmo di Bellman-Ford: SEDICESIMA LEZIONE (04.05.2020) (Spiegazione file .mos degli algoritmi della lezione precedente, vedi registrazione) Parliamo ora del Problema del Massimo Flusso: ho una rete (quindi un grafo) e voglio distribuire su questo grafo un certo prodotto da una o più origini ad una o più destinazioni e voglio trasportare la quantità massima da origine a destinazione. Ho quindi un grafo orientato e ogni arco è caratterizzato da una capacità massima. Inoltre ho due nodi di questo grafo, s e t, detti rispettivamente sorgente e pozzo: in s posso produrre una quantità infinita di flusso, e in t posso assorbire una quantità infinita di flusso. Se la mia rete è questa, una possibile soluzione (non so se è quella ottima), potrebbe essere quella di trasportare 6 quantità di flusso sul percorso 1-4-5-6 (6 perché è).

La capacità massima di 1) ; altre 4 unità le posso trasportare lungo il percorso 1-2-3-6 (4 perché la capacità massima di 3) ; altre 6 unità le posso trasportare lungo il percorso 1-2-5-6 (6 perché l'arco 1-2 ha una capacità residua, in base a quelle già trasportate prima, pari a 6).

Questa sembra una buona soluzione che mi permette di portare da origine a destinazione 16 unità di flusso.

OSS: gli algoritmi che studieremo risolvono il problema con un'origine ed un'unica destinazione. Nel caso in cui così non fosse, è possibile ricondurre il problema al caso in cui ho una sola origine e una sola destinazione: per farlo, aggiungo al mio problema un'origine fittizia s* e una destinazione fittizia t*: questi archi fittizi, poiché non esistono, avranno capacità +infinito. A questo punto risolvere il problema del massimo flusso è esattamente equivalente del risolvere il

problema dello spostare la massima quantità da origine a destinazione. Vediamo ora come deve essere formulato il problema del massimo flusso. Nello scegliere le variabili decisionali, posso scegliere una variabile per ogni arco del grafo: x_ij rappresenta quindi la quantità di flusso che attraversa l'arco (i,j). Poi abbiamo f, che è il flusso totale inviato dalla sorgente alla destinazione (potrei far a meno di tale variabile che misura semplicemente il valore della soluzione). La funzione obiettivo quindi è quella che massimizza f. Per quanto riguarda i vincoli del problema: La prima sommatoria indica l'insieme dei nodi j che sono collegati al nodo i con un arco che va da i a j (somma il flusso su tutti gli archi uscenti dal nodo i, flusso uscente da i). La seconda sommatoria è l'insieme dei nodi entranti nel nodo i (flusso entrante in i, misura il flusso su tutti gli archi entranti nel nodo i). Se i è proprio il nodo origine,volta nel flusso massimo. A ciascun arco del grafo risultante, da ingegnere a lavoro, associo una capacità pari al numero di lavori che l'ingegnere è in grado di svolgere. Infine, a ciascun arco del grafo risultante, da lavoro a t, associo una capacità pari ad 1 per indicare che ogni lavoro deve essere assegnato ad un solo ingegnere. In questo modo, il problema del massimo flusso nel grafo risultante corrisponde al problema di assegnare il massimo numero di lavori agli ingegneri, rispettando le loro capacità. Quindi, se ho a disposizione un algoritmo per risolvere il problema del massimo flusso, posso utilizzarlo per risolvere anche questo problema di assegnamento.volta nella mia soluzione. Diamo ora alcune definizioni: Vediamo un esempio di taglio: immaginiamo di avere questo grafo. In questa configurazione sto trasportando 9 unità di flusso dal nodo 1 al nodo 6. Il taglio individuato dalla linea tratteggiata, distingue Vs e Vt. Se questo è il taglio, qual è la capacità? La capacità del taglio è 9+4=13 (cioè la capacità di 2-4 più la capacità 3-5). Il valore del flusso sul taglio, invece, è 9 (cioè x24-x35-x43). Il flusso è ovviamente minore della capacità del taglio. Il problema del minimo taglio richiede di trovare tra tutti i possibili tagli di un grafo il taglio con la capacità minima.