Difference between revisions 1395182 and 1431643 on hywiki

''Bellman – Ford ալգորիթմ''-ը հաշվարկում է միաղբյուր [[ամենակարճ ճանապարհ]]ները [[կշռավոր արտահայտություն]]ներում: Միայն ոչ բացասական եզրին կշիռներով ալգորիթմերի համար, ավելի արագ [[Dijkstra ալգորիթմ]]ը նույնպես լուծում է խնդիրը։
Այսպիսով, Bellman – Ford-ը օգտագործվում է հիմնականում բացասական եզրային կշիռներով գրաֆիկների համր։ Ալգորիթմն իր անունը ստացել է իր մշակողների, [[Ռիչարդ Բելլման]]ի և [[Լեստեր Ֆորդ կրտ.]]ի անուններից։

Եթե գրաֆիկի պարունակում է “բացասական ցիկլ”, այսինքն, [[ցիկլ]], որի եզրերի գումարը բացասական արժեք է, ապա, կամայականորեն ցածր կշռի [[անցում]]ները կարող են կառուցվել, այսինքն, չի կարող լինել ինչ-որ “ամենակարճ” ճանապարհ։ Bellman – Ford-ը կարող է հայտնաբերել բացասական ցիկլերը և հաղորդել դրանց գոյությունը, բայց այն չի կարող արտադրել ճիշտ պատասխան, եթե բացասական ցիկլը հասանելի չէ աղբյուրից։

Ըստ [[Ռոբերտ Սեդջուիք]]ի, «Բացասական կշիռները պարզապես մաթեմատիկական հետաքրքրություն չեն,  դրանք առաջանում են բնական ձևով, երբ մենք կրճատում ենք այլ խնդիրները ամենակարճ ճանապարհներով խնդիրների»: Ենթադրենք “G” գրաֆիկ է, որը պարունակում է բացասական ցիկլ։ Ամենակարճ ճանապարհով խնդրի մեկ [[NP-ամբողջական]] տարբերակը, պահանջում է ամենակարճ ամենակարճ ճանապարհ “G”-ում (պարունակում է բացասական ցիկլը), այնպես որ ոչ մի եզր չկրկնվի։ Սեդջուիքը տալիս է [[Համիլտոնյան ճանապարհի խնդրի]] [[կրճատում]] մինչև խնդրի այս տարբերակը։

=Ալգորիթմ=
Bellman - Ford-ը իր հիմնական կառուցվածքով շատ նման է [[Dijkstra-ի ալգորիթմ]]ին, սակայն [[«ագահ» ալգորիթմ]]ի փոխարեն ընտրում է նվազագույն կշռով հանգույց, որը դեռ մշակված չէ թուլանալու, այն պարզապես թուլացնում է «բոլոր» եզրերը | V|- 1 անգամ, որտեղ |V|-ն գրաֆիկում անկյունների քանակն է։ Կրկնությունները հանարավոր են դարձնում նվազագույն հեռավորությունների ճշգրիտ տարածում ամբողջ գրաֆիկով, քանզի, բացակայության ցիկլերի բացակայության դեպքում, ամենակարճ ճանապարհը կարող է այցելել ամեն հանգույցը առավելագույնը մեկ անգամ։ Ի տարբերություն “ագահ” մոտեցման, որը կախված է դրական կշիռներից ստացված կոնկրետ կառուցվածքային ենթադրություններից, այս պարզ մոտեցումը վերաբերում է ընդհանուր դեպքին։

