Maksimalaus srauto tinkle radimo algoritmai


Maksimalus srautas. Fordo fulkersono algoritmas. Edmonds-karp. Maksimalusis srautas. Grafu srautas. Fordo fulkersono metodas. Fordo – fulkersono algoritmas. Maksimalus srautas grafai. 3 grafu lankstinukas word. Maksimalaus srauto tinkle radimo algoritmų analizė.

Informatikos laboratorinis darbas. Maksimalaus srauto tinkle radimo algoritmai. Rasti maksimalų srautą duotajame tinkle. Analizė. Sprendimo metodai. Ford-fulkerson metodas. Edmonds-karp algoritmas. Push-relabel (goldbergo) metodas. Išvados.


Maksimalaus srauto radimo uždavinys dažnai tiesiogiai nagrinėja praktinės situacijos galimus sprendimus. Srautu galima vaizduoti skysčių tėkmę vamzdžiais, elektros grandinę ar transporto tinklą. Norint maksimaliai išnaudoti tokių objektų galimybes tenka spręsti maksimalaus srauto uždavinį.

Tinklas yra atvaizduojamas orientuotu grafu. Lanko kryptis nurodo galimą tėkmės kryptį. Taip pat kiekvienas lankas turi sau priskirtą skaičių – lanko pralaidumą. Jis parodo maksimalų kiekį kuris gali pratekėti atitinkamu lanku. Trap viršūnių u ir v gali būti tik vienas iš dviejų lankų: (u;v) arba (v;u). Jei jie yra abu, tai vienas lankas yra perteklinis nes jį galima eliminuoti sumažinant kito lanko pralaidumą esamo lanko pralaidumu. Tinklas turi ypatingas viršūnes: šaltinį ir nuotakį. Iš šaltinio išeina pradinis srautas ir jis turi keliauti į nuotakį. Būtent maksimalų srauto kiekį kurį galima perkelti iš šaltinio į nuotakį ir vaidname maksimaliu srvisoms viršūnėms išskyrus s ir t turi būti tenkinamas kirchofo dėsnis: srauto kiekis kuris įteką į tam tikrą viršūnę turi būti lygus srauto kiekiui kuris iš jos išteka. Tai reiškia, kad srautas nesikaupiapirmasis buvo sukurtas didinančiomis grandinėmis pagrįstas ford-fulkerson metodas. Tai gana paprastas, nesunkiai suprogramuojamas ir lengvai suprantamas metodas. Tačiauu šio metodo trūkumas buvo tas, kad jo efektyvumas yra apribotas ne tinklo dydžio charakteristikomis, o maksimalasu srauto dydžiu. Be to tinklams kurių lankų pralaidumai nėra sveikieji skaičiai, šis metodas apskritai gali lėtai konverguoti ir galiausiai duoti neteisingą atsakymą. Vėliau buvo pasiūlytas kitas šio algoritmo variantas, kai srautas visada didinamas mažiausios (trumpiausios) didinančios grandinės srautu. Šis algoritmas vadinamas edmonds-karp vardu ir neturi anksčiau minėtų trūkumų.

Vėliau buvo pradėti kurti kitais metodais pagrįsti algoritmai leidžiantys srautą skaičiuoti efektyviau. Šie metodai tapo vis sudėtingesni ir sunkiau suprantami, tačiau algoritmo efektyvumas šiuo metu jau yrašis metodas yra paremtas didinančiųjų grandinių tinkle radimu. Didinančioji grandinė – tai toks kelias nuo šaltinio s iki nuotakio t, kad visos jį sudarančios briaunos tenkina vieną iš sąlygų.

Briauna nukreipta tiesiogiai iš u į v ir šios briaunos esamas srautas yra mažesnis ukiekviena iš tokių grandinių galima perkelti dalį srauto iš šaltinio į nuotakį ir taip didinti bendrą srautą.

Maksimalaus srauto tinkle radimo algoritmai. (2010 m. Kovo 03 d.). http://www.mokslobaze.lt/algoritmai-maksimalaus-srauto-tinkle-radimo-algoritmai-lab5.html Peržiūrėta 2016 m. Gruodžio 11 d. 00:29