Ֆորդ-ֆալկերսոնի ալգորիթմ

Ֆորդ–Ֆալկերսոնի ալգորիթմը որոշում է տրանսպորտային ցանցերում առավելագույն հոսքերի հայտնաբերման խնդիրը:

Ալգորիթմի գաղափարը հետևյալում է.սկզբնապես հոսքի մեծությանը վերագրվում է 0: $f(u,v)=0$ նշանակություն` բոլոր $u,v \in V$ համար: Ապա հոսքի մեծությունը ինտերատիվ մեծանում է` մեծացնող ուղու ընդլայնման հետևանքով: ( s աղբյուրից t հոսանքին ուղին, որի երկայնքով կարելի է ավելի շատ հոսք ուղարկել): Գործընթացը շարունակվում է, քանի դեռ հնարավոր է գտնել մեծացնող ուղի:

Ոչ պաշտոնական բնութագրում

1. Բոլոր հոսքերը զրոյացնում ենք: Մնացորդային ցանցը սկզբնապես համընկնում է ելակետային ցանցի հետ:
2. Մնացորդային ցանցում գտնում ենք աղբյուրից դեպի հոսանք ցանկացած ուղի. Եթե այդպիսին ուղի չկա` կանգ ենք առնում:
3. Գտնված ուղով բաց ենք թողնում (այն անվանվում է մեծացնող ուղի կամ մեծացնող շղթա) առավելագույն հնարավոր հոսքը:
   1. Մնացորդային ցանցում հայտնաբերված ուղու վրա փնտրում ենք նվազագույն բացթողնման հնարավորությամբ եզրը $c_\min$:
   2. Գտնված ուղու յուրաքանչյուր եզրի համար մեծացնում ենք հոսքը $c_\min$, իսկ դրա հակառակ ուղությամբ` փոքրացնում $c_\min$:
   3. Մոդիֆիկացնում ենք մնացորդային ցանցը: Բոլոր եզրերի համար գտնված ուղու, ինչպես նաև դրան հակառակ եզրի վրա, դուրս ենք բերում նոր բացթողման հնարավորությունը: Եթե այն դառնում է ոչ զրոյական, ապա եզրն ավելացնում ենք մնացորդային ցանցին, իսկ եթե զրոյական է` ջնջում ենք:
4. Վերադառնում ենք 2-րդ քայլին:

Կարևոր է, որ ալգորիթմը չի հսատկեցնում, թե կոնկրետ որ ուղին ենք մենք փնտրում 2-րդ քայլում կամ, թե ինչպես ենք մենք դա անում: Այդ իսկ պատճառով ալգորիթմը համապատասխանում է միայն ամբողջ բացթողնման հնարավորություններին, սակայն անգամ դրանց համար, բացթողնման հնարավորությունների մեծ նշանակությունների դեպքում, այն կարող է շատ երկար աշխատել: Եթե բացթողնման հնարավորությունները նյութական են, ապա կարող է անվերջ երկար աշխատել` չհամընկնելով օպտիմալ որոշմանը: (տես օրինակը ներքևում).

Եթե փնտրենք ոչ ցանկացած ուղի, այլ ամենակարճը, կստացվի Էմոնդս-Կարպի ալգորիթմը կամ Դինիցի ալգորիթմը.

Պաշտոնական նկարագրություն

