Stručni rad
Guraj-Promijeni visinu algoritam za pronalaženje maksimalnog protoka mreže
Mario Zekić
; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet
Ivica Nakić
; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet
Sažetak
Problem maksimalnog toka i njemu dualan problem, problem minimalnog reza, iznimno su korisni u modeliranju mnogih problema koji sadrže mreže, bilo cestovne, željezničke, računalne ili društvene. Obično modeliramo tok nekog materijala iz jednog dijela mreže u drugi, a tok mogu biti automobili, vlakovi, bitovi, preporuke i mnogi drugi predmeti i koncepti. Zanimljivo je da su se ova dva problema također pokazala korisnima u problemima modeliranja za koje nije očito da uključuju mreže ili protok materijala. Jedan takav primjer izložit ćemo u ovom članku.
U ovom članku izložit ćemo jedan od najefikasnijih poznatih algoritama za rješavanje problema maksimalnog toka, guraj-promijeni visinu algoritam za pronalaženje maksimalnog protoka mreže. Uz teorijsku pozadinu algoritma guraj-promijeni visinu, osvrnut ćemo se i na implementaciju tog algoritma u Javascriptu, kao i neke varijante algoritma koje nude određena poboljšanja.
Ključne riječi
optimizacija na grafovima; problem maksimalnog reza
Hrčak ID:
307610
URI
Datum izdavanja:
31.8.2023.
Posjeta: 132 *