Difference between revisions 1235017 and 1389176 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.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ:։

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