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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Ալգորիթմի գաղափարը հետևյալում է.սկզբնապես հոսքի մեծությանը վերագրվում է 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-ով։

Չհամընկնող ալգորիթմի օրինակ[խմբագրել]

Ford-Fulkerson forever.svg

Դիտարկենք հետևյալ ցանցի օրինակը \ 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" Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում:[1]

Օրինակ[խմբագրել]

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

Ուղի Բացթողնման հնարավորություն Արդյունք
Սկզբնական տրանսպորտային ցանց Ford-Fulkerson example 0.svg
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
Ford-Fulkerson example 1.svg
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
Ford-Fulkerson example 2.svg
1998 քայլ հետո …
Վերջնական ցանց Ford-Fulkerson example final.svg

Հղումներ[խմբագրել]

Ծանոթագրություններ[խմբագրել]

  1. Zwick, Uri (21 August 1995). «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.