Ալիքային ալգորիթմ
| Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
Ալիքային ալգորիթմը — ալգորիթմ է, որը թույլ է տալիս գրաֆում գտնել ամենակարճ ճանապարհը։ Հիմնված է լայնությամբ փնտրման ալգորիթմի վրա։ Կիրառվում է գրաֆում ամենակարճ ճանապարհը գտնելու համար։
| Ալիքային ալգորիթմ | |
|---|---|
| Տեսակ | գրաֆների ալգորիթմ |
Ալգորիթմի իմաստը խմբագրել
Երկչափանի վանդակավոր քարտեզի վրա (մատրից), որը բաղկացած է անցանելի և անանցանելի վանդակներից, նշված են սկզբնակետի և վերջնակետի կոորդինատները։ Ալգորիթմի նպատակն է ցույց տալ ամենակարճ ճանապարհը սկզբնակետի վանդակից դեպի վերջնակետի վանդակը, իհարկե, եթե դա հնարավոր է։ Սկզբնակետից բոլոր ուղղություններով տարածվում է ալիքը, ընդ որում ալիքի յուրաքանչյուր անցած վանդակը նշվում է որպես «անցած»։ Ալիքը, իր հերթին, չի կարող անցնել այն վանդակների միջով, որոնք նշված են «անցած» կամ «անանցանելի»։ Ալիքը շարժվում է, մինչև որ չի հասնում վերջնակետի կետին կամ մինչև որ չմնա չանցած վանդակ։ Եթե ալիքը անցել է բոլոր հասանելի վանդակները, բայց այդպես էլ չի հասել վերջնակետի վանդակին, նշանակում է ճանապարհը սկզբնակետից դեպի վերջնակետը անցնել հնարավոր չէ։ Ալիքի միջոցով վերջնակետին հասնելուց հետո վերջնակետից տեղադրվում է ճանապարհ մինչև սկզբնակետը և պահպանվում է զանգվածում։
Տարատեսակները խմբագրել
Մատրիցայում անցումը չորս ուղղություններով Լիի ալգորիթմն է։ Ավելի ճշգրիտ, բայց դանդաղ մեթոդ։
i+1
i+1 i i+1
i+1
Անցումը մատրիցայում ութ ուղղություններով ավելի արագ, բայց ոչ այնքան ճշգրիտ մեթոդ է։ Ճանապարհը անկյունագծով մոտավորպես 1.4 անգամ ավելի մեծ է, քան ուղղահայաց և հորիզոնական ուղղություններով։ Հենց այդ պատճառով էլ վանդակները, որոնք դասավորված են անկյունագծով, ունեն +3 գործակից, իսկ հորիզոնական և ուղղահայացը՝ +2 գործակից։
i+3 i+2 i+3 i+2 i i+2 i+3 i+2 i+3
Գոյություն ունի նաև ալգորիթմ A* (A-աստղ) — ուղղված ալիքային ալգորիթմ։
Գործնական կիրառությունը խմբագրել
Ալիքային ալգորիթմի ամենաբնութագրիչ հատկությունը նրա կիրառությունն է ստրատեգիական խաղերի մեջ՝ ամենակարճ ճանապարհը գտնելու համար։