Didžiausio srauto skaičiavimo algoritmų realizavimas ir analizė
Sunklodas, Vytautas |
Šiame darbe nagrinėjama didžiausio srauto radimo tinkluose problema ir tokių uždavinių sprendimo būdai: Fordo ir Falkersono metodas bei pakėlimo algoritmas. Analitinėje dalyje aprašoma didžiausio srauto radimo tinkluose problema, suformuluojamas pagrindinis uždavinys apie srautus tinkluose, aprašomi pasirinkti sprendimo būdai bei jų sudėtingumo įverčiai, pateikiami algoritmų psiaudokodai bei pagrindinės teoremos ir apibrėžimai. Eksperimentinėje dalyje atliekama realizuotų Fordo ir Falkersono metodo bei pakėlimo algoritmo skaičiavimų analizė. Pateikiami eksperimentinių skaičiavimų metu gauti rezultatai ir jų palyginimas su teoriniais įverčiais. Algoritmų analizei naudojamas tinklas G=(V, E) yra orientuotas, įvertintasis grafas, kurio visos briaunos yra įvertintos neneigiamais skaičiais. Darbą sudaro: įvadas, didžiausio srauto radimo tinkluose problemos analizė, Fordo ir Falkersono metodo aprašymas, pakėlimo algoritmo aprašymas, uždavinių sprendimas panaudojant algoritmus, algoritmų realizacija ir analizė, išvados, literatūros sąrašas.Darbo apimtis be priedų 40 p., 5 lentelės, 23 paveikslai ir 12 bibliografinių šaltinių.Atskirai pridedami darbo priedai.
This paper analyzes the problem of finding the maximum flow in a network and its solutions methods: the Ford-Fulkerson method and the push-relabel algorithm.The analytical part introduces the issue of finding the maximum flow in a network and defines the initial problem. It also provides an overview of the selected solution methods, their weighted complexity, and outlines the main theorems, definitions.The experimental part of this work consists of a thorough analysis of results obtained using implementations of the Ford-Fulkerson method and the push-relabel algorithm. This section dissects the results obtained from the calculations and provides a comparative analysis of these results to theoretical weights. The network used in the analysis, is an oriented, weighted graph, all of its edges having non-negative weights.The paper consists of the following parts: an introduction, the analysis of the problem of maximum flow, an outline of the Ford-Fulkerson method, an outline of the push-relabel algorithm, solutions to problems using these methods, an implementation and analysis of the algorithms, conclusions, references.The scope excl. appendices: 40 pages, 5 tables, 23 illustrations, 12 bibliographical sources.Appendices are supplied separately.