Es Flusso Max
Clicca QUI per vedere il messaggio nel forum |
| Gimmy |
Ecco il domandone... Dato un grafo come costruisco il relativo grafo incrementale a seconda se i valori sugli archi sono capacità superiore-costo unitario oppure capacità superiore-flusso inviato?
Grazie :) |
| spenk.85 |
il grafo incrementale è sempre capacità residua nel verso di percorrenza del arco orginale, capacità deflusso (flusso mandato) nell'arco di ritorno.
esempio: arco originale s->b (7 capacità sup, 2 flusso inviato). L'arco sul grafo incrementale sarà: s->b (5) b->a (2).
Scambio di dritte: sai come aggiornare poi il grafo incrementale quando ho trovato un cammino aumentante oppure quando devo cercare il flusso di costo minimo? Mi incarto in quel punto |
| Gimmy |
ok, pero quello che non capivo è che in alcuni esercizi c'è scritto che i valori sugli archi sono capacità superiore, flusso inviato(e si fa come dici tu), ma ci sono altri es dove i valori sugli archi indicano capacità superiore,costo unitario e qui non so come fare...
Per aggiornare il grafo incrementale quando cerchi i cammini per il flusso massimo devi sommare agli archi uscenti del cammino scelto il valore minimo degli archi(ossia il collo di bottiglia) e sottrarlo invece agli archi in uscita. Per esempio se scegli s-a-b-t e il collo di bottiglia è 2, devi sottrarre a tutti gli archi uscenti che collegano i 4 nodi il valore 2 e sommarlo ai relativi archi in entrata.
Cmq guarda la lezione 16-01-2006 presente nell'area filez, che lì è spiegato bene. |
| carla86 |
semplicemente quando nn ce il flusso inviato.. parti con le frecce d ritorno a zero.
i costi unitari ti serve per la seconda parte, ossia quando l'esercizio ti chiede se il flusso inviato l'hai inviato a costo min. |
| Gimmy |
| mmm... quindi prima applico l'algoritmo di ford fulkerson per determinare il flusso massimo (ossia cerco i vari cammini da s a t finchè on ottengo un taglio di capacità minima, e fin qui non uso i costi unitari giusto?) poi invece per la seconda parte devo usare i costi unitari, metterli sul grafo appena ottenuto e vedere se ci sono cicli a costo negativo? |
| carla86 |
si esatto.
attenzione ke quando hai il flusso iniziale, non devi partire cn i percorsi da zero ma le capacità sn gia state un po usate... |
| Gimmy |
ok, ora provo a fare qualche esercizio con il flusso...
intanto ho fatto questo con i costi unitari, dovrebbe essere giusto... |
| spenk.85 |
Originally posted by Gimmy
ok, ora provo a fare qualche esercizio con il flusso...
intanto ho fatto questo con i costi unitari, dovrebbe essere giusto...
confermo. l'ho svolto anche io e mi viene lo stesso valore di flusso, taglio etc.. |
| Gimmy |
bella ;)
menter per gli es con il flusso inviato per passare alla rete incrementale devo fare capacità supeiore - flusso inviato (uscente) e flusso inviato (entrante) giusto?
Se invece nella rete incrementale (ottenuta da capacità superiore,flusso inviato) ho già dei possibili tagli non faccio nessun cammino e taglio direttamente? |
| spenk.85 |
se hai già del flusso inviato devi mettere l'arco di ritorno con il valore del flusso, mentre nella direzione dell'arco originale la capacità rimanente (cap tot - flusso inviato).
il taglio da che ne so io è uno soltanto. sostanzialmente dovresti fare così:
-rete incrementale
-controlli la presenza dei cammini aumentanti, se ci sono modifichi la rete incrementale
-quando non hai più cammini allora hai un taglio. per trovare questo taglio parti da nodo di partenza e guardi i nodi che puoi raggiungere, gli altri sono al di la del taglio. Nel esempio dell'esercizio sopra: parti da 1; da 1 non posso andare da nessuna parte, quindi il taglio è tra 1 e tutti gli altri nodi. |
| Gimmy |
| si per il procedimento ok, pero in un es mi è capitato che passando alla rete incrementale avevo già il taglio sul nodo 1 dell'es che abbiamo fatto, cioè praticamente ho già gli archi uscenti dal nodo 1 a 0, e quindi teoricamente potrei già tagliare... |
| spenk.85 |
| si, significa in pratica che non hai nessuno cammino aumentante e il flusso è già instradato in maniera ottimale |
|
|
|
