Променевий пошук

В інформатиці, променевий пошук – це евристичний алгоритм пошуку, що досліджує граф, розширюючи найперспективніші вузли в обмеженому їх наборі. Променевий пошук є оптимізацією так званого «пошуку першого-найліпшого» (best-first), що суттєво знижує його вимоги до необхідної кількості пам’яті. best-first пошук в графі, що будує усі тимчасові рішення (стани) по деяким евристикам, що намагаються передбачити наскільки близьким є частковий розв’язок до повного розв’язку (цільового стану). В променевому пошуку лише деяка частина найкращих часткових розв’язків зберігаються як кандидати.

Променевий пошук використовує пошук в ширину, щоб побудувати своє дерево пошуку. На кожному рівні дерева він генерує всіх нащадків станів на поточному рівні, сортуючи їх в порядку збільшення евристичної ваги (значимості). Тим не менш він зберігає тільки певну кількість станів на кожному рівні (так звана ширина променя). Чим більша у пучка променів ширина, тим менше станів видаляється. З нескінченою шириною променя жоден стан не видаляється і променевий пошук ідентичний пошуку в ширину. Ширина пучка обмежує об’єм пам’яті, необхідний для виконання пошуку. Оскільки цільовий стан потенційно може бути видалений, променевий пошук жертвує повнотою (гарантія того, що алгоритм буде припинений з розв’язком, якщо він існує) та оптимальністю (гарантія того, що він знайде найкращий розв’язок).

Ширина пучка

Ширина пучка може бути або фіксованою, або змінною. Один з підходів ,що використовує змінну ширину пучка стартує з мінімальною шириною. Якщо не буде знайдено розв’язку, то промінь розширюється і процедура повторюється.