Комбінаторний пошук
В інформатиці та штучному інтелекті комбінаторний пошук вивчає пошукові алгоритми для розв'язування прикладів проблем, які загалом вважаються складними, шляхом ефективного дослідження зазвичай великого простору рішень цих екземплярів. Алгоритми комбінаторного пошуку досягають такої ефективності шляхом зменшення ефективного розміру простору пошуку або використання евристик. Деякі алгоритми гарантовано знаходять оптимальне рішення, тоді як інші можуть повертати лише найкраще рішення, знайдене в дослідженій частині простору станів.
Класичні задачі комбінаторного пошуку включають розв'язання головоломки про вісім ферзів або оцінку ходів у іграх із великим деревом гри, таких як реверсі чи шахи .
Вивчення теорії обчислювальної складності допомагає мотивувати комбінаторний пошук. Алгоритми комбінаторного пошуку зазвичай пов'язані з проблемами, які є NP-складними . Вважається, що такі проблеми загалом не можна ефективно вирішити. Проте різні наближення теорії складності припускають, що деякі випадки (наприклад, «маленькі» випадки) цих проблем можуть бути ефективно вирішені. Це справді так, і такі випадки часто мають важливі практичні наслідки.
Загальні алгоритми розв'язання задач комбінаторного пошуку включають:
Прогнозування (планування наперед) є важливим компонентом комбінаторного пошуку, який визначає, приблизно, наскільки глибоко досліджується граф, що представляє проблему. Потреба в певному обмеженні для планування наперед виникає через великі графи задач у багатьох програмах, таких як комп'ютерні шахи та комп'ютерне ґо. Наївний пошук в графі у ширину швидко поглинув би всю пам'ять будь-якого сучасного комп'ютера. Встановлюючи певний ліміт планування наперед, можна ретельно контролювати час алгоритму; його час експоненціально зростає зі збільшенням межі очікування.
Більш складні методи пошуку, такі як альфа-бета відсічення, здатні виключити цілі піддерева дерева пошуку з розгляду. Коли використовуються ці методи, прогноз не є точно визначеною величиною, а натомість або максимальною глибиною пошуку, або деяким типом середнього значення.
- Рассел і Норвіг. Штучний інтелект: сучасний підхід .