Ա*

Ա*
Տեսակ	փնտրման ալգորիթմ, ուղի որոնման ալգորիթմ և գրաֆների ալգորիթմ
Դաս	լավագույն առաջին որոնում
Տվյալների կառուցվածք	$O(|V|)=O(b^{d})$
Վատագույն դեպքում կատարումը	$O(|E|)=O(b^{d})$
Օգտագործում է	գրաֆ
Հայտնաբերող	Փիթեր Էլլիոտ Հարթ, Նիլս Ջոն Նիլսոն և Բերտրամ Ռաֆայել

A* (կարդացվում է «Ա աստղ» կամ «Ա սթար», անգլ.՝ A star), ինֆորմատիկայում և մաթեմատիկայում, առաջին լավագույն համընկմամբ որոնման ալգորիթմ գրաֆների վրա, որը գտնում է քիչ ծախսատար ճանապարհը մի կետից (սկզբնական) մյուսին (նպատակային, վերջնական)։

Մի կետից մյուսի անցման հերթականությունը որոշվում է էվարիստիկ ֆունկցիայով «ճանապարհ + արժեք» (հաճախ նշանակվում է՝ f(x))։ Այս ֆունքցիան երկու այլ ֆունկցիաների գումարն է. դիտարկվող բարձրության հասանելիության արժեքի ֆունկցիա (x) սկզբնական (հաճախ նշանակվում է՝ g(x) ) և սկզբնական բարձրությունից դեպի վերջնական հեռավորության էվարիստիկ գնահատումով (նշանակվում է՝ h(x))։

Ֆունկցիա h(x)-ը պետք է լինի թույլատրելի էվարիստիկ գնահատական, այսինքն չպետք է գերագնահատի հեռավորությունը դեպի նպատակային բարձրությունը։ Օրինակ, երթուղավորման տրման համար h(x)–ը կարող է իրենից ներկայացնել մինչև նպատակակետը գտնվող հեռավորություն ուղիղ գծի տեսքով, այնպես որ դա լինի ֆիզիկապես հնարավոր ամենափոքր հեռավորությունը 2 կետերի միջև։

Այս ալգորիթմը առաջին անգամ նկարագրվել է 1968 թին Պիտեր Խարտի, Նիլսոն Նիլսի և Ռաֆաել Բերտրամի կողմից։ Այն իրականում Էդսգեր Դեյկստռի ալգորիթմի ընդարձակումը, որը ստեղծվել է 1959 թ.-ին։ Այն ավելի էր մեծացնում իր արտադրողականությունը(ժամանակի ընթացքում) էվրիստիկայի օգնությամբ։ Իրենց աշխատանքում այն անվանվում է «ալգորիթմ A»։ Բայց քանի որ այն որոշում է տրված էվարիստիկայի լավագույն ճանապարհը այն անվանեցին A*։

Նրա ընդհանրացում հանդիսանում է երկակի ուղղությամբ փնտրման էվարիստիկ ալգորիթմը։

Պատմություն

1964 թ.-ին Նիլսոն Նիլսը հայտնագործեց Դեյկստռի ալգորիթմի արագության ավելացման էվարիստիկ մոտեցումը։ Այդ ալգորիթմը անվանվեց А1. 1967 թ.-ին Ռաֆաել Բերտրամը այդ ալգորիթմում կատարեց զգալի բարեփոխումներ, բայց նրան չհաջողվեց հասնել օպտիմալության։ Նա անվանեց այդ ալգորիթմը A2. Այնուհետև 1968 թ.-ին Պիտեր Խարտը բերեց փաստարկներ, որոնք ապացուցում էին, որ A2 –ը օպտիմալ կլիներ հաջորդական էվրիստիկայի օգտագործման դեպքում, չնչին փոփոխություններով։ Այսպիսով նա նոր ալգորիթմը շարահյուսությունում նշանակեց աստղով, այն սկսվում էր А-ով և ներառում էր վերսիայի բոլոր համարները։

Ալգորիթմի նկարագրությունը

Հանգույցներում գտնվող դատարկ օղակները պատկանում են բաց ցուցակին, կարմիրները/կապույտները պատկանում են փակ ցուցակին.

