Հապսրոֆտ-Կառպ ալգորիթմ

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

Համակարգչային գիտության մեջ Հապսրոֆտ-Կառպ ալգորիթմը ալգորիթմ է, որը որպես մուտք վերցնում է երկչափանի գրաֆը և արտադրում որպես թողարկման առավելագույն համապատասխան հզորությունը – ամենաշատ հնարավոր եզրերի սահմանումը այն հատկությամբ, որ ոչ մի երկու եզր չեն կիսում վերջնակետը:Այն վատագույն դեպքում աշխատում է O(m√n) ժամանակում,որտեղ "O" վերաբերում է մեծ O նշումին, m-ը գրաֆում եզրերի թիվն է, և n-ը գրաֆի գագաթների թիվն է: Խիտ գրաֆիդեպքում ժամանակային սահմանը դառնում է O(n5/2), և պատահական գրաֆի համար այն աշխատում է մոտավորապես գծային ժամանակում:

Ալգորիթմը հայտնաբերվել է Ջոն Հապսրոֆտի և Ռիչարդ Կառպի կողմից 1973 թվականին: Ինչպես և նախորդ համապատասխանեցնող մեթոդներում, ինչպիսին Հունգարական ալգորիթմը և Կաղապար:Harvtxt աշխատանքն է, Հապսրոֆտ-Կառպ ալգորիթմը բազմակի անգամ շատացնում է մասնակի համապատասխանեցումների չափը մեծացման ճանապարհ գտնելու միջոցով: Ինչևէ, յուրաքանչյուր բազմակրկնություն մեծացման ճանապարհ գտնելու փոխարեն, ալգորիթմը գտնում են մի շարք առավելագույն սեղմ մեծացման ճանապարհներ:Որպես արդյունք միայն O(√n) բազմակրկնություններ են անհրաժեշտ: Նույն սկզբունքն է օգտագործվել ավելի բարդ ալգորիթմեր զարգացնելու նպատակով ոչ երկչափ համապատասխանությունների համար նույն ասիմտոտիկ աշխատաժամանակով ինչպիսին Հապսրոֆտ-Կառպ ալգորիթմն է:

Մեծացման ուղիներ[խմբագրել]

Գագաթը,որը չի հանդիսանում սահմանի վերջնակետ որոշ մասնակի համապատասխանող M-երի համար, անվանվում է ազատ գագաթ: Հիմնական գաղափարը,որի վրա հիմնվա է ալգորիթմը այն է,որ մեծացման ուղինեը, ուղին, որը սկսվում է ազատ գագաթից, վերջանում է ազատ գագաթում,և միմյանց են հաջորդում չգերազանցված և համապատասխան ճանապարհի եզրերը: Եթե Mn-ի համապատասխան չափն է,և P-ն հանդիսանում է մեծացման չափը M-ի համար, ապա սիմետրիկ տարբերությունըերկու եզրերի միջ, M ⊕ P, կստեղծեն համապատասխան n + 1 չափ: Ուստի,մեծացման ուղիները փնտրելով, ալգորիթմը կարող է մեծացնել համապատասխանությունների չափը:

Եվ ընդհակառակը, ենթադրենք , որ համապատասխան M-ը օպտիմալ չէ, և թող P-ն լինի M ⊕ M*սիմետրիկ տարբերությունը, որտեղ M*-ը օպտիմալ համապատասխանուրյունն է :Այսպիսով P-ն պետք է ձևավորի հավաքածու առանձնացված մեծացման ուղիներից և շրջաններից կամ ուղիներից, որտեղ համապատասխան ու անհամապատասխան եզրերը հավասար թվով են. չափերի տարբերությունը M և M*-ի միջև P-ում ուղիների ավելացումների թիվն և: Ուստր, եթե ոչ մի մեծացման ճանապարհ չի գտնվում, ապա ալգորիթմը ապահով դադարեցվում է, քանի որ այս դեպքում Mպետք է լինի օպտիմալ:

Համապատասխանող խնդրի մեծացման ճանապարհը սերտորեն կապված է մեծացմանճանապարհների հետ,որը բխում է առավելագույն հոսքի խնդիրից, ճանապարհներ, որոնց երկայնքով կարելի է ավելացնել հոսքի գումարը հոսքի տերմինալների միջև: Հնարավոր է փոխակերպել երկչափ համապատասխան խնդիրը առավելագույն հոսքի առանձին դեպքի, այնպես որ համապատասխաման խնդրի միմյանց հաջորդող ուղիները դառնում են հոսքերի խնդրի մեծացման ճանապարհ: [1]Ի դեպ, տեխնիկայի ընդհանրացումը, որը օգտագործվում է Հապսրոֆտ-Կառպ ալգորիթմում կամայական հոսքի ցանցերի համար հայտնի է որպես Դենիսի ալգորիթմ:

Ալգորիթմ[խմբագրել]

