Ағын желісінде максималды ағынды есептеу алгоритмі
Ford–Fulkerson algorithm
Ford-Fulkerson әлгоритмі: ағын желісінде максималды ағынды (немесе ең төменгі кесіндіні) есептеу. 1956 ж. жасалған, тиімді әдіс, ағын жолдарын іздейді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ағымдық желідегі максималды ағынды есептеу алгоритмі (эквивалентті түрде; ең кішкентай кесім)
Algorithm to compute the maximum flow in a flow network (equivalently; the minimum cut)
Форд-Фулкерсон әдісі немесе Форд-Фулкерсон алгоритмі (FFA) – ағымдық желідегі максималды ағынды есептейтін ашкөз алгоритм. Қалдық графта ағымды арттыру жолдарын табу тәсілі толыққанды сипатталмағандықтан немесе әртүрлі орындалу уақыттары бар бірнеше іске асырылымдарда көрсетілгендіктен, кейде ол "алгоритм" емес, "әдіс" деп аталады. Ол 1956 жылы Л.Р. Форд кіші және Д.Р. Фулкерсон тарапынан жарияланды. "Форд-Фулкерсон" атауы Форд-Фулкерсон әдісінің толыққанды анықталған іске асырылымы болып табылатын Эдмондс-Карп алгоритмі үшін де жиі қолданылады. Алгоритмнің негізгі идеясы мынадай: бастапқы түйінден (көзден) соңғы түйінге (тұнбаға) дейін жол бар болғанда, және жолдың барлық қабырғаларында қолжетімді сыйымдылық болса, біз ағынды осы жолдардың біреуі арқылы жібереміз. Содан кейін біз тағы бір жол іздейміз, және т.б. Қолжетімді сыйымдылығы бар жол – ағымды арттыру жолы деп аталады.
The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method. The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an augmenting path.
Күрделілігі
Ағынды арттыру жолын графиктегі қалыптасқан ағынға қосу арқылы, егер графикте ағынды арттыру жолы табылмайтын болса, максималды ағынға жетеді. Дегенмен, мұндай жағдайдың ешқашан тумауы мүмкін, сондықтан алгоритм аяқталса ғана жауаптың дұрыс болатынына кепілдік беруге болады. Егер алгоритм шексіз жұмыс істейтін болса, ағын тіпті максималды ағынға да жақындамайды. Алайда, мұндай жағдай тек иррационалды ағын мәндерінде ғана орын алады. Сыйымдылықтар бүтін сандар болған жағдайда, Форд-Фулкерсон алгоритмінің орындалу уақыты (үлкен О нотациясын қараңыз) шектеледі, мұнда – графиктегі қабырғалар саны, ал – графиктегі максималды ағын. Бұл әрбір ағынды арттыру жолын уақыт ішінде табуға болады, және ағын кем дегенде бірлікке артады, жоғарғы шегі . Форд-Фулкерсон алгоритмінің өзгеруі, яғни Эдмондс-Карп алгоритмі, кепілдік берілген аяқталумен және максималды ағын мәніне тәуелсіз орындалу уақытымен сипатталады және уақыт ішінде жұмыс істейді.
By adding the flow augmenting path to the flow already established in the graph, the maximum flow will be reached when no more flow augmenting paths can be found in the graph. However, there is no certainty that this situation will ever be reached, so the best that can be guaranteed is that the answer will be correct if the algorithm terminates. In the case that the algorithm runs forever, the flow might not even converge towards the maximum flow. However, this situation only occurs with irrational flow values. When the capacities are integers, the runtime of Ford–Fulkerson is bounded by (see big O notation), where is the number of edges in the graph and is the maximum flow in the graph. This is because each augmenting path can be found in time and increases the flow by an integer amount of at least , with the upper bound
A variation of the Ford–Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds–Karp algorithm, which runs in time.
Интегралды мысал
Келесі мысалда Форд-Фулкерсон алгоритмінің 4 түйінді, бастапқы және соңғы ағыс желісіндегі алғашқы қадамдары көрсетілген. Бұл мысал алгоритмнің ең нашар жағдайдағы қызметін көрсетеді. Әр қадамда желі арқылы тек бірлік ағын жіберіледі. Егер ендігі бірінші іздеу қолданылса, тек екі қадам ғана қажет болар еді. Жол Сыйымдылығы Нәтижесіндегі ағыс желісі Бастапқы ағыс желісі 1998 жылдан кейін тағы көп қадамдар Соңғы ағыс желісі.
The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source and sink This example shows the worst case behaviour of the algorithm. In each step, only a flow of is sent across the network. If breadth first search were used instead, only two steps would be needed. Path Capacity Resulting flow network Initial flow network After 1998 more steps Final flow network
Жолды тапқан кезде ағынның қалай бастапқы түйінден соңғы түйінді қарай "кері итерілетінін" байқаңыз.
Notice how flow is "pushed back" from to when finding the path .