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

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

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

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

Ալգորիթմ[խմբագրել | խմբագրել կոդը]

Ոչ պաշտոնական բնութագրում[խմբագրել | խմբագրել կոդը]

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

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

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

Պաշտոնական նկարագրություն[խմբագրել | խմբագրել կոդը]

Տրված է գրաֆը բացթողնման հնարավորությունով և հոսքով՝ u-ից v եզրերի համար։ Պետք է գտնել s աղբյուրից t հոսանքին առավելագույն հոսքը։ Ալգորիթմի յուրաքանչյուր քայլի համար գործում են բոլոր հոսքերի համար գործող պայմանները։

  • . -ից հոսանքը չի գերազանցում բացթողնման հնարավորությունը։
  • .
  • բոլոր կապերի համար , բացի և ։ Կապերի միջով անցնելիս հոսքը չի փոխվում։

Մնացորդային ցանց - բացթողման հնարավորությունով ցանց և առանց հոսքի։

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

  1. բոլոր եզրերի համար
  2. Քանի դեռ ուղի կա -ից , այնպիսին, որ բոլոր եզրերի համար ։
    1. Գտնել
    2. Յուրաքանչյուր եզրի համար

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

Բարդությունը[խմբագրել | խմբագրել կոդը]

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

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

Ford-Fulkerson forever.svg

Դիտարկենք հետևյալ ցանցի օրինակը աղբյուրով, հոսանքով, = , = , = եզրերի բացթողնման հնարավորություններով և մնացած բոլոր եզրերի բացթողնման հնարավորություններով, որոնք հավասար են ամբողջ թվին. հաստատունը ընտրված է այնպես, որ . Օգտագործում ենք ուղիներ մնացորդային գծագրից, որոնք բերված են աղյուսակում, ընդ որում՝ , և .

Քայլ Գտնված ուղի Ավելացված հոսք Մնացորդային բացթողնման հնարավորություններ
0
1
2
3
4
5

Նկատենք, որ 1 քայլից հետո, ինչպես և 5 քայլից հետո , և եզրերի մնացորդային հնարավորությունները ունեն , և ձևը, համապատասխանաբար, որևէ բնական համար։ Դա նշանակում է, որ կարող ենք օգտագործել , , և մեծացող ուղիները անվերջ անգամներ և այդ եզրերի մնացորդային բացթողնման հնարավորությունները միշտ կլինեն նույն ձևով։ 5-րդ քայլից հետո ամբողջական հոսքը հավասար է ։ Անվերջ ժամանակահատվածում ամբողջական հոսքը կհամընկնի , այն դեպում, որ առավելագույն հոսքը հավասար է " Այսպիսով, ալգորիթմը ոչ միայն անվերջ երկար է աշխատում, այլ նաև լավագույն որոշմանը չի համընկնում։[1]

Օրինակ[խմբագրել | խմբագրել կոդը]

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

Ուղի Բացթողնման հնարավորություն Արդյունք
Սկզբնական տրանսպորտային ցանց Ford-Fulkerson example 0.svg


Ford-Fulkerson example 1.svg


Ford-Fulkerson example 2.svg
1998 քայլ հետո …
Վերջնական ցանց Ford-Fulkerson example final.svg

Հղումներ[խմբագրել | խմբագրել կոդը]

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

  1. Zwick Uri (օգոստոսի 21, 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