Ամենաերկար ճանապարհի խնդիր

Գրաֆերի տեսության մաթեմատիկական կարգապահությունում, ամենաերկար ճանապարհի խնդիրը տրված գրաֆում մաքսիմալ երկարությամբ պարզ ճանապարհը գտնելու խնդիրն է։ Այդ ճանապարհը կոչվում է պարզ, եթե այն չունի մի քանի կրկնվող գագաթներ։ Ի տարբերություն ամենակարճ ճանապարհի խնդրի, որն օգտագործվում է գտնելու 2 գագաթների միջև ամենակարճ ճանապարհը և կարող էր լուծվել պոլինոմիալ ժամանակում այն գրաֆերում, որոնք չունեն բացասական զանգված ունեցող ցիկլեր, այս խնդրի լուծման տարբերակը NP-ամբողջությունն է, որը նշանակում է, որ օպտիմալ լուծումը չի գտնվի պոլինոմիալ ժամանակում, եթե P = NP.

այս խնդրի լուծման ստանդարտ տարբերակի դեպքում պետք է հաշվի առնել, արդյոք այդ գրաֆը պարունակում է kից մեծ կամ հավասար երկարությամբ պարզ ճանապարհ, որտեղ ճանապարհի երկարությունը պետք է հավասար լինի ճանապարհին եղած գագաթների թվին։

NP-ամբողջություն[խմբագրել | խմբագրել կոդը]

Խնդրի լուծման NP-ամբողջությունը կարող է ցուցադրվել, եթե օգտագործենք Համիլթոնյան ճանապարհի խնդրի կրճատումը։ Իսկապես, եթե որոշակի ընդհանուր գրաֆ ունի համիլթոնյան ճանապարհ, այս ճանապարհը հնարավոր ամենաերկար ճանապարհն է, քանի որ այն անցնում է բոլոր հնարավոր գագաթներով։ Համիլթոնյան ճանապարհի խնդիրը լուծելու համար՝օգտագործելով ամենաերկար ճանապարհի ալգորիթմը, մենք օգտագործում ենք այդ ալգորիթմը միևնույն մուտքագրված գրաֆի համար և տեղադրում ենք k=|V|, որը գրաֆում եղած գագաթների թիվն է։

Եթե գրաֆում կա համիլթոնյան ճանապարհ, ապա ալգորիթմը կվերադարձնիայո, քանի որ համիլթոնյան ճանապարհի երկարությունը հավասար է |V|։ Հակառակ դեպքում, երբ ալգորիթմը դուրս բերիայո, դա նշանակում է, որ գրաֆում կա |V| երկարությամբպարզ ճանապարհ։ Քանի որ դա|V| երկարությամբ պարզ ճանապարհն է, հետևաբար դա այն ճանապարհն է, որն անցնում է գրաֆի բոլոր գագաթներով առանց կրկնության, և դա ճշգրտության համիլթոնյան ճանապարհն է։

Քանի որ համիլթոնյան ճանապարհի խնդիրը NP-ամբողջությունն է, սա ցույց է տալիս, որ այս խնդիրը NP-բարդ է։ Ցույց տալու համար, որ դա NP-ամբողջություն է, պետք է նաև ցույց տանք, որ այս խնդիրը NP-ում է։ Դա հեշտ է տեսնել, սակայն, քանի որ վկայականը այո-տարածության համար k երկարությամբ ճանապարհի նկարագրություննէ։

Ամենակարճ ճանապարհի խնդրի հետ կապը[խմբագրել | խմբագրել կոդը]

Ամենաերկար ճանապարհի խնդիրը կարող է վերածվել ամենակարճ ճանապարհի խնդրի (չնայած, որ գրաֆը կարող է ունենալ բացասական զանգվածով ցիկլեր), կիրառելով օպտիմալացման երկակիությունը (դրական մեծության մաքսիմալացումը նույննէ, ինչ որ բացասական մեծության մինիմալացումը)։ Եթե ամենաերկար ճանապարհի խնդրի մուտքագրված գրաֆըG է, իսկ ամենակարճ պարզ ճանապարհինը՝ H, որը լրիվ նույնն է, ինչ որ G-ն, բայց բացասական եզրային զանգվածներով, դա ամենաերկար պարզ ճանապարհն էG-ում։ Սակայն, օրիգինալG գրաֆի որոշ դրական զանգված ունեցող ցիկլեր տանում են դեպի H-ի բացասական զանգված ունեցող ցիկլեր։ Բացասական զանգված ունեցող ցիկլերով գտնելով ամենակարճ պարզ ճանապարհը գրաֆում՝ կարող ենք ասել, որ NP-ամբողջություն ունենք։ Եթե G-ն ցիկլեր չի պարունակում, ապա H-ը չի ունենա բացասական զանգվածով ցիկլեր և ամենակարճ ճանապարհը գտնելու ալգորիթմը չի կարող օգտագործվել H-ում պոլինոմիալ ժամանակում օրիգինալ խնդրի լուծման համար։ Այսպիսով, ամենաերկար ճանապարհի խնդիրը հեշտ է լուծել ացիկլիկ գրաֆերում։

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

