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

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


== Ալգորիթմ ==


== Ոչ պաշտոնական բնութագրում ==
Բոլոր հոսքերը զրոյացնում ենք։ Մնացորդային ցանցը սկզբնապես համընկնում է ելակետային ցանցի հետ։
Մնացորդային ցանցում գտնում ենք աղբյուրից դեպի հոսանք ցանկացած ուղի։ Եթե այդպիսի ուղի չկա՝ կանգ ենք առնում։
Գտնված ուղով բաց ենք թողնում (այն անվանվում է մեծացնող ուղի կամ մեծացնող շղթա) առավելագույն հնարավոր հոսքը։
Մնացորդային ցանցում հայտնաբերված ուղու վրա փնտրում ենք նվազագույն բացթողնման հնարավորությամբ եզրը 
  
    
      
        
          c
          
            min
          
        
      
    
    {\displaystyle c_{\min }}
  ։
Գտնված ուղու յուրաքանչյուր եզրի համար մեծացնում ենք հոսքը 
  
    
      
        
          c
          
            min
          
        
      
    
    {\displaystyle c_{\min }}
  , իսկ դրա հակառակ ուղղությամբ՝ փոքրացնում 
  
    
      
        
          c
          
            min
          
        
      
    
    {\displaystyle c_{\min }}
  ։
Մոդիֆիկացնում ենք մնացորդային ցանցը։ Բոլոր եզրերի համար գտնված ուղու, ինչպես նաև դրան հակառակ եզրի վրա, դուրս ենք բերում նոր բացթողման հնարավորությունը։ Եթե այն դառնում է ոչ զրոյական, ապա եզրն ավելացնում ենք մնացորդային ցանցին, իսկ եթե զրոյական է՝ ջնջում ենք։
Վերադառնում ենք 2-րդ քայլին։Կարևոր է, որ ալգորիթմը չի հստակեցնում, թե կոնկրետ որ ուղին ենք մենք փնտրում 2-րդ քայլում կամ, թե ինչպես ենք մենք դա անում։ Այդ իսկ պատճառով ալգորիթմը համապատասխանում է միայն ամբողջ բացթողնման հնարավորություններին, սակայն անգամ դրանց համար, բացթողնման հնարավորությունների մեծ նշանակությունների դեպքում, այն կարող է շատ երկար աշխատել։ Եթե բացթողնման հնարավորությունները նյութական են, ապա կարող է անվերջ երկար աշխատել՝ չհամընկնելով օպտիմալ որոշմանը։ (տես օրինակը ներքևում).
Եթե փնտրենք ոչ ցանկացած ուղի, այլ ամենակարճը, կստացվի Էմոնդս-Կարպի ալգորիթմը կամ Դինիցի ալգորիթմը.


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

  
    
      
         
        f
        (
        u
        ,
        v
        )
        ⩽
        c
        (
        u
        ,
        v
        )
      
    
    {\displaystyle \ f(u,v)\leqslant c(u,v)}
  . 
  
    
      
        u
      
    
    {\displaystyle u}
  -ից 
  
    
      
        v
      
    
    {\displaystyle v}
   հոսանքը չի գերազանցում բացթողնման հնարավորությունը։

  
    
      
         
        f
        (
        u
        ,
        v
        )
        =
        −
        f
        (
        v
        ,
        u
        )
      
    
    {\displaystyle \ f(u,v)=-f(v,u)}
  .

  
    
      
         
        
          ∑
          
            v
          
        
        f
        (
        u
        ,
        v
        )
        =
        0
        ⟺
        
          f
          
            i
            n
          
        
        (
        u
        )
        =
        
          f
          
            o
            u
            t
          
        
        (
        u
        )
      
    
    {\displaystyle \ \sum _{v}f(u,v)=0\Longleftrightarrow f_{in}(u)=f_{out}(u)}
   բոլոր կապերի համար 
  
    
      
        u
      
    
    {\displaystyle u}
  , բացի 
  
    
      
        s
      
    
    {\displaystyle s}
   և 
  
    
      
        t
      
    
    {\displaystyle t}
  ։ Կապերի միջով անցնելիս հոսքը չի փոխվում։Մնացորդային ցանց 
  
    
      
        
          G
          
            f
          
        
        (
        V
        ,
        
          E
          
            f
          
        
        )
      
    
    {\displaystyle G_{f}(V,E_{f})}
   - բացթողման հնարավորությունով ցանց 
  
    
      
        
          c
          
            f
          
        
        (
        u
        ,
        v
        )
        =
        c
        (
        u
        ,
        v
        )
        −
        f
        (
        u
        ,
        v
        )
      
    
    {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
   և առանց հոսքի։
Մուտք Գրաֆ 
  
    
      
        
        G
      
    
    {\displaystyle \,G}
   բացթողման հնարավորությունով 
  
    
      
        
        c
      
    
    {\displaystyle \,c}
  , աղբյուր 
  
    
      
        
        s
      
    
    {\displaystyle \,s}
   և հոսանք 
  
    
      
        
        t
      
    
    {\displaystyle \,t}
  Ելք Առավելագույն հոսք 
  
    
      
        
        f
      
    
    {\displaystyle \,f}
   
  
    
      
        
        s
      
    
    {\displaystyle \,s}
  -ից 
  
    
      
        
        t
      
    
    {\displaystyle \,t}
  

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

  
    
      
        f
        (
        u
        ,
        v
        )
        ←
        f
        (
        u
        ,
        v
        )
        +
        
          c
          
            f
          
        
        (
        p
        )
      
    
    {\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}
  

  
    
      
        f
        (
        v
        ,
        u
        )
        ←
        f
        (
        v
        ,
        u
        )
        −
        
          c
          
            f
          
        
        (
        p
        )
      
    
    {\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}
  Ուղին կարող է գտնվել.օրինակ, լայնությամբ փնտրման (Էմոնդս-Կարպի ալգորիթմ) կամ խորությամբ փնտրման 
  
    
      
        
          G
          
            f
          
        
        (
        V
        ,
        
          E
          
            f
          
        
        )
      
    
    {\displaystyle G_{f}(V,E_{f})}
  ։


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


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

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

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


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


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


== Հղումներ ==
Визуализатор алгоритма Archived 2015-04-02 at the Wayback Machine.
Реализация поиска максимального потока методом Форда-Фалкерсона на Java