Ենթադրենք U-ն և V-ն երկու մասի բաժանված G-ի երկու հավաքածուներ են, և U-ի համապատասխանությունը V-ի հետ ցանկացած ժամանակ ներկայացված է որպես M-ի սահմանում:

Ալգորիթմը կատարվում է փուլերով:Յուրաքանչյուր փուլ բաղկացած է հետևյալ քայլներց.

  • Առաջինը ամենալայնի որոնումը փոխում է գրաֆի սյուները տողերով: Uում ազատ սյուները օգտագործվում են որպես փնտրման սկզբնական սյուներ,և ձևավորում է փոփոխված առաջին տողը: Փնտրման առաջին մակարդակում, միայն իրարից տարբեր եզրեր կարող են տեղաշարժվել(քանի որ U-ի ազատ սյուները ըստ սահմանման չեն դրան կարող կցվել որևէ համապատասխան եզրի); փնտրման հաջորդ մակարդակներում, փոփոխված եզրերը պահանջում են իրար համապատասխան և անամապատասխան հաջորդականություն: Այսպիսով, երբ փնտրում ենք իրավահաջորդներ U-ի սյուներից, ապա միայն անհամապատասխան եզրերը կարող են փոխարինվել, մինչդեռ V-ի սյուներից միայն համապատասխան եզրերը կարող են փոխարինվել: Որոնումը դադարում է k-ի առաջին տողում, որտեղ V-ում մի կամ ավելի ազատ սյուների են հասնում:
  • Բոլոր ազատ սյուները V-ում k տողով հավաքված են F հավաքածույում: Այսինքն, v սյունը դրվում է F-ում, միայն և միայն այն դեպքում,եթե այն ավարտվում է ամենակարճ արգումենտի ճանապարհով:
  • Ալգորիթմը գտնում է խաչվող գագաթների առավելագույն հավաքածուն k լայնությամբ արգումենտի ուղիներում: Այս հավաքածուն կարող է հաշվարկվել առաջինը ըստ խորության որոնում միջոցով F-ից դեպի U-ի ազատ սյուներ,որոնումը առաջնորդելու համար ագտագործելով լայնություն առաջին շերտը. առաջինը ըստ խորության որոնումը թույատրվում է միայն եզրերը կենտրոնացնելու համար,որը հանգեցնում է նախորդ շերտում չօգտագործված սյան, և ուղիները առաջինը ըստ խորության որոնուման ծառում պետք է միմյանց հաջորդեն համապատասխան և անամապատասխան եզրերը: Հենց որ արգումենտի ճանապարհը գտնվում է,որը ներառում է F-ի մի որևէ սյուն,առաջինը ըստ խորության որոնումը շաչունակվում է հաջորդ սյունից:
  • Այս ճանապարհով գտնված յուրաքանչյուր ուղի օգտագործվում է M-ը մեծացնելու համար:

Ալգորիթմը դադարում է,երբ էլ ոչ մի մեծացման ճանապարհներ չեն գտնվում առաջինը ըստ խորության որոնուման ժամանակ առաջին փուլում:

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

Ամեն փուլը բաղկացած է պարզ առաջինը ամենալայնի և առաջինը ամենախորի որոնումից: Այսպիսով մեկ փուլը կարող է իրականացվել գծային ժամանակահատվածի ընթացքում:

Այս եղանակով , առաջին √n փուլը, գրաֆում n բարձրությունների և m եզրերի հետ, պահանջում է O(m √n) ժամանակահատված:

Կարելի է ցույց տալ, որ յուրաքանչյուր փուլը, մեծացնում է ամենակարճ արգումենտի ճանապարհի երկարությունը առնվազն մեկով: Փուլը գտնում է տվյալ երկարությամբ արգումենտի ճանապարհի մաքսիմալ շարքը, այնպես որ մնացած ճանապարհները պետք է լինեն ավելի երկար: Այդ պատճառով էլ ալգորիթմի √n սկզբնական փուլը ամբողջական է, հետևաբար մնացած ամենակարճ ճանապարհը պետք է լինի √n–ի եզրերը: Այնուամենայնիվ սիմետրիկ տարբերություն հնարավոր օպտիմալ համաձայնության և գտնված M-ի սիմետրիկությունը ,սկզբնական էտապում ձևավորում է բարձրությունների շարքը և ալտերնատիվ ցիկլերը: Եթե այս շարքի յուրաքանչյուր ճանապարհի երկարությունը առնվազն √n է, ապա հավաքածուի մեջ կարող է լինել √m և օպտիմալ համաձայնության չաթը կարող է տարբերվել M-ի չափերից ոչ ավել √n –ի եզրերից: Ալգորիթմի յուրաքանչյուր էտապից հետո մեծանում է համապատասխանությունների թիվը: Քանի որ ալգորիթմը ընդհանուր առմամբ կատարում է 2√n փուլը , այն պահանջում է O(m √n) ընդհանուր ժամանակահատված վատագույն դեպքում: Օրինակ միջին դեպքում նոսր երկկողմանի պատահական գրաֆները (բարելավելով իր նախորդ արդյունքները Motwani 1994 թ.) ցույց տվեցին, որ ամենայն հավանականությամբ բոլոր ոչ-օպտիմալ համապատասխանեցումները եղել են լոգարիթմական երկարությունների ավելանալու ճանապարհին: Որպես հետևանք , այս գրաֆներում, Հապսրոֆտ-Կառպի ալգորիթմը պահանջում է O(log n) փուլեր և O(m log n) ընդհանուր ժամանակահատված:


