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

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

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

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

Ալգորիթմ

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

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

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

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

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

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

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

Մնացորդային ցանց ${\displaystyle G_{f}(V,E_{f})}$ - բացթողման հնարավորությունով ցանց ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ և առանց հոսքի։

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

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

Ուղին կարող է գտնվել.օրինակ, լայնությամբ փնտրման (Էմոնդս-Կարպի ալգորիթմ) կամ խորությամբ փնտրման ${\displaystyle G_{f}(V,E_{f})}$։

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

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

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

Դիտարկենք հետևյալ ցանցի օրինակը ${\displaystyle \ s}$ աղբյուրով, ${\displaystyle \ t}$ հոսանքով, ${\displaystyle \ e_{1}}$ = ${\displaystyle \ 1}$, ${\displaystyle \ e_{2}}$ = ${\displaystyle r=({\sqrt {5}}-1)/2}$, ${\displaystyle \ e_{3}}$ = ${\displaystyle \ 1}$ եզրերի բացթողնման հնարավորություններով և մնացած բոլոր եզրերի բացթողնման հնարավորություններով, որոնք հավասար են ${\displaystyle M\geq 2}$ ամբողջ թվին. ${\displaystyle \ r}$ հաստատունը ընտրված է այնպես, որ ${\displaystyle \ r^{2}=1-r}$. Օգտագործում ենք ուղիներ մնացորդային գծագրից, որոնք բերված են աղյուսակում, ընդ որում՝ ${\displaystyle \ p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}$, ${\displaystyle \ p_{2}=\{s,v_{2},v_{3},v_{4},t\}}$ և ${\displaystyle \ p_{3}=\{s,v_{1},v_{2},v_{3},t\}}$.

Քայլ	Գտնված ուղի	Ավելացված հոսք	Մնացորդային բացթողնման հնարավորություններ
			${\displaystyle e_{1}}$	${\displaystyle e_{2}}$	${\displaystyle e_{3}}$
0			${\displaystyle r^{0}=1}$	${\displaystyle r}$	${\displaystyle 1}$
1	${\displaystyle \{s,v_{2},v_{3},t\}}$	${\displaystyle 1}$	${\displaystyle r^{0}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
2	${\displaystyle p_{1}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{1}}$
3	${\displaystyle p_{2}}$	${\displaystyle r^{1}}$	${\displaystyle r^{2}}$	${\displaystyle r^{1}}$	${\displaystyle 0}$
4	${\displaystyle p_{1}}$	${\displaystyle r^{2}}$	${\displaystyle 0}$	${\displaystyle r^{3}}$	${\displaystyle r^{2}}$
5	${\displaystyle p_{3}}$	${\displaystyle r^{2}}$	${\displaystyle r^{2}}$	${\displaystyle r^{3}}$	${\displaystyle 0}$

Նկատենք, որ 1 քայլից հետո, ինչպես և 5 քայլից հետո ${\displaystyle e_{1}}$, ${\displaystyle e_{2}}$ և ${\displaystyle e_{3}}$ եզրերի մնացորդային հնարավորությունները ունեն ${\displaystyle r^{n}}$, ${\displaystyle r^{n+1}}$ և ${\displaystyle 0}$ ձևը, համապատասխանաբար, որևէ բնական ${\displaystyle n}$ համար։ Դա նշանակում է, որ կարող ենք օգտագործել ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, ${\displaystyle p_{1}}$ և ${\displaystyle p_{3}}$ մեծացող ուղիները անվերջ անգամներ և այդ եզրերի մնացորդային բացթողնման հնարավորությունները միշտ կլինեն նույն ձևով։ 5-րդ քայլից հետո ամբողջական հոսքը հավասար է ${\displaystyle 1+2(r^{1}+r^{2})}$։ Անվերջ ժամանակահատվածում ամբողջական հոսքը կհամընկնի ${\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}$, այն դեպում, որ առավելագույն հոսքը հավասար է ${\displaystyle 2M+1}$" Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում^[1]։

Օրինակ

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

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

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

1. Zwick, Uri (1995 թ․ օգոստոսի 21). «The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate». Theoretical Computer Science. 148 (1): 165–170. doi:10.1016/0304-3975(95)00022-O.

Արտաքին հղումներ

• Визуализатор алгоритма Արխիվացված 2015-04-02 Wayback Machine
• Реализация поиска максимального потока методом Форда-Фалкерсона на Java Արխիվացված 2012-01-03 Wayback Machine