Forum@DeGiorgi :: Pogledajte temu - Uvjet za kraj Ford-Fulkersonovog algoritma

Uvjet za kraj Ford-Fulkersonovog algoritma

through

[^/[Print]\]

Forum@DeGiorgi -> Matematičko modeliranje

#1: Uvjet za kraj Ford-Fulkersonovog algoritma Autor/ica: Melkor, Lokacija: Void

Postano: 16:06 sri, 14. 12. 2005
—
Ford-Fulkersonov algoritam staje kad više ne možemo pronaći put od izvora do ponora na kojem bi se tok mogao povećati. To znači da bi na kolokviju morali provjeriti sve moguće putove tražeći eventualno povećanje. No, za neki malo veći graf takvih putova može biti jako puno. Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

#2: Re: Uvjet za kraj Ford-Fulkersonovog algoritma Autor/ica: Casper, Lokacija: Krk

Postano: 17:09 sri, 14. 12. 2005
—

Melkor (napisa):

Ford-Fulkersonov algoritam staje kad više ne možemo pronaći put od izvora do ponora na kojem bi se tok mogao povećati. To znači da bi na kolokviju morali provjeriti sve moguće putove tražeći eventualno povećanje. No, za neki malo veći graf takvih putova može biti jako puno. Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

Na kolokviju neces dobit nesto ultra tesko, obicno su grafovi takvi da se jednostavno vidi kad vise nema prolaza do ponora

#3: Re: Uvjet za kraj Ford-Fulkersonovog algoritma Autor/ica: goranm,

Postano: 18:00 sri, 14. 12. 2005
—

Melkor (napisa):

Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

Slaba i jaka dualnost.
Vrijednos max toka je ⇐ kapacitetu minimalnog i-p reza, odnosno
jaka dualnost - vrijednost max toka = kapacitet min i-p reza.

#4: Re: Uvjet za kraj Ford-Fulkersonovog algoritma Autor/ica: Melkor, Lokacija: Void

Postano: 20:39 sri, 14. 12. 2005
—

Lord Sirius (napisa):

Melkor (napisa):

Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

Slaba i jaka dualnost.
Vrijednos max toka je ⇐ kapacitetu minimalnog i-p reza, odnosno
jaka dualnost - vrijednost max toka = kapacitet min i-p reza.

To sam i pomislio, ali čini mi se da je bolja strategija prvo pronaći maksimalan tok.

Ništa, idem to malo bolje proučiti. Inače, ako nekog zanima, guglanje pojma "ford-fulkerson" daje korisne rezultate. Mogu se naći zgodne demonstracije algoritma napravljene u Javi.

#5: Re: Uvjet za kraj Ford-Fulkersonovog algoritma Autor/ica: vili, Lokacija: Keglić

Postano: 21:46 sri, 14. 12. 2005
—

Melkor (napisa):

Lord Sirius (napisa):

Melkor (napisa):

Ima li kakav koristan trik kako bismo mogli zaključiti da se tok ne može dalje maksimizirati?

Slaba i jaka dualnost.
Vrijednos max toka je ⇐ kapacitetu minimalnog i-p reza, odnosno
jaka dualnost - vrijednost max toka = kapacitet min i-p reza.

Da, ali mislim da je Lord Sirius imao na umu:

ako ti je preveliki graf za provjeravat, a imaš tok za koji sumnjaš da bi mogao biti maksimalan, probaj pronaći i-p rez istog tog kapaciteta i to ti je dovoljno zbog jake dualnosti.

To je alternativni algoritam, ali mislim da je u praksi lakše doći do toga da ne postoji put proširenja.

I slažem se s Casperom, neće u kolokviju dolaziti toliki grafovi da bi to bio problem.

#6: Autor/ica: goranm,

Postano: 0:31 čet, 15. 12. 2005
—
U svakom slučaju, za dovoljno jednostavni graf netreba puno vremena da se uoči minimalni i-p rez.
I-p rez se može smatrati kao metoda provjere rješenja.
Ako se popune kapacitieti, ali tako da su manji od kapaciteta pronađenog minimalnog i-p reza, onda očito se još negdje mora ići u suprotnom smjeru.
Uglavnom, korisno je znati jaku dualnost. Smile

#7: Autor/ica: Nesi,

Postano: 0:34 čet, 15. 12. 2005
—
u praxi, iz vlastitog gusta sam isla rjesavati sve zadatake koji su bili dopstuni online prije 2 godine.... u prosjeku ti treba 5 minuta krampanja ili vise ako zeznes, ili si gotov 3-4 poteza, ili je toilko ocito da ti je dosadno pisati jer moras step by step iako mislis da vidis rjesenje (i onda zbilja to bude)

zbilja ugodni zadaci.... samo preporucam ici ih vjezbati... rijesiti ih barem 5-10... samostalno Wink

na kolokviju gdje sam bila je zbilaj bilo gotovo u cca 5 ocitih poteza, a onaj prekrivac jedinica u matrici je trebalo 3 poteza... Smile

#8: Autor/ica: filipnet, Lokacija: cvrsto na stolici

Postano: 2:32 čet, 15. 12. 2005
—
mene malo bune te dualnosti, tj. dal uvijek i-p rez mora biti jednak maksimalnom toku da zadatak bude tocan? po slaboj dualnosti znaci da ne mora, ako sam dobro skuzio?

#9: Autor/ica: Braslav,

Postano: 8:39 čet, 15. 12. 2005
—
@filipnet
Naravno da ne, samo minimalan i-p rez je jednak maksimalnom toku, nekakav drugi je zapravo strogo veci.

Inace ja te zadatke rjesavam onako vrticki, donesem bojice pa
svaki put povecanja toka mi je linija druge boje. Na kraju to izgleda
puno preglednije nego da sam crtao 3-4 posebna grafa, a da ne kazem koliko je brze gotovo.

@melkor
Isprva tok je uglavnom takav da (gotovo) kojim god putem krenuo
imas put povecanja toka. Kasnije kada si nakon kojih 3-4 takva puta vec se priblizio krajnjem rijesenju mozes krenuti zaokruzivati cvorove do kojih mozes doci putem povecanja.
Samim trazenjem puta povecanja mozes vidjeti minimalan i-p rez
jer jednostavno vidis cvorove u koje mozes doci povecanjam, a u chije susjede ne mozes jer npr ulazi maksimalno sto upoce moze izaci. Ako to vrijedi za svaki cvor sa "granice izmedu cvorova prve i druge vrste" tada
imas mak tok i min i-p rez.

Forum@DeGiorgi -> Matematičko modeliranje

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.