Փնտրման ճառագայթ
Փնտրման ճառագայթ | |
---|---|
Տեսակ | փնտրման ալգորիթմ և greedy algorithm? |
Դաս | լավագույն առաջին որոնում և local search? |
Ինֆորմատիկայում փնտրման ճառագայթն իրենից ներկայացնում է էվրիստիկական փնտրման ալգորիթմ, որն ուսումնասիրում է սահմանափակ լրակազմից առավել խոստումնալից հանգույցներով գրաֆ։ Փնտրման ճառագայթը լավագույն առաջին փնտրման օպտիմիզացումն է, որը նվազեցնում է իր հիշողության պահանջները։ Լավագույն առաջի որոնումը գրաֆի որոնման մեջ, որը պատվեր է բոլոր մասնակի լուծումների (դրություն), որոշ հերոստիկ, որը փորձում է գուշակել, թե որն է մոտ մասնակի լուծմանը ամբողջական լուծումում (դրության նպատակը)։ Բայց ճառագայթային փնտրման մեջ լավագույն մասնակի լուծումների միայն կանխորոշված շարքերն են պահվում որպես թեկնածուներ։
Որոնման լայնության օգտագործումը լայնությունում որոնման ծառը կառուցելու համար է։ Ծառի յուրաքանչյուր մակարդակում գերակշռում է բոլոր հետնորդների վիճակները ներկա մակարդակից, դասավորում դրանք աճման կարգով, տալիս է հերոստիկ արժեք։ Սակայն այն միայն հիշում է որոշակի թվով դրություններ յուրաքանչյուր մակարդակում (այսպես կոչված վերդիր լայնությունը)։ Որքան մեծ է վերդիր լայնությունը, այնքան քիչ են երկրները հեռանում։ Անսահմանափակ լայնությունը ճառագայթը դրություններ են կտրում և փնտրման ճառագայթի նույնական են դեպի որոնման լայնությունը։ Վերդիր լայնությունը մեծացնում է հիշողության ծավալը, որը անհրաժեշտ է փնտրման համար։ Դրության նպատակը կարող է կրճատվել ճառագայթային որոնման ամբողջականացման պատճառով (երաշխիքը, որ այդ ալգորիթմը չի դադարեցնի իր լուծումը, եթե այն գոյություն ունի)և օպտիմալության (երաշխիքը, որ նա կգտնի լավագույն լուծումը)։
Ճառագայթի լայնությունը կարող է կամ պետք է լինի հաստատուն կամ փոփոխական։ Այն մոտեցումը, որը կիրառում է փոփոխական ճառագայթ, լայնությունը սկսում է նվազագույնից։ Եթե որևէ լուծում չի գտնվում, ապա ճառագայթի լայնությունթյունը մեծանում է և պրոցեսը նորից է կրկնվում։
Անուն
[խմբագրել | խմբագրել կոդը]Փնտրման ճառագայթ տերմինը հնարել է Ռաջ Ռեդդին 1976 թվականին, Քարնեգի Մելլոն համալսարանում։
Օգտագործումը
[խմբագրել | խմբագրել կոդը]Վերդիր փնտրումը առավել հաճախ օգտագործվում են ճկունության պահպանման համար մեծ համակարգերում, որոնք ունեն քիչ հիշողություն որոնման ծառը պահպանելու համար։ Օրինակ, այն օգտագործվում է բազմաթիվ մեքենաների թարգմանչական համակարգերում։ Որպեսզի ընտրվի լավագույն թարգմանությունը, յուրաքանչյուր մաս մշակվում է և տարբեր ձևեր են հայտնվում բառերը թարգմանելու։ Լավագույն թարգմանության համար կախված նրանց նախադասության կառուցվածքից պահպանվում են, իսկ մնացածը անտեսվում են։ Թարգմանիչը հետո գնահատվում է թարգմանություններով ընտրելով ամենալավ թարգմանությունը, որը պահում է նպատակները։ Այսպիսի ձևը առաջին անգամ օգտագործվել է Հարփի Սփիչ սիստեմում (Harpy Speech Recognition System) CMU 1976 թ.։
Ընդլայնումը
[խմբագրել | խմբագրել կոդը]Ճառագայթային փնտրումը կատարվել է լրիվությամբ համատեղելով այն խորության փնտրման հետ, որի արդյունքում որոնման ճառագայթը պահպանվում է որոնման ճառագայթ պահոցում և առաջին որոնման ճառագայթի խորությունում և սահմանափակ որոնման անհամապատասխանությունում ինչի արդյունքում որոնման ճառագայթը, որը օգտագործվում է փնտրման սահմանափակման մեջ անհամատեղելի է դառնում (լամպ)։ Արդյունքում որոնման ալգորիթմները համարվում են ալգորիթմներ ցանկացած ժամանակի, որը կարող է գտնել լավ, բայց ոչ օպտիմալ խնդիրներ արագ, ինչպես փնտրման ճառագայթը, այնուհետև նորից վերադարձնել և շարունակել, որպեսզի խնդիրի լուժումը գտնի, ձգտումը դեպի համապատասխանությունը բարելավման օպտիմալ որոշում։
Աղբյուրներ
[խմբագրել | խմբագրել կոդը]Հոդվածի սկզբնական տարբերակը թարգմանվել է անգլերեն վիքիպեդիայի համանուն հոդվածից։