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

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

Գրաֆերի տեսության մաթեմատիկական կարգապահությունում , ամենաերկար ճանապարհի խնդիրը տրված գրաֆում մաքսիմալ երկարությամբ պարզ ճանապարհը գտնելու խնդիրն է։ Այդ ճանապարհը կոչվում է պարզ, եթե այն չունի մի քանի կրկնվող գագաթներ։ Ի տարբերություն ամենակարճ ճանապարհի խնդրի, որն օգտագործվում է գտնելու 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-ում պոլինոմիալ ժամանակում օրիգինալ խնդրի լուծման համար։ Այսպիսով, ամենաերկար ճանապարհի խնդիրը հեշտ է լուծել ացիկլիկ գրաֆերում։

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

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

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

Պարզ DAG-ը շերտերի հեռավորության հետ, կարմիրը ամենաերկար ճանապարհն է նախորդ շետերի և ամենաերկար եզրի միջև դեպի ընթացիկ գագաթը, որը նշված է (6)-ով

։

Եթե G-ն ուղղված ացիկլիկ գրաֆն է, ամենաերկար ճանապարհի խնդիրը G-ում կարող է լուծվել գծային ժամանակում`օգտագործելով դինամիկ ծրագրավորումը։ Ենթադրում ենք, որ topOrder(G)-ի ելքերը գագաթների հերթականությունն է տոպոլոգիական կարգով (Սա կարող է հաշվվել տոպոլոգիական տեսակավորման միջոցով, և այս քայլը պահանջում է, որ մուտքագրված գրաֆը լինի ուղղված ացիկլիկ գրաֆ)։ Բացի այդ, թույլ տանք, որV(G)-ն դրված լինի G-ի գագաթներում ևE(G)-ն տեղադրված լինի G-ի եզրերում և, երբ զանգվածները սահմանված են, թույլ տանք, որ (Ge) զանգվածը լինի 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, (vw)) + 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-ն փոփոխվում է։ Սա անելով, ինչ-որ մեկը կարող է վերակառուցել ուղղված ացիկլիկ գրաֆի գլխավոր գագաթից դուրս եկող ճանապարհը և հենց մաքսիմալ երկարության ճանապարհը վերակառուցվի, դա կդառնա մեկը ամենաերկար ճանապարհներից։

Աղբյուր[խմբագրել]

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