A*-ը հերթականությամբ դիտարկում է բոլոր ուղղությունները, որոնք սկզբնական կետից տանում են դեպի վերջնականը, մինչև չի գտնում մինիմալը։ Ինչպես և բոլոր ինֆորմացված փնտրման ալգորիթմները, այն սկզբում դիտարկում է այն ճանապարհները, որոնք դեպի նշանակակետ տանող են թվում։ Ժլատ ալգորիթմից (որը նույնպես հանդիսանում է առաջին լավագույն համընկմամբ փնտրման ալգորիթմ) տարբերվում է նրանով, որ բարձրության ընտրման ժամանակ, նա հաշվի է առնում նրա ամբողջ անցած ճանապարհը (որը կազմում է g(x) - դա սկզբնական կետից մինչև վերջնականը անցած ճանապարհի գինն է, ինչպես ժլատ ալգորիթմում)։ Աշխատանքի սկզբում դիտարկվում են հանգույցները, որոնք կցված են սկզբնականին, դրանցից ընտրվում է այն, որը ունի մինիմալ f(x) բովանդակություն, որից հետո այդ հանգույցը բացվում է։ Ամեն փուլում ալգորիթմը գործողություններ է կատարում սկզբնականան կետից մինչև գրաֆի դեռ չբացված(էջային) կետը («անձնական որոշումների բազմություն»), որը գտնվում է առաջնայնությամբ հերթականությունում։ Ճանապարհի առաջնայնությունը որոշվում է f(x) = g(x) + h(x) արժեքով։ Ալգորիթմը շարունակում է աշխատել այնքան ժամանակ, մինչև f(x) –ի արժեքը չի լինում ավելի փոքր, քան հերթականության մնացած արժեքները։ Բոլոր լուծումներից ընտրվում է փոքրագույն արժողությամբ լուծումը։

Ինչքան փոքր է h(x) էվրիստիկան, այնքան մեծ է առաջնայնությունը։

 function A*(start, goal)
   % արդեն անցած գագաթների բազմություն
   var closed := the empty set
   % անձնական որոշումների բազմություն
   var q := make_queue(path(start))
   while q is not empty
     var p := remove_first(q)
     var x := the last node of p
     if x in closed
       continue
     if x = goal
       return p
     add x to closed
     % ավելացնենք կից գագաթները
     foreach y in successors(x)
       enqueue(q, p, y)
   return failure

Արդեն անցած բարձրությունների բազմությունը կարելի է իջեցնել, եթե հայտնի է, որ լուծումը գոյություն ունի կամ եթե կատուցվածքը successors կարող է առանձնացնել ցիկլերը։

Օրինակ

A* ալգորիթմի օրինակ է շարժման մեջ, որտեղ հանգույցները դա քաղաքներն են, որոնք կապված են փողոցներով և Н (х)-ը հանդիսանում է ամենակարճ ճանապարհը մինչև նպատակային կետը։

Բանալի։ կանաչ - սկիզբ, կապույտ - նպատակ, գազարագույն – հաճախական հանգույց։

Ծանոթություն։ Այս օրինակում ստորակետն օգտագործվում է ինչպես տասնորդական բաժանորդ։

Հատկություններ

Ինչպես և փնտրում լայնությամբ ալգորիթմը, այննպես էլ A*-ը հանդիսանում է ընդհանուր այն իմաստով, որ այն միշտ գտնում է լուծում, եթե այդպիսին գոյություն ունի։ Եթե h էվարիստիկ ֆունկցիան թույլատրելի է, այսինքն երբեք չի գերագնահատում նպատակին հասնելու համար անհրաժեշտ մինիմալ արժեքը, ապա A*-ը ինքն է հանդիսանում թույլատրելի (կամ օպտիմալ), և այն պայմանուվ, որ մենք չենք զատի անցած բարձրությունները։ Եթե մենք դա անում ենք, ապա ալգորիթմի օպտիմալության համար հարկավոր է, h(x)-ը լինի նաև մոնոտոն, կամ հաջորդաբար էվրիստիկա։ Մոնոտոնության հատկությունը նշանակում է, որ եթե գոյություն ունեն A - B - C և A - C (անպայման չէ B-ով) կապեր, ապա A-ից C ճանապարհի արժեքի գնահատումը պետք է լինի կամ փոքր կամ հավասար A - B և B - C ճանապարհների գումարին։ (Մոնոպոլությունը նաև հայտնի է որպես եռանկյան անհավասարություն. եռանկյան մի կողմը չի կարող ավելի երկար լինել, քան մյուս երկու կողմերի գումարը։) Մաթեմատիկորեն x, y (որտեղ y-ը x-ի հետևորդ) ուղիների համար կատարում ենք։

