Ինֆորմացիոն փնտրում
Ինֆորմացված որոնման ալգորիթմները[1][2] արհեստական բանականության մեջ օգտագործվող որոնման ալգորիթմների ենթատեսակ են։ Ի տարբերություն ոչ ինֆորմացված որոման, ինֆորմացված որոնմանը հասանելի է որոշակի տեղեկություն որոնման տարածության մասին (ինչքան հեռու է նպատակից, ճանապարհի արժքեը, ինչպես հասնել նպատակի հանգույցին)։ Այս տեղեկությունները օգնում են, որպեսզի ավելի քիչ ուսումնասիրվի որոնման տարածությունը, և ավելի արդյունավետ կերպով գտնվի նպատակային հանգույցը։
Ինֆորմացված որոնման ալգորիթմները ավելի նպատակահարմար են մեծ որոնման տարածությունների հետ գործ ունենալիս։ Ինֆորմացված որոնման ալգորիթմները օգտագործում են էվրիստիկայի գաղափարը, և հետևաբար նաև կոչվում են Էվրիստիկ որոնում։
Էվրիստիկ ֆունկցիա[խմբագրել | խմբագրել կոդը]
Էվրիստիկ ֆունկցիան օգտագործվում է ինֆորմացված որոնման ալգորիթմների ժամանակ, այն գտնում է ամենախոստումնալից ճանապարհը։ Որպես մուտքային տվյալ այն վերցնում է որոնող տարրի ներկա վիճակը տարածության մեջ, և արտածում է մոտավոր հեռավորությունը նպատակային հանգույցից։ Էվրիստիկ ֆունկցիան ոչ միշտ է հաշվարկում ամենաարդյունավետ ճանապարհը, սակայն ամեն դեպքում իր առաջարկած ճանապարհը բավականին լավն է,այսինքն՝ ցանկացած դեպքում այդ ճանապարհը ավելի արդյունավետ է քան ոչ ինֆորմացված որոնման ալգորիթմով փնտրումը։
Ինֆորմացված որոնման ալգորիթմների տեսակներ[խմբագրել | խմբագրել կոդը]
Ինֆորմացված որոնման ալգորիթմները լինում են շատ տարբեր տեսակների։ Ընդհանուր դեպքը առաջին լավագույն համընկնմամբ որոնման ալգորիթմն է, և դրանից ելնելով կազմվել են ավելի մասնագիտացված ալգորիթմներ։
Առաջին լավագույն համընկնամբ որոնում[խմբագրել | խմբագրել կոդը]
Այս ալգորիթմը[3] գրաֆը հետազոտում է ընդարձակվելով դեպի ամենախոստումնալից հանգույցները՝ ըստ ինչ-որ օրենքի։ Այն գնահատում է ամենախոստումնալից հանգույցը էվրիստիկ ֆունկցիայի միջոցով, կախված տվյալ հանգույցի նկարագրությունից, նպատակի նկարագրությունից, մինչ այդ պահը որոնման ժամանակ հավաքված ինֆորմացիայից և այլ հավելյալ տեղեկությունից։ Ընդարձակման ենթակա հանգույցները ընտրվում են առաջնահերթության հերթի միջոցով։
Հիմնականում այդ տերմինը օգտագործելիս նկատի ունեն առաջին լավագույն համընկնմաբ ժլատ ալգորիթմը, որը նաև անվանում են մաքուր էվրիստիկ որոնում։
Երկակի ուղղությամբ փնտրման էվրիստիկ ալգորիթմ[խմբագրել | խմբագրել կոդը]
Այս ալգորիթմը օգտագործվում է ուղղորդված գրաֆում որոնում կատարելիս, այն միաժամանակ կատարում է երկու գործողություն՝ փնտրում սկզբնական հանգույցիցմ և հակառակ փնտրում նպատակային հանգույցից, կանգ առնելով երբ այդ երկուսը հանդիպեն։ Էվրիստիկ ֆունկցիան այստեղ հաշվարկում է հեռավորությունը նպատակային հանգույցից, կամ սկզբնականից՝ հակառակ փնտրման դեպքում։
Ա* ալգորիթմ[խմբագրել | խմբագրել կոդը]
Ա* ալգորիթմը[4] հանդիսանում է երկակի ուղղությամբ թնտրման ալգորիթմի մասնավոր դեպք, օգտագործում է ճանապարհի արժեքը, ինչպես նաև էվրիստիկ տեղեկություններ, այսինքն՝ առաջին լավագույն համընկնմամբ ժլատ որոնում։ Այն Դեքստրայի ալգորիթմի ընդլայնում է, որը ինքնին ինֆորմացված ալգորիթմ չէ, Ա*-ը իր արտադրողականությունը ավելացնում է էվրիստիկայի օգնությամբ։ Էվրիստիկ գնահատականը պետք է լինի թույլատրելի, այսինքն՝ երբեք չգերագնահատի տվյալ հանգույցի և նպատակի միջև ճանապարհի արժեքը։ Ամբողջ ճանապարհը հանդիսանում է հայտնի ճանապարհի արժեքի և մինչև նպատակը մնացած ճանապարհի էվրիստիկ մոտավորության գումարը։
Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]
- ↑ «Informed Search Algorithms in AI - Javatpoint». www.javatpoint.com (անգլերեն). Վերցված է 2021 թ․ հոկտեմբերի 25-ին.
- ↑ «Artificial Intelligence: A Modern Approach, 4th US ed». aima.cs.berkeley.edu. Վերցված է 2021 թ․ նոյեմբերի 18-ին.
- ↑ http://web.pdx.edu/~arhodes/ai6.pdf
- ↑ «3.6.1 A^* Search‣ 3.6 Heuristic Search ‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition». artint.info. Վերցված է 2021 թ․ նոյեմբերի 18-ին.