Տրված է $G(V,E)$ գրաֆը $c(u,v)$ բացթողնման հնարավորությունով և $f(u,v)=0$ հոսքով` u-ից v եզրերի համար: Պետք է գտնել s աղբյուրից t հոսանքին առավելագույն հոսքը. Ալգորիթմի յուրաքանչյուր քայլի համար գործում են բոլոր հոսքերի համար գործող պայմանները:

• $\ f(u,v) \leqslant c(u,v)$. $u$-ից $v$ հոսանքը չի գերազանցում բացթողնման հնարավորությունը:
• $\ f(u,v) = - f(v,u)$.
• $\ \sum_v f(u,v) = 0 \Longleftrightarrow f_{in}(u) = f_{out}(u)$ բոլոր կապերի համար $u$, բացի $s$ և $t$: Կապերի միջով անցնելիս հոսքը չի փոխվում:

Մնացորդային ցանց $G_f(V,E_f)$ — բացթողման հնարավորությունով ցանց $c_f(u,v) = c(u,v) - f(u,v)$ և առանց հոսքի:

Մուտք Գրաֆ $\,G$ բացթողման հնարավորությունով $\,c$, աղբյուր $\,s$ և հոսանք $\,t$
Ելք Առավելագույն հոսք $\,f$ $\,s$-ից $\,t$

1. $f(u,v) \leftarrow 0$ բոլոր եզրերի համար $\,(u,v)$
2. Քանի դեռ ուղի կա $\,p$ $\,s$-ից $\,t$ $\,G_f$, այնպիսին, որ $\,c_f(u,v) > 0$բոլոր եզրերի համար $(u,v) \in p$:
   1. Գտնել $\,c_f(p) = \min\{c_f(u,v) \;|\; (u,v) \in p\}$
   2. Յուրաքանչյուր եզրի համար $(u,v) \in p$
      1. $f(u,v) \leftarrow f(u,v) + c_f(p)$
      2. $f(v,u) \leftarrow f(v,u) - c_f(p)$

Ուղին կարող է գտնվել.օրինակ, լայնությամբ փնտրման (Էմոնդս-Կարպի ալգորիթմ)կամ խորությամբ փնտրման $G_f(V,E_f)$:

Բարդությունը

Արդեն գոյություն ունեցող հոսքերին հոսք ավելացնելով առավելագույն հոսքը կստացվի այն դեպքում, երբ հնարավոր չի լինի գտնել մեծացող հոսք: Այդուհանդերձ, եթե բացթողնման հնարավորության մեծությունը իռացիոնալ թիվ է, ապա ալգորիթմը կարող է անվերջ աշխատել: Ամբողջ թվերի դեպքում այդպիսի խնդիր չի առաջանում և աշխատանքի ժամանակը սահմանափակ է O(E*f), որտեղ E — գրաֆում եզրերի թիվն է, f — գրաֆում առավելագույն հոսքը, քանի որ ամեն մեծացող ուղի կարող է գտնվել O(E) համար և մեծացնում է հոսքը առնվազն 1-ով:

Չհամընկնող ալգորիթմի օրինակ

Դիտարկենք հետևյալ ցանցի օրինակը $\ s$ աղբյուրով, $\ t$ հոսանքով, $\ e_1$ = $\ 1$, $\ e_2$ = $r=(\sqrt{5}-1)/2$, $\ e_3$ = $\ 1$ եզրերի բացթողնման հնարավորություններով և մնացած բոլոր եզրերի բացթողնման հնարավորություններով, որոնք հավասար են $M \ge 2$ ամբողջ թվին. $\ r$ հաստատունը ընտրված է այնպես, որ $\ r^2 = 1 - r$. Օգտագործում ենք ուղիներ մնացորդային գծագրից, որոնք բերված են աղյուսակում, ընդ որում` $\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}$, $\ p_2 = \{ s, v_2, v_3, v_4, t \}$ և $\ p_3 = \{ s, v_1, v_2, v_3, t \}$.

Քայլ	Գտնված ուղի	Ավելացված հոսք	Մնացորդային բացթողնման հնարավորություններ
			$e_1$	$e_2$	$e_3$
0			$r^0=1$	$r$	$1$
1	$\{ s, v_2, v_3, t \}$	$1$	$r^0$	$r^1$	$0$
2	$p_1$	$r^1$	$r^2$	$0$	$r^1$
3	$p_2$	$r^1$	$r^2$	$r^1$	$0$
4	$p_1$	$r^2$	$0$	$r^3$	$r^2$
5	$p_3$	$r^2$	$r^2$	$r^3$	$0$

Նկատենք, որ 1 քայլից հետո, ինչպես և 5 քայլից հետո $e_1$, $e_2$ և $e_3$ եզրերի մնացորդային հնարավորությունները ունեն $r^n$, $r^{n+1}$ և $0$ ձևը, համապատասխանաբար, որևէ բնական $n$ համար. Դա նշանակում է, որ կարող ենք օգտագործել $p_1$, $p_2$, $p_1$ և $p_3$ մեծացող ուղիները անվերջ անգամներ և այդ եզրերի մնացորդային բացթողնման հնարավորությունները միշտ կլինեն նույն ձևով: 5-րդ քայլից հետո ամբողջական հոսքը հավասար է $1 + 2(r^1 + r^2)$. Անվերջ ժամանակահատվածում ամբողջական հոսքը կհամընկնի $\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r$, այն դեպում, որ առավելագույն հոսքը հավասար է $2M + 1$. Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում:

Օրինակ

Հետևյալ օրինակը ցույց է տալիս Ֆորդ-Ֆալկերսոնի ալգորիթմի առաջին քայլերը չորս կապերով տրասպորտային ցանցում` A աղբյուրով ևD հոսքով: Այս օրինակը ցույց է տալիս ամենավատ դեպքը: Լայնությամբ փնտրման դեպքում ալգորիթմին պետք կգա ընդամենը 2 քայլ.

Ուղի	Բացթողնման հնարավորություն	Արդյունք
	Սկզբնական տրնսպորտային ցանց
$A,B,C,D$	$\min(c_f(A,B), c_f(B,C), c_f(C,D))=$ $\min(c(A,B)-f(A,B) ,c(B,C)-f(B,C), c(C,D)-f(C,D))=$ $\min(1000-0, 1-0, 1000-0)=1$
$A,C,B,D$	$\min(c_f(A,C), c_f(C,B), c_f(B,D))=$ $\min(c(A,C)-f(A,C), c(C,B)-f(C,B), c(B,D)-f(B,D))=$ $\min(1000-0, 0-(-1), 1000-0)=1$
	1998 քայլ հետո …
	Վերջնական ցանց

Հղումներ

• Визуализатор алгоритма
• Реализация поиска максимального потока методом Форда-Фалкерсона на Java

Ծանոթագրություններ

Մեդիաֆայլեր այստեղ՝ Ֆորդ-ֆալկերսոնի ալգորիթմ