Համեմատություն այլ երկչափ համապատասխանեցված ալգորիթմների հետ[խմբագրել]

Նոսր գրաֆների համար,Հապսրոֆտ-Կառպ ալգորիթմը շարունակում է ունենալ ամենահայտնի 'վատագույն դեպքի' կատարումը,բայց խիտ գրաֆների համար օգտագործում է ավելի ժամանակակից ալգորիթմ Կաղապար:Harvtxt-ի կողմից հասնելով փոքր - ինչ ավելի լավ ժամանակի սահմանապակում O(n1.5(m/log n)0.5): Նրանց ալգորիթմը հիմնված է հրման-վերապիտակավորման առավելագույն հոսքի ալգորիթմի օգտագործման վրա և հետո ,երբ այս ալգորիթմի ստեղծած համապատասղանեցումը մոտենում է օպտիմալ սահմանին, անցում է կատարվում Հապսրոֆտ-Կառպի եղանակին:

Մի շարք հեղինակներ հանդես են եկել երկչափ համապատասխանեցված ալգորիթմների փորձարարական համեմատություններով: Դրանց արդյունքները ընդհանուր առմամբ հակված են ցույց տալու,որ Հապսրոֆտ-Կառպի եղանակը գործնականում այնքան լավը չէ, ինչքան տեսականորեն. այն գերազանցված է ինչպես պարզ առաջինը ամենալայնի և առաջինը ամենախորի ռազմավարություններով արգումենտի ճանապարհներ գտնելու հարցում, և հրման-վերապիտակավորման տեխնիկայով: [2]

Ոչ երկչափ գրաֆներ[խմբագրել]

Ամենակարճ արգումենտի ուղիների առավելագույն շարքը գտնելու նույն գաղափարը աշխատում է նաև ոչ երկչափ գրաֆներում առավելագույն արտադրողական համապատասխանությունների փնտրման ժամանակ, և նույն պատճառներով էլ ալգորիթմը,որը հիմնված է այս մտքի վրա վերցնում է O(√n) փուլերը: Ինչևէ, ոչ երկչափ գրաֆների համար, յուրաքանչյուր փուլում արգումենտի ճանապարհ գտնելու խնդիրը ավելի դժվար է:Հիմնվելով մի քանի դանդաղ նախորդների աշխատանքի վրա, Կաղապար:Harvtxt ցույց տվեց, թե ինչպես պետք է իրականացնել փուլերը գծային ժամանակում , որի արդյունքում կառուցվում է ոչ երկչափ համապատասխանեցված ալգորիթմը,նույն սահմանված ժամանակուն ինչես որ Հապսրոֆտ-Կառպի ալգորիթմը երկչափ գրաֆների համար: Micali–Vazirani-ի տեխնիկան բարդ է,և նրա հեղինակները չեն ապահովում իրենց արդյունքների լրիվ ապացույցներ. այս խնդրի այլընտրանքային մեթոդը ավելի ուշ բացատրվել է այլ հեղինակների կողմից:[3]

Կեղծ կոդ[խմբագրել]

/*

  G = G1  G2  {NIL}

where G1 and G2 are partition of graph and NIL is a special null vertex

*/
function BFS ()
    for v in G1
        if Pair_G1[v] == NIL
            Dist[v] = 0
            Enqueue(Q,v)
        else
            Dist[v] = ∞
    Dist[NIL] = ∞
    while Empty(Q) == false
        v = Dequeue(Q)
        for each u in Adj[v]
            if Dist[ Pair_G2[u] ] == ∞
                Dist[ Pair_G2[u] ] = Dist[v] + 1
                Enqueue(Q,Pair_G2[u])
    return Dist[NIL] != ∞
function DFS (v)
    if v != NIL
        for each u in Adj[v]
            if Dist[ Pair_G2[u] ] == Dist[v] + 1
                if DFS(Pair_G2[u]) == true
                    Pair_G2[u] = v
                    Pair_G1[v] = u
                    return true
        Dist[v] = ∞
        return false
    return true
function Hopcroft-Karp
    for each v in G
        Pair_G1[v] = NIL
        Pair_G2[v] = NIL
    matching = 0
    while BFS() == true
        for each v in G1
            if Pair_G1[v] == NIL
                if DFS(v) == true
                    matching = matching + 1
    return matching

Նշումներ[խմբագրել]

Մանրամասներ[խմբագրել]