Մասնակից:Ashkhen Khachatryan/Ճառագայթային որոնում
Ինֆորմատիկայում, փնտրման ճառագայթը իրենից ներկայացնում է էվրիստիկական փնտրման ալգորիթմ, որն ուսումնասիրում է սահմանափակ լրակազմից առավել խոստումնալից հանգույցներով գրաֆ: Փնտրման ճառագայթը լավագույն առաջին փնտրման օպտիմիզացումն է, որը նվազեցնում է իր հիշողության պահանջները: Լավագույն առաջի որոնումը գրաֆի որոնման մեջ , որը պատվեր է բոլոր մասնակի լուծումների (դրություն) ,որոշ հերոստիկ (heuristic) ,որը փորձում է գուշակել, թե որն է մոտ մասնակի լուծմանը ամբողջական լուծումում (դրության նպատակը ). Բայց ճառագայթային փնտրման մեջ լավագույն մասնակի լուծումների միայն կանխորոշված շարքերն են պահվում որպես թեկնածուներ:[1]
Որոնման լայնության օգտագործումը լայնությունում որոնման ծառը կառուցելու համար է :Ծառի յուրաքանչյուր մակարդակում գերակշռում է բոլոր հետնորդների վիճակները ներկա մակարդակից, դասավորում դրանք աճման կարգով ,տալիս է հերոստիկ (heuristic) արժեք : .[2] Սակայն այն միայն հիշում է որոշակի թվով դրություններ յուրաքանչյուր մակարդակում (այսպես կոչվածվ վերդիր լայնությունը)):Որքան մեծ է վերդիր լայնությունը ,այնքան քիչ են երկրները հեռանում : Անսահմանափակ լայնությունը ճառագայթը դրություններ են կտրում և փնտրման ճառագայթի նույնական են դեպի որոնման լայնությունը : Վերդիր լայնությունը մեծացնում է հիշողության ծավալը ,որը անհրաժոշտ է փնտրման համար : Դրության նպատակը կարող է կրճատվել ճառագայթային որոնման ամբողջականացման պատճառով (երաշխիքը, որ այդ ալգորիթմը չի դադարեցնի իր լուծումը , եթե այն գոյություն ունի)և օպտիմալության ((երաշխիքը, որ նա կգտնի լավագույն լուծումը):
Ճառագայթի լայնությունը կարող է կամ պետք է լինի հաստատուն կամ փոփոխական: Այն մոտեցումը, որը կիրառում է փոփոխական ճառագայթ, լայնությունը սկսում է նվազագույնից: Եթե որևէ լուծում չի գտնվում, ապա ճառագայթի լայնությունԹ մեծանում է և պրոցեսը նորից է կրկնվում:[3]
Անուն խմբագրել
Փնտրման ճառագայթ տերմինը հնարել է Ռաջ Ռեդդին 1976 թվականին, [[Քարնեջիե Մելլոն համալսարանում (Carnegie Mellon University) ]]:
Օգտագործումը խմբագրել
Վերդիր փնտրումը առավել հաճախ օգտագործվում են ճկունության պահպանման համար մեծ համակարգերում ,որոնք ունեն քիչ հիշողություն որոնման ծառը պահպանելու համար : .[4] Օրինակ, այն օգտագործվում է բազմաթիվ մեքենաների թարգմանչական համակարգերում : .[5]Որպեսզի ընտրվի լավագույն թարգմանությունը, յուրաքանչյուր մաս մշակվում է , եւ տարբեր ձեւեր են հայտնվում բառերը թարգմանելու : Լավագույն թարգմանության համար կախված նրանց նախադասության կառուցվածքից պահպանվում են ,իսկ մնացածը անտեսվում են :Թարգմանիչը հետո գնահատվում է թարգմանություններով ընտրելով ամենալավ թարգմանությունը, որը պահում նպատակներ: Այսպիսի ձևը առաջին անգամ օգտագործվել է Հարփի Սփիչ սիստեմում (Harpy Speech Recognition System) CMU 1976թ. :[6]
Ընդլայնումը խմբագրել
Ճառագայթային փնտրումը կատարվել է լրիվությամբ համատեղելով այն խորության փնտրման հետ ,որի արդյունքում որոնման ճառագայթը պահպանվում է որոնման ճառագայթ պահոցում և առաջին որոնման ճառագայթի խորությունում և սահմանափակ որոնման անհամապատասխանությունում ինչի արդյունքում որոնման ճառագայթը ,որը օգտագործվում է փնտրման սահմանափակման մեջ անհամատեղելի է դառնում (լամպ) : [7] ,[4] [4] .Արդյունքում որոնման ալգորիթմները համարվում են ալգորիթմներ ցանկացած ժամանակի ,որը կարող է գտնել լավ ,բայց ոչ օպտիմալ խնդիրներ արագ , ինչպես փնտրման ճառագայթը ,այնուհետեվ նորից վերադարձնել և շարունակել ,որպեսզի խնդիրի լուժումը գտնի ,ձգտումը դեպի համապատասխանությունը բարելավման օպտիմալ որոշում :
Հղումներ խմբագրել
- ↑ beam search from FOLDOC
- ↑ British Museum Search
- ↑ Norvig, Peter. Paradigms of Artificial Intelligence. http://books.google.com/books?id=X4mhySvjqUAC&pg=PA196&lpg=PA196&dq=beam+search+in+paradigms+of+artificial+intelligence+programming&source=web&ots=20BH2lB3sc&sig=udBIO2Qeg8awaySgwCu7gDEObY4&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA196,M1 Programming
- ↑ 4,0 4,1 4,2 Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. http://www.ijcai.org/papers/0596.pdf
- ↑ Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf
- ↑ Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976
- ↑ Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php