Difference between revisions 749081 and 762565 on hywiki

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

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

Ըստ [[Ռոբերտ Սեդջուիք]]ի, «Բացասական կշիռները պարզապես մաթեմատիկական հետաքրքրություն չեն,  դրանք առաջանում են բնական ձևով, երբ մենք կրճատում ենք այլ խնդիրները ամենակարճ ճանապարհներով խնդիրների»: Ենթադրենք “G” գրաֆիկ է, որը պարունակում է բացասական ցիկլ: Ամենակարճ ճանապարհով խնդրի մեկ [[NP-ամբողջական]] տարբերակը, պահանջում է ամենակարճ ամենակարճ ճանապարհ “G”-ում (պարունակում է բացասական ցիկլը), այն(contracted; show full)
        '''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

(contracted; show full)
2.	Ամեն հանգույց ուղարկում է իր գրաֆիկը բոլոր հարևան հանգույցներին:
3.	Երբ հանգույցը ստանում է իր հարևանի գրաֆիկը, այն հաշվում էամենակարճ ճանապարհները մյուս հանգույցների համեմատ և համապատասխանաբար թարմացնում իր սեփական գրաֆիկը:

Bellman–Ford ալգորիթմի հիմնական թերություններն են`
1.	Այն լավ չի հաշվարկում կշիռը:
2.	Փոփոխությունները [[ցանցային տոպոլոգիա]]ում արագ չեն երևում, քանզի թարմացումները փոխանցվում են հանգույցից հանգույց:
3.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ:
⏎
⏎
{{Uncategorized|date=Հունիս 2012}}