Променевий пошук
В інформатиці, променевий пошук – це евристичний алгоритм пошуку, що досліджує граф, розширюючи найперспективніші вузли в обмеженому їх наборі. Променевий пошук є оптимізацією так званого «пошуку першого-найліпшого» (best-first), що суттєво знижує його вимоги до необхідної кількості пам’яті. best-first пошук в графі, що будує усі тимчасові рішення (стани) по деяких евристиках, що намагаються передбачити наскільки близьким є частковий розв’язок до повного розв’язку (цільового стану). В променевому пошуку лише деяка частина найкращих часткових розв’язків зберігаються як кандидати.
| Алгоритми пошуку графами та деревами |
|---|
|
| Переліки |
|
| Пов'язані теми |
Променевий пошук використовує пошук в ширину, щоб побудувати своє дерево пошуку. На кожному рівні дерева він генерує всіх нащадків станів на поточному рівні, сортуючи їх в порядку збільшення евристичної ваги (значимості). Тим не менш він зберігає тільки певну кількість станів на кожному рівні (так звана ширина променя). Чим більша у пучка променів ширина, тим менше станів видаляється. З нескінченою шириною променя жоден стан не видаляється і променевий пошук ідентичний пошуку в ширину. Ширина пучка обмежує об’єм пам’яті, необхідний для виконання пошуку. Оскільки цільовий стан потенційно може бути видалений, променевий пошук жертвує повнотою (гарантія того, що алгоритм буде припинений з розв’язком, якщо він існує) та оптимальністю (гарантія того, що він знайде найкращий розв’язок).
Ширина пучка
Ширина пучка може бути або фіксованою, або змінною. Один з підходів ,що використовує змінну ширину пучка стартує з мінімальною шириною. Якщо не буде знайдено розв’язку, то промінь розширюється і процедура повторюється.
Походження терміну термін
Термін "променевий пошук" ввів Радж Редді в Carnegie Mellon University у 1976 році.
Використання променевого пошуку
Променевий пошук найчастіше використовується для підтримання поступливості у великих системах з недостатньою кількістю пам’яті для збереження всього дерева пошуку. Наприклад, він використовується в багатьох системах машинного перекладу. Щоб обрати найкращий переклад, кожна частина обробляється і з’являються різні варіанти перекладу слова. Найкращі переклади згідно з їх структурою речення зберігаються, а інші відкидаються. Перекладач потім оцінює переклади за заданими критеріями, обираючи переклад, що найкраще відповідає цілі. Вперше променевий пошук використали у Harpy Speech Recognition System, CMU 1976.
Додаткові факти
Прагнення подолати обмеження, пов’язані з нестачею пам’яті призвело до того, що свого часу перевага віддавалася алгоритмам, що передбачають зберігання в пам’яті лише одного вузла, але, як з’ясувалося, такий підхід часто є надто радикальним способом економити пам’ять. В алгоритмі локального променевого пошуку передбачено відслідковування K станів, а не тільки одного стану. Робота цього алгоритму починається з формування випадковим чином K станів. На кожному етапі формуються всі нащадки всіх K станів. Якщо який-небудь з цих K нащадків відповідає цільовому стану - алгоритм зупиняється. Інакше алгоритм обирає з загального списку найкращих нащадків і повторює цикл.
На перший погляд може здатися, що локальний променевий пошук з K станами являє собою ні що інше, як виконання K перезапусків випадковим чином, але не послідовно, а паралельно. Тим не менш, в реальності ці два алгоритми є абсолютно різними. При пошуку з перезапуском випадковим чином кожен процес пошуку виконується незалежно один від інших. В локальному променевому пошуку корисна інформація передається по K паралельних потоках пошуку. Наприклад, якщо в одному стані виробляється кілька хороших нащадків, а в усіх інших K-1 станах виробляються погані нащадки, то виникає такий ефект, як в разі якби потік, що контролює перший стан, повідомив іншим потокам: «Йдіть всі сюди, тут трава зеленіша!». Цей алгоритм здатен швидко відмовлятися від безплідних пошуків і перекинути свої ресурси туди, де досягли найбільший прогрес.
У своїй найпростішій формі локальний променевий пошук може страждати від відсутності різноманітності між K станами, оскільки всі ці стани здатні швидко зосередитись в невеликому регіоні простору станів, в результаті чого цей пошук починає ненабагато відрізнятися від дорогої версії пошуку із сходженням на вершину. При стохастичному променевому пошуку замість вибору найкращих K нащадків випадковим чином, при тому, що ймовірність вибору даного конкретного нащадка являє собою функцію значення його оцінки, що зростає. Стохастичний променевий пошук має деяку схожість з процесом природного відбору, в якому нащадки деякого стану (організму) утворюють наступне покоління згідно зі значенням їхньої оцінки (відповідно до їхньої життєвої придатності).