$g(x)+h(x)\leq g(y)+h(y).$

A*-ը նաև օպտիմալորեն էֆեկտիվ է h տրված էվրիստիկայի համար։ Դա նշանակում է, որ ցանկացած այլ ալգորիթմը հետազոտում է A*-ից ոչ քիչ հանգույցներ (բացառությամբ այն դեպքերի, երբ գոյություն ունեն մի քանի անձնական որոշումներ միևնույն էվրիստիկայով, որը ճշտորեն համապատասխանում է օպտիմալ ուղղության արժեքով։ Այն ժամանակ, երբ A*-ն օպտիմալ է «հանկարծակի » տրված գրֆների համար, չկա ապահովություն, որ նա կանի իր աշխատանքը ավելի լավ, քան ավելի պարզ, բայց ավելի ինֆորմացիոն կախված խնդրային շրջանի ալգորիթմներից։ Օրինակ, ինչ որ լաբիրինթում կարող է պետք գալ սկզբում գնալ մուտքից ներս ուղղությամբ, իսկ այնուհետև թեքվել հետ։ Այդ դեպքում սկզբում դիտարկելը այն բարձրությունները, որոնք տեղակայված են ելքին մոտ, կլինի ժամանակի կորուստ։

Մասնավոր դեպքեր

Ընդհանուր առմամբ, փնտրում խորությամբ և փնտրումը լայնությամբ հանդիսանում են ալգորիթմ A*-ի երկու մասնավոր դեպքեր։ Խորությամբ փնտրման համար կվերցնենք գլոբալ փոփոխական` հաշվիչ С, նշանակելով այն ինչ-որ մեծությամբ։ Ամեն անգամ գագաթների բացման դեպքում հաշվիչի բովանդուկությունը կվերագրենք կից գագաթներին, այն փոքրացնելով մեկով ամեն վերագրումից հետո։ Այսպիսով, ինչքան շուտ բացվի գագաթը, այնքան մեծ h(x) մեծություն այն կստանա, դա նշանակում է, կդիտարկվի վերջում։ Եթե որոշոնք h(x) = 0, ապա մենք կստանանք մեկ այլ մասնավոր դեպք` Դեյկստռի ալգորիթմ։

Իրականացման նրբություններ

Գոյություն ունեն իրականացման և ընդունման մի շարք յուրահատկություններ և օրինակներ, որոնք կարող են ազդել ալգորիթմի էֆեկտիվության վրա։ Առաջինը, ինչի վրա պետք է ուշադրություն դարձնել դա այն է, թե հերթականությունը առաջնայնությամբ ինչպես է մշակում կապերը գագաթների միջև։ Եթե գագաթները ավելացվում են LIFO մեթոդով, ապա միևնույն գնահատմամբ գագաթների դեպքում A*-ը «կգնա» դեպի խորքը։ Իսկ, եթե գագաթների ավելացման ժամանակ իրագործվի FIFO մեթոդը, ապա միևնույն գնահատմամբ գագաթների ալգորիթմը կստեղծի լայնությամբ փնտրում։ Որոշ դեպքերում այդ իրավիճակը կարող է մեծ ազդեցություն ունենալ արտադրողականության վրա։

Այն դեպքում, եթե ալգորիթմի աշխատանքից հետո անհրաժեշտ է լինում ուղի, ամեն գագաթի հետ պահում են հղում դեպի ծնողական հանգույց։ Այդ հղումները թույլ են տալիս վերակառուցել օպտիմալ հանգույց։ Եթե այդպես է, ապա կարևոր է, որ միևնույն գագաթը հերթում չհանդիպի երկու անգամ (այդ դեպքում նաև ունենալով իր ուղին և իր արժեքի գնահատականը)։ Սովորաբար այդ խնդրի լուծման համար գագաթի ավելացման ժամանակ ստուգում են, թե արդյոք հերթում չկա նրա մասին գրառում։ Եթե այն առկա է, ապա գրառումը թարմացնում են այնպես, որ այն համապատասխանի երկուսից ավելի մինիմալ արժեղություն ունեցողին։ Դիրքային ծառում գագաթի փնտրման համար շատ ստանդարտ ալգորիթմներ պահանջում են O(n) ժամանակ։ Եթե կատարելագործենք ծառը քեշ-աղյուսակի օգնությամբ, ապա կարելի է փոքրացնել այդ ժամանակը։

Ինչու է A* թույլատրելի և օպտիմալ

A* ալգորիթմը և թույլատրելի է և անցնում է մինիմալ քանակությամբ գագաթներ, ի շնորհիվ նրա, որ նա աշխատում է մինիմալ «օպտիմալությամբ» գագաթով անցնող ճանապարհի գնահատման դեպքում։ Օպտիմալ այն իմաստով, որ եթե նա մոտենա այդ գագաթի մոտից ալգորիթմը «կունենա հնարավորություն», որ արդյունքի իրական արժեքը հավասար կլինի այդ գնահատականին, բայց ոչ ավելի փոքր։ Բայց քանի որ A*-ը հանդիսանում է տեղեկացված ալգորիթմ, այդպիսի հավասարությունը կարող է լինել հնարավոր։ Երբ A*-ը վերջացնում է փնտրումը, նա, համաձայն որոշմանը, գտել է ուղին, որի իրականարժեքը ավելի փոքր է, քան ցանկացած բաց հանգույցից ցանկացած ճանապարհ արժեքի գնահատումը։ Բայց քանի որ այդ արժեքները հանդիսանում են օպտիմալ, համապատասխան հանգույցները կարելի է թողնել։ Այլ կերպ ասած A*-ը երբեք բաց չի թողնի հնարավորություն փոքրացնել ճանապարհի երկարությունը, այդ պատճառով էլ հանդիսանում է հասանելի։ Այժմ ենթադրենք, որ ինչ որ B ալգորիթմ արտացոլում է ճանապարհը որպես արդյունք, որի երկարությունը ավելի մեծ է քան ինչ որ գագաթի արժեքի գնահատումը։ Էվրիստիկ ինֆորմացիայի հիման վրա, ալգորիթմ B-ի համար չի կարելի բացառել այն հնարավորությունը, որ այդ ուղին ուներ ավելի փոքր երկարություն քան արդյունքը։ Հետևաբար, մինչև ալգորիթմ B –ն կդիտարկի ավելի քիչ քանակությամբ ալգորիթմ քան A*-ն, նա չի լինի թույլատրելի։ Այսպիսով A*-ը անցնում է մինիմալ քանակությամբ գագաթներ թույլատրելի ալգորիթմներում, որոնք օգտագործում են նույն կերպ հստակ էվրիստիկա։

Բարդության գնահատում

A* ալգորիթմի ժամանակավոր բարդությունը կախված ք էվրիստիկայից։ Վատագույն դեպքում, գագաթների քանակը, որը դիտարկվում է ալգորիթմի կողմից, էքսպոտենցիալ կերպով աճում է օպտիմալ ուղղու երկարության համեմատ, բայց բարդությունը դառնում է պոլինոմինալ, երբ էվրիստիկան բավարարում է հետևյալ պայմանին.

$|h(x)-h^{*}(x)|\leq O(\log h^{*}(x))$;

որտեղ h*-ը օպտիմալ էվրիստիկան է, այսինքն գագաթից մինչև նպատակը ընկած տարածքի հեռավորության ճշգրիտ գնահատումն է։ Այլ կերպ ասած, h(x) սխալը չպետք է աճի ավելի արագ քան օպտիմալ էվրիստիկայի լոգարիթմը։ Բայց ավելի մեծ խնդիր, քան ժամանակավոր բարդությունն է, իրենցից ներկայացնում են ալգորիթմի ռեսուրսներից օգտվողները։ Վատագույն դեպքում նա ստիպված է լինում հիշել էքսպոնենտալ քանակությամբ հանգույցներ։ Դրա դեմ կռվի համար առաջարկվել են մի շարք ալգորիթմներ, օրինակ iterative deeping A*, IDA*, memory-bounded A*, MA*, simplified MA*, SMA*, recursive best-first search, RBFS։

Կիրառության օրինակներ

Կլասիկ օրինակ է հանդիսանում Lines (Color Lines) խաղը, որը հայտնագործել է Օլեգ Դյոմինի, Գենադիյ Դինիսովի և Իգոր Իվկինի կողմից և մշակվել է ռուսական Gamosկազմակերպության կողմից 1992 թ.-ին։ Տվյալ խաղում էկրանին ցույց է տրվում քառակուսիների 9×9 չափսերով դաշտ, որտեղ տարբեր վանդակներում ծրագիրը դուրս է բերում տարբեր գույների երեք գնդիկներ։ Միայն յոթ հնարավոր գույներով։ Մեկ քայլի ընթացքում խաղացողը կարող է կատարել մեկ քայլ, նշելով գնդիկը և տեղափոխելով այն։ Քայլի վերջացման համար անհրաժեշտ է, որ սկզբանական և վերջնական վանդակների միջև գոյություն ունենա ազատ վանդակներից կազմված ուղի։ Խաղի նպատակը նրանում է, որ ինչքան հնարավոր է շատ գնդիկներ ջնջվի, որոնք անհետանում են նույն գույնի գնդիկները մի ուղղի վրա շարելիս(հորիզոնական, ուղղահայաց կամ անկյունագծով)։ Գնդիկների անհետացման դեպքում նոր գնդիկներ չեն ավելանում։ Մնացած դեպքերում ամեն քայլից հետո ավելանում են երեք նոր գնդիկներ։ Խաղացողը նախապես կարող է տեսնել այն երեք գնդիկները, որոնք առաջանալու են հաջորդ քայլում։

Գրականություն

• Лорьер Ж.-Л. Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. - М.։ Мир, 1991. - С. 238 - 244. - 20 000 экз, экз. - ISBN 5-03-001408-X
• Рассел С. Дж., Норвиг, П. Искусственный интеллект։ современный подход = Artificial Intelligence։ A Modern Approach / Пер. с англ. и ред. К. А. Птицына. - 2-е изд.. - М.։ Вильямс, 2006. - С. 157 - 162. - 3 000 экз, экз. - ISBN 5-8459-0887-6
• Нильсон Н. Искусственный интеллект։ методы поиска решений = Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л. Стефанюка; под ред. С. В. Фомина. - М.։ Мир, 1973. - С. 70 - 80.
• Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. - 1985. - Т. 32. - № 3. - С. 505 - 536.
• Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. - 1968. - № 2. - С. 100 - 107.
• Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. - 1972. - Т. 37. - С. 28 - 29.
• Pearl J. Heuristics։ Intelligent Search Strategies for Computer Problem Solving. - Addison-Wesley, 1984. - ISBN 0-201-05594-5

Արտաքին հղումներ

• A* Подробное описание алгоритма А* Արխիվացված 2012-02-04 Wayback Machine
• A* построение пути со сглаживанием и реалистичными поворотами - Автор Marco Pinter
• A* Explorer Արխիվացված 2011-06-25 Wayback Machine - программа для Windows, позволяющая пошагово просматривать работу A* алгоритма.
• Алгоритм A* - реализация на PHP и визуализация используя Google Map API.
• Amit’s Pages - О поиске пути и A*
• Реализация на VB 6.0 в виде DLL, включает графический интерфейс и возможность пошагового просмотра.
• Руководство по A*
• Cupper (17 января 2004 года). «Принцип работы алгоритма поиска пути Астар (A*)». GameDev.ru. Վերցված է 22 июля 2009-ին.