Ա*

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) \le 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* Подробное описание алгоритма А*
• A* построение пути со сглаживанием и реалистичными поворотами — Автор Marco Pinter
• A* Explorer — программа для Windows, позволяющая пошагово просматривать работу A* алгоритма.
• Алгоритм A* — реализация на PHP и визуализация используя Google Map API.
• Amit’s Pages — О поиске пути и A*
• Реализация на VB 6.0 в виде DLL, включает графический интерфейс и возможность пошагового просмотра.
• Руководство по A*
• Cupper։ «Принцип работы алгоритма поиска пути Астар (A*)»։ GameDev.ru։ http://www.gamedev.ru/articles/?id=70121։ Վերցված է 22 июля 2009։