Maksimalaus srauto algoritmo sudėtingumas

Įvadas

Maksimalus srautas (angl. maximum flow) yra sąvoka iš grafų teorijos, kuri apibūdina didžiausią galimą srautą, kurį galima perduoti nuo šaltinio iki tikslinio taško tam tikrame orientuotame grafe su srautui praleidžiamomis briaunomis ir įrenginiais.

Pagrindinis tikslas yra rasti didžiausią galimą kiekį, kurį galima perduoti nuo vieno taško iki kito per tinklą, kurį sudaro briaunos ir taškai. Tai gali turėti praktinių taikymų, pavyzdžiui, tinklų optimizavime, keliais, krovinių pervežimo logistikoje ir pan.

Maksimalaus srauto paieškos algoritmai yra naudojami grafų teorijoje ir tinklų analizėje. Šie algoritmai yra skirti rasti didžiausią galimą srautą nuo šaltinio iki tikslinio taško tinkle. Pagrindinė idėja yra optimizuoti srautą per tinklą, atsižvelgiant į tam tikrus apribojimus arba savybes. Vienas iš maksimalaus srauto paieškos algoritmų yra Edmondso – Karpo, Dinitzo algoritmas(1972).

Edmundso - Karpo algoritmas yra gobšus algoritmas, apskaičiuojantis didžiausią srautą srautotinkle, taip pat yra platesnio Fordo-Fulkersono metodo taikymas.

Darbo tikslas:

Ištirti Edmondso - Karpo algoritmo sudėtingumą. Motyvuoti programavimo kalbos (įrankio) pasirinkimą. Paminėti iškilusias problemas. Palyginti rezultatus su teoriniu sudėtingumu.

Darbo eiga

• C++ kalboje sukuriamas Edmondso - Karpo algoritmo kodas. Keičiamas grafo viršūnių skaičius – 50, 100, 500, 600, 700, 1000.

• Programa sugeneruoja atstumus tarp viršūnių nuo 1 iki 10.

• Su kiekvienu viršūnių kiekiu atliekama po 10 bandymų.

• Išvedamas vidurkis.

• Rezultatai pateikiami lentelėje ir diagramoje.

Edmondso – Karpo, Dinitzo algoritmas(1972)

Informatikos srityje Edmondsas – Karpas algoritmas yra Fordo – Fulkersono metodo įgyvendinimas, skirtas apskaičiuoti didžiausią srautą srauto tinkle O(|V||E|²) laike. Algoritmą pirmą kartą paskelbė J. Dinitzas 1970 m., o 1972 m. nepriklausomai paskelbė J. Edmondsas ir R. Karpas. Dinitzo algoritmas apima papildomų metodų, kurie sumažina veikimo laiką iki O(|V||E|²).

Diniko algoritmas arba Dinitzo algoritmas yra labai polinominis algoritmas, skirtas apskaičiuoti didžiausią srautą srauto tinkle, kurį 1970 m. sukūrė Izraelio kompiuterių mokslininkas J. Dinitzas. Įsijungia algoritmas O(|V|²|E|) laiko ir yra panašus į

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!