Bellman - Ford ներմուծում է “[[Մեծ O նշում]]” (|“V”| • |“E”|) ժամանակահատված, որտեղ |“V”|-ն ու |“E”|-ն համապատասխանաբար անկյունների և եզրերի քանակներն են։

 '''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)
 ''// This implementation takes in a graph, represented as lists of vertices''
 ''// and edges, and modifies the vertices so that their ''distance'' and''
 ''//'' predecessor ''attributes store the shortest paths.''

 ''// Step 1: initialize graph''
 '''for each''' vertex v '''in''' vertices:
   '''if''' v '''is''' source '''then''' v.distance := 0
   '''else''' v.distance := '''infinity'''
v.predecessor := '''null'''

 ''// Step 2: relax edges repeatedly''
 '''for''' i '''from''' 1 '''to''' size(vertices), 1:
   '''for each''' edge uv '''in''' edges: ''// uv is the edge from u to v''
u := uv.source
v := uv.destination
    '''if''' u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u

 ''// Step 3: check for negative-weight cycles''
 '''for each''' edge uv '''in''' edges:
u := uv.source
v := uv.destination
   '''if''' u.distance + uv.weight < v.distance:
    '''error''' "Graph contains a negative-weight cycle"

=Ճշտության ապացույց=
Ալգրիթմի ճշությունը կարելի ե ցույց տալ [[մաթեմատիկական ինդուկցիա]]յի միիջոցով։ Ահա ինդուկցիայով ցուցադրված կոկնկրետ արտահայություն,

«Լեմ»: «for» ցիկլի «i» կրկնություններ.
*Եթե տարածություն(«u») անվերջություն չէ, այն հավասար է «s»ից դեպի «u» որոշ ճանապարհների երկարությունը։
*Եթե կա ճանապարհ «s»ից դեպի «u», առավելագույնը «i» եզրերով ապա տարածություն(«u») հավասար է առավելագույնը «s»ից դեպի «u» ամեակարճ ճանապարհին`առավելագույնը «i» եզրերով։

«Ապացույց»: Որպես ինդուկցիայի հիմնական դեպք ընդունենք i=0 այն պահին, երբ «for» ցիկլը կատարվում է առաջին անգամ։ Ապա հիմնական գագաթի համար, հիմք տարածություն=0, ինչը ճիշտ է։ Մյուս գագաթների համար «u», տարածություն= «անվերջություն», ինչը նույնպես ճիշտ է, քանզի «հիմք»-ից դեպի «u» տանող 0 եզրերով ճանապարհ չկա։

Ինդուկտիվ մասի համար, սկզբից ապացուցենք առաջին մասը։ Քննարկենք մի դեպք, երբ գագաթների տարածությունները փոխվում են.
v տարածություն։= u տարածություն + uv կշիռ։ Ինդոկտիվ ենթադրությամբ, u տարածություն-ը «հիմք»-ից դեպի «u» տանող ճանապարհի երկարությունն է։ Ապա, u տարածություն + uv կշիռ` «հիմք»-ից դեպի «v» տանող ճանապարհի երկարությունն է, որը շարունակում է «հիմք»-ից դեպի «u» տանող ճանապարհը և գնում դեպի «v»:

Երկրորդ մասի համար, քննարկենք «հիմք»-ից դեպի «u» տանող ամենակարճ ճանապարհը, առավելագույնը «i» եզրերով։ Ընդունենք, որ «v»-ն վերջին գագաթն է, մինչև «u» այս ճանապարհի վրա։ Ապա ճանապարհի` «հիմքից» դեպի «v» տանող մասը ամենակարճ ճանապարհն է «հիմք»-ից դեպի «v», առավելագույնը «i-1» եզրերով։ Ինդուկտիվ ենթադրությամբ, v տարածություն-ը «i-1» ցիկլից հետո առավելագույն այս ճանապարհի երկարության է։ Որից հետևում է, որ uv կշիռ + v տարածություն առավելագույնը հավասար է «s»-ց դեպի «u» տանող ճանապրհին։ «i»-երրորդ ցիկլում uտարածությունը համեմատվում է uv կշիռ+ v տարածության հետ, և հավասարվում է դրան, եթե uv կշիռ + v տարածություն ավելի փոքր էր։
Այդ պատճառով, «i» քանակով ցիկլերից հետո, u տարածությունը առավելագույնը հավասար է «հիմք»-ից դեպի «u» տանող ամենակարճ ճանապարհին, որն օգտագործում է առավելագույնը «i» քանակով եզրեր։

Եթե բացասական կշիռ ունեցող ցիկլեր չկան, ապա ամեն ամենակարճ ճանապարհ այցելում է յուրաքանչյուր գագաթը առավելագույնը մեկ անգամ, այնպես որ 3-րդ քայլից ոչ մի փոփոխություն հնարավոր չէ անել։ Մյուս կողմից, ընդունենք, որ ընդհանրապես ոչ մի փոփոխություն հնարավոր չէ անել։ Այս դեպքում «v»[0],…, «v»[«k»-1] գագաթներով ցանկացած ցիկլի համար.
v[i]տարածություն<= v[(i-1) mod k]տարածություն+ v[(i-1) mod k]v[i]կշիռ
v[i]տարածություն և v[(i-1) mod k]տարածություն արտահայտությունները կրճատվում են` թողնելով.
0<<= sum from 1 to k of v[i-1 (mod k)]v[i]կշիռ
Այսինքն, ամեն ցիկլ ունի ոչ բացասական կշիռ։

=Կիրառումը ռաութինգում=
Bellman–Ford ալգորիթմի կրճատված տարբերակը օգտագործվում է [[տարածական վեկտորային ռաութինգ]]ում, օրինակ [[ռաութինգի ինֆորմացիոն կանխագրեր]]ում: Ալգորիթմը կրճատված է, քանզի այն պարունակում է որոշ հանգույցներ (ռաութերներ) [[ավտոնոմ ցանաց (ինտերնետ)]]ում IP ցանցերի հավաքածու, որոնք հիմնականում լինում Ինտերնետ ծառայության մատակարարների մոտ։
1.	Ամեն հանգույց հաշվում է տարածությունը իր և մնացած բոլոր հանգույցների միջև և պահում է ինֆորմացիան գրաֆիկի տեսքով։
2.	Ամեն հանգույց ուղարկում է իր գրաֆիկը բոլոր հարևան հանգույցներին։
3.	Երբ հանգույցը ստանում է իր հարևանի գրաֆիկը, այն հաշվում էամենակարճ ճանապարհները մյուս հանգույցների համեմատ և համապատասխանաբար թարմացնում իր սեփական գրաֆիկը։

Bellman–Ford ալգորիթմի հիմնական թերություններն են`
1.	Այն լավ չի հաշվարկում կշիռը։
2.	Փոփոխությունները [[ցանցային տոպոլոգիա]]ում արագ չեն երևում, քանզի թարմացումները փոխանցվում են հանգույցից հանգույց։
3.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ։

[[Կատեգորիա:Ալգորիթմներ]]