Ալիքային ալգորիթմ
 |
Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
| Ալիքային ալգորիթմ | |
|---|---|
| Տեսակ | գրաֆների ալգորիթմ |
Ալիքային ալգորիթմը — ալգորիթմ է, որը թույլ է տալիս գրաֆում գտնել ամենակարճ ճանապարհը։ Հիմնված է լայնությամբ փնտրման ալգորիթմի վրա։ Կիրառվում է գրաֆում ամենակարճ ճանապարհը գտնելու համար։
Ալգորիթմի իմաստը[խմբագրել | խմբագրել կոդը]
Երկչափանի վանդակավոր քարտեզի վրա (մատրից), որը բաղկացած է անցանելի և անանցանելի վանդակներից, նշված են սկզբնակետի և վերջնակետի կոորդինատները։ Ալգորիթմի նպատակն է ցույց տալ ամենակարճ ճանապարհը սկզբնակետի վանդակից դեպի վերջնակետի վանդակը, իհարկե, եթե դա հնարավոր է։ Սկզբնակետից բոլոր ուղղություններով տարածվում է ալիքը, ընդ որում ալիքի յուրաքանչյուր անցած վանդակը նշվում է որպես «անցած»։ Ալիքը, իր հերթին, չի կարող անցնել այն վանդակների միջով, որոնք նշված են «անցած» կամ «անանցանելի»։ Ալիքը շարժվում է, մինչև որ չի հասնում վերջնակետի կետին կամ մինչև որ չմնա չանցած վանդակ։ Եթե ալիքը անցել է բոլոր հասանելի վանդակները, բայց այդպես էլ չի հասել վերջնակետի վանդակին, նշանակում է ճանապարհը սկզբնակետից դեպի վերջնակետը անցնել հնարավոր չէ։ Ալիքի միջոցով վերջնակետին հասնելուց հետո վերջնակետից տեղադրվում է ճանապարհ մինչև սկզբնակետը և պահպանվում է զանգվածում։
Տարատեսակները[խմբագրել | խմբագրել կոդը]
Մատրիցայում անցումը չորս ուղղություններով Լիի ալգորիթմն է։ Ավելի ճշգրիտ, բայց դանդաղ մեթոդ։
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-աստղ) — ուղղված ալիքային ալգորիթմ։
Գործնական կիրառությունը[խմբագրել | խմբագրել կոդը]
Ալիքային ալգորիթմի ամենաբնութագրիչ հատկությունը նրա կիրառությունն է ստրատեգիական խաղերի մեջ՝ ամենակարճ ճանապարհը գտնելու համար։