Ինչպես նշվեց վերևում, ամենաերկար ճանապարհի խնդիրը ացիկլիկ գրաֆերում կարող է լուծվել պոլինոմիալ ժամանակում՝ բացասականացնելով եզրային զանգվածները և կիրառելով ամենակարճ ճանապարհը գտնելու ալգորիթմը։ Վերոնշյալ ալգորիթմը չի օգտագործում այս կրճատումը և հասնում է կոմպլեքսության ավելի լավ ժամանակում։

Կշռված ուղղված ացիկլիկ գրաֆեր[խմբագրել | խմբագրել կոդը]

։

Եթե G-ն ուղղված ացիկլիկ գրաֆն է, ամենաերկար ճանապարհի խնդիրը G-ում կարող է լուծվել գծային ժամանակում՝օգտագործելով դինամիկ ծրագրավորումը։ Ենթադրում ենք, որ topOrder(G)-ի ելքերը գագաթների հերթականությունն է տոպոլոգիական կարգով (Սա կարող է հաշվվել տոպոլոգիական տեսակավորման միջոցով, և այս քայլը պահանջում է, որ մուտքագրված գրաֆը լինի ուղղված ացիկլիկ գրաֆ)։ Բացի այդ, թույլ տանք, որV(G)-ն դրված լինի G-ի գագաթներում ևE(G)-ն տեղադրված լինի G-ի եզրերում և, երբ զանգվածները սահմանված են, թույլ տանք, որ (G, e) զանգվածը լինի e-ի եզրային զանգվածը Gգրաֆում(եթե գրաֆը կշռված չէ, մտցնել 0-ից տարբեր ցանկացած հաստատուն (G,e)) զանգվածի մի քանի դեպքերի համար։ Հետո հետևյալ ալգորիթմը հաշվում է ամենաերկար ճանապարհի երկարությունը։

algorithm dag-longest-path is
input։ 
Directed acyclic graph G
output։ 
Length of the longest path

length_to = array with |V(G)| elements of type int with default value 0

for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G, (v, w)) then
length_to[w] = length_to[v] + weight(G, (v, w))

return max(length_to[v] for v in V(G))

Ճշտությունը կարող է ստուգվել հետևյալ կերպ՝ նախ բոլոր գագաթները պետք է ունենան 0 հեռավորություն գլխավոր գագաթից, իսկ հետո բոլոր գագաթները պետք է ունենան 1 հեռավորությունը գլխավոր գագաթից...։ Յուրաքանչյուր գագաթի համար այն իրոք ունի մաքսիմալ երկարությամբ ճանապարհ, որը բաղկացած է գլխավոր գագաթին ավելի մոտ գտնվող շերտերի միջև ամենամեծ երկարությունն ունեցող ճանապարհներից։ Այս ձևով, ամենաերկար ճանապարհով մի հանգույցը կապվում է մյուսին։ length_to(w) = max(weight(G, (v, w)) + length_to(v)) for all edges (v, w) in G,

Այս ալգորիթմի գործարկման ամենավատ ժամանակը սա է. O(T + |V| + |E| + |V|), եթե T-ն տոպոլոգիական կանոնի կողմից պահանջված ժամանակն է։ Տոպոլոգիական կանոնի հաշվարկման համար ընտրում ենք ստանդարտ ալգորիթմ, որի պարզեցված տեսքն այսպիսինն է O(|V| + |E| + |V| + |E| + |V|), որը պարզեցնում է հերթականները O(|V| + |E|).

Բացի այդ, երկարացնելով այս ալգորիթմը՝ կարող ենք հաշվել նաև իրական ճանապարհը։ Սա անելու համար անհրաժեշտ է ներկայացնել նախորդ(կամ փոխարինող)-դասավորությունը, որը թարմացվում է ամնե անգամ, երբ length_to-ն փոփոխվում է։ Սա անելով, ինչ-որ մեկը կարող է վերակառուցել ուղղված ացիկլիկ գրաֆի գլխավոր գագաթից դուրս եկող ճանապարհը և հենց մաքսիմալ երկարության ճանապարհը վերակառուցվի, դա կդառնա մեկը ամենաերկար ճանապարհներից։

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

Հոդվածի սկզբնական տարբերակը թարգմանվել է անգլերեն վիքիպեդիայի համանուն հոդվածից։

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