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

Ֆորդ-ֆալկերսոնի ալգորիթմ
Տեսակ	ալգորիթմ և գրաֆների ալգորիթմ
Անվանված է	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$ $\,p$ $\,s$ $\,s$ -ից $\,t$ $\,t$ $\,G_{f}$ $\,G_{f}$ , այնպիսին, որ $\,c_{f}(u,v)>0$ $\,c_{f}(u,v)>0$ բոլոր եզրերի համար $(u,v)\in p$ $(u,v)\in p$ ։
1. Գտնել $\,c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\}$
2. Յուրաքանչյուր եզրի համար $(u,v)\in p$ $(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 քայլ հետո …
	Վերջնական ցանց