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

Ֆորդ-ֆալկերսոնի ալգորիթմ
Տեսակ	ալգորիթմ և գրաֆների ալգորիթմ
Անվանված է	L. R. Ford, Jr.? և D. R. Fulkerson?

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

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

Ալգորիթմ խմբագրել

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

Բոլոր հոսքերը զրոյացնում ենք։ Մնացորդային ցանցը սկզբնապես համընկնում է ելակետային ցանցի հետ։
Մնացորդային ցանցում գտնում ենք աղբյուրից դեպի հոսանք ցանկացած ուղի։ Եթե այդպիսի ուղի չկա՝ կանգ ենք առնում։
Գտնված ուղով բաց ենք թողնում (այն անվանվում է մեծացնող ուղի կամ մեծացնող շղթա) առավելագույն հնարավոր հոսքը։
1. Մնացորդային ցանցում հայտնաբերված ուղու վրա փնտրում ենք նվազագույն բացթողնման հնարավորությամբ եզրը $c_{\min }$ ։
2. Գտնված ուղու յուրաքանչյուր եզրի համար մեծացնում ենք հոսքը $c_{\min }$ , իսկ դրա հակառակ ուղղությամբ՝ փոքրացնում $c_{\min }$ ։
3. Մոդիֆիկացնում ենք մնացորդային ցանցը։ Բոլոր եզրերի համար գտնված ուղու, ինչպես նաև դրան հակառակ եզրի վրա, դուրս ենք բերում նոր բացթողման հնարավորությունը։ Եթե այն դառնում է ոչ զրոյական, ապա եզրն ավելացնում ենք մնացորդային ցանցին, իսկ եթե զրոյական է՝ ջնջում ենք։
Վերադառնում ենք 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$

$f(u,v)\leftarrow 0$ բոլոր եզրերի համար $\,(u,v)$
Քանի դեռ ուղի կա $\,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\geq 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$ " Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում^[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 քայլ հետո …
	Վերջնական ցանց