Difference between revisions 749081 and 762565 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տարածությւն= «անվերջություն», ինչը նույնպես ճիշտ է, քանզի «հիմք»-ից դեպի «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» տանող ճանապրհին: «ի»-երրորդ ցիկլում 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.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ:⏎
⏎
{{Uncategorized|date=Հունիս 2012}}