Autore Topic: Esercizi Preflow Flush  (Letto 341 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Esercizi Preflow Flush
« il: 28 Dicembre 2010, 13:56:43 »
Dato che sul libro non ce ne sono di svolti, ne ho ripresi un paio del MaxFlow e li ho risolti con quest'algoritmo.
Posto quelli fatti oggi a titolo di confronto, nel caso qualcuno dovesse decidere di provarli (molto spesso mi sono reso conto che applicavo l'algoritmo senza rendermi conto di fare cose non concesse...).
Come criterio di massima, la scelta dei nodi ha seguito il seguente ordine:
  • Prima quelli con d maggiore, poiché più portati a scaricare flusso
  • A parità di d, arbitrariamente sono scelti quelli con indice di nodo minore
  • Tra gli archi ammissibili a disposizione, scegli quello che ha maggiore disponibilità di transito

Anziché fare millemila grafi, riporto le singole iterazioni indicando la scelta fatta e le etichette ai nodi (se cambiano).
I valori di d ed e sono relativi al grafo di scarto.
Per indicare il flusso da (s)caricare al posto di epsilon uso la lettera w, che non mi va di perdere tempo con latex e simboli a caso.

E3.11

Inizializzazione del problema e prima compilazione del grafo di scarto.
1) e = -5, d = 7
2) e = 1, d = 2
3) e = 0, d = 2
4) e = 4, d = 2
5) e = 0, d = 1
6) e = 0, d = 1
7) e = 0, d = 0

IT1
Scegli (2) da scaricare su (2,5) con w = 1

IT2
2) e = 0, d = 2
5) e = 1, d = 1
Scegli (4) da scaricare su (4,6) con w = 2

IT3
4) e = 2, d = 2
6) e = 2, d = 1
Scegli (5) da scaricare su (5,7) con w = 1

IT4
5) e = 0, d = 1
7) e = 1, d = 0
Scegli (6) da scaricare su (6,7) con w = 2

IT5
6) e = 0, d = 1
7) e = 3, d = 0
Per tutti i nodi attivi (cioè solo (4)) non ci sono archi ammissibili. Esegue relabel e porta d = 3 (l minore dei successori e (3) con d = 2

IT6
4) e = 2, d = 3
Scegli (4) da scaricare su (4,3) con w = 2

IT7
3) e = 2, d = 2
4) e = 0, d = 3
Scegli (3) da scaricare su (3,5) con w = 2

IT8
3) e = 0, d = 2
5) e = 2, d = 1
Scegli (5) da scaricare su (5,7) con w = 2

IT9
5) e = 0, d = 1
7) e = 5, d = 0
1) e = -5, d = 7
Sono finiti i nodi attivi e il problema è bilanciato.
STOP



3.13

Inizializzazione del problema e prima compilazione del grafo di scarto.
s) e = -9, d = 8
1) e = 6, d = 2
2) e = 3, d = 2
3) e = 0, d = 2
4) e = 0, d = 1
5) e = 0, d = 2
6) e = 0, d = 1
d) e = 0, d = 0

IT1
Scegli (1) da scaricare su (1,4) con w = 4

IT2
1) e = 2, d = 2
4) e = 4, d = 1
Scegli (2) da scaricare su (2,6) con w = 3

IT3
2) e = 0, d = 2
6) e = 3, d = 1
Scegli (4) da scaricare su (4,d) con w = 4

IT4
4) e = 0, d = 1
d) e = 4, d = 0
Scegli (6) da scaricare su (6,d) con w = 3

IT5
6) e = 0, d = 1
d) e = 7, d = 0
L'unico nodo attivo (1) non ha archi ammissibili. Relabel con d = 3.

IT6
1) e = 2, d = 3
Scegli (1) da scaricare su (1,2) con w = 1

IT7
1) e = 1, d = 3
2) e = 1, d = 2
Tra i due nodi attivi (1) e (2), nessuno dei quali presenta archi ammissibili, rietichetta (2) che potrebbe ancora far defluire del flusso verso (d).
Porta d = 2 (il successore a d minore è (3) con d =2)

IT8
2) e = 1, d = 3
Scegli (2) da scaricare su (2,3) con w = 1

IT9
2) e = 0, d = 3
3) e = 1, d = 2
Scegli (3) da scaricare su (3,6) con w = 1

IT10
3) e = 0, d = 2
6) e = 1, d = 1
Scegli (6) da scaricare su (6,d) con w = 1

IT11
6) e = 0, d = 1
d) e = 8, d = 0
L'unico nodo attivo (1) non ha archi ammissibili. Occorre rietichettare.
L'unico successore è la sorgente, per cui d = 9

IT12
1) e = 1, d = 9
Scegli (1) da scaricare su (1,s) con w = 1

IT13
1) e = 0, d = 9
s) e = -8, d = 8
d) e = 8, d = 0
I nodi attivi sono finiti.
Il problema è bilanciato.
STOP
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Esercizi Preflow Flush
« Risposta #1 il: 29 Dicembre 2010, 10:37:14 »
Per cercare di limitare il numero di iterazioni ho provato a seguire l'algoritmo HIGHEST LABEL PREFLOW-PUSH che seleziona sempre il nodo attivo con l'etichetta d(i) più elevata. In caso di parità ho scelto di procedere nell'ordine di numerazione dei nodi.

3.11

1a IT:
     Nodo attivo 2. PUSH w = 1 su (2,5).
     e(2) diventa 0
     e(5) diventa 1

2a IT:
     Nodo attivo 4. PUSH w =  2 su (4,6).
     e(4) diventa 2
     e(6) diventa 2

3a IT:
     Nodo attivo 4. Non esistono archi ammissibili uscenti da 4, per cui etichetto il nodo con d(4) = d(3)+1 = 3.

4a IT:
     Nodo attivo 4. PUSH w = 2 su (4,3).
     e(4) diventa 0
     e(3) diventa 2

5a IT:
     Nodo attivo 3. PUSH w = 2 su (3,5).
     e(3) diventa 0
     e(5) diventa 3

6a IT:
     Nodo attivo 5. PUSH w = 3 su (5,7).
     e(5) diventa 0

7a IT:
     Nodo attivo 6. PUSH w = 2 su (6,7).
     e(6) diventa 0

8a IT:
     Non vi sono nodi attivi. STOP.
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esercizi Preflow Flush
« Risposta #2 il: 29 Dicembre 2010, 13:14:05 »
In effetti ho dato priorità al deflusso piuttosto che al relabelling, ma il numero di iterazioni è abbastanza elevato a priori.
Sarà per via del legame più profondo con Fulkerson, ma sia io sia Dex preferiamo decisamente il primo algoritmo.
A mano, purtroppo, tutta questa grande efficienza non la si vede...  ::)
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"

Offline Mithrandir

  • Maestro Geek
  • *
  • *
  • *
  • Post: 1.157
  • Reputazione: 44
  • Sesso: Maschio
  • Battlemage
Re:Esercizi Preflow Flush
« Risposta #3 il: 29 Dicembre 2010, 16:22:14 »
In effetti in questi esercizi si risparmiamo al massimo 3 o 4 iterazioni (nel 3.12).

La seconda variante mi pare però più intuitiva. La filosofia può essere riassunta con "prima di iniziare a lavorare sui nodi a valle, preoccupati di tutti i nodi a monte".

All'esame non credo che sia concesso scegliere, nella traccia ci sarà scritto quale algoritmo usare (Ford Fulkerson?).

PS:
In effetti ho dato priorità al deflusso piuttosto che al relabelling.
Nel primo post però hai scritto come criterio di scelta esattamente quello dell'HIGHEST LABEL.

« Ultima modifica: 29 Dicembre 2010, 16:24:44 da Mithrandir »
Spoiler (click to show/hide)
Gandalf? Yes... that was what they used to call me. Gandalf the Grey. That was my name.
I am Gandalf the White. And I come back to you now - at the turn of the tide.


Offline Cosmos

  • Signore dei Geek
  • *
  • *
  • *
  • Post: 1.493
  • Reputazione: 48
  • Sesso: Maschio
  • Is this the end?
Re:Esercizi Preflow Flush
« Risposta #4 il: 29 Dicembre 2010, 16:54:59 »
PS:Nel primo post però hai scritto come criterio di scelta esattamente quello dell'HIGHEST LABEL.

Quella nota sull'aver preferito il deflusso è legata proprio al fatto che mi sia reso conto solo dopo il tuo intervento di non aver (sempre) seguito il principio scelto...  :-[
« Ultima modifica: 29 Dicembre 2010, 16:57:30 da Cosmos »
Spoiler: XKCD (click to show/hide)



Regola Aurea: Qualsiasi calcolo ridicolmente complesso a vedersi, ed ancor più complesso a farsi, porterà certamente ad un risultato nullo...

Corollario: Se il risultato non si annulla, sarà 2\pi

Se X è un insieme non vuoto su cui è definita una relazione d'ordine parziale tale che ogni sua catena possiede un maggiorante, allora contiene almeno un elemento massimale. Chiaro no?

In trepidante attesa della pubblicazione di "Orchi, Antilopi e Calamari - Vol. I"