Претрага бима
У информатици, претрага бима је хеуристичан алгоритам за претрагу који истражује графикон ширећи чвор, који највише обећава, у лимитиран цет. Претрага бима је оптимизација Претраге према најбољем која смањује меморијску захтевност. Претрага „први најбољи“ је графичка претрага која сортира сва парцијална решења у зависности од неке хеуристике која покушава да предвиди колико близз је парцијално решење комплетном решењу (стање поготка). Али у претрази бима, само предодређени број најбољих парцијалних решења се чувају као кандидати.[1]
Претрага бима користи Претрагу по ширини за креирање стабла претраге. На сваком нивоу стабала, она генерише сва успешна стања, сортирајући их од најмањег ка највећем по цени хеуристике.[2] Међутим, она складишти само предодређен број најбољих стања на сваком нивоу (названом ширина бима). Само та стања се проширују даље. Што је већа ширина бима, мање стања је одбачено. Са бесконачном ширином бима, ниједно стање није одбачено и претрага миба је идентична претрази по ширини. Ширина бима веже меморију потребну да изведе претрагу. Пошто стање поготка потенцијално може бити одбачено, претрага бима жртвује комплетност (гаранцију да ће алгоритам избацити решење, ако оно постоји) и оптималност (гаранцију да ће бити пронађено најбоље решење.
Ширина бима може бити фиксна или варијабилна. Приступ који користи варијабилну ширину бима почиње са ширином на минимуму. Ако решење није пронађено, бим се шири и процес се понавља.[3]
Име уреди
Термин „претрага бима“ је осмислио Раж Реди(Raj Reddy), Универзитет Карнеги Мелон, 1976.
Употреба уреди
Претрага бима се најчешће користи да одржи обрадивост у великим системима са недовољном количином меморије за склаштење целог стабла претраге.[4] Нпр. Користи се у многим системима за „превод“ машина.[5] Да би се пронашло најбоље решење, сваки део се процесуира, и много различитих начина превода речи се појави. Неколико најбољих превода према структурама реченице се чувају док се остали одбацују. Преводилац онда оцењује преводе према датом критеријуму, бирајући превод који вајбоље чува погодак. Претрага бима је први пут употребљена 1976 у Harpy Speech Recognition System-у.[6]
Екстензије уреди
Претрага бима је комплетирана кобиновањем са Претрагом у дубину што је резултовало Бим-Стек Претрагом[7] и Претрагом бима у дубину[4], као и лимитираном претрагом противречности, што је резултовало Бектрекингом бим претраге са лимитираним раскораком (енгл. Beam Search Using Limited Discrepancy Backtracking).[4] Ови алгоритми за претрагу су алгоритми у "свако доба" (енгл. anytime algorithms) који проналазе добра али често полу-оптимална решења брзо, као претрага бима, а затим се враћају и настављају да траже побољшања решења док не пронађу оптимално.
Референце уреди
- ^ beam search from FOLDOC Архивирано на сајту Wayback Machine (25. јануар 2020)
- ^ 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
- ^ а б в Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. Архивирано на сајту Wayback Machine (16. мај 2008)
- ^ „Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation".” (PDF). Архивирано из оригинала (PDF) 18. 06. 2006. г. Приступљено 31. 05. 2013.
- ^ 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.”. Архивирано из оригинала 20. 04. 2021. г. Приступљено 31. 05. 2013.