Բելլաման - Ֆորդի ալգորիթմ

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

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. Մինչև անվերջություն հաշվելու խնդիրներ։