Евристичний пошук
План
Вступ
Алгоритм евристичного пошуку
1. "Жадібний" алгоритм пошуку
2. Функції евристичної оцінки станів
Вступ
У [Polya, 1945] евристика визначається як "вивчення методів і правил відкриттів і винаходів". Це слово має грецький корінь, дієслово eurisco означає "досліджувати". Коли Архімед вискочив з ванни, тримаючи золотий вінець, він закричав "Еврика!", що означає "Я знайшов!". У просторі станів пошуку евристика визначається як набір правив для вибору тих гілок з простору станів, які з найбільшою вірогідністю приведуть до прийнятного рішення проблеми.
Фахівці з штучного інтелекту використовують евристику в двох ситуаціях.
1. Проблема може не мати точного рішення із-за невизначеності в постановці завдання і/або в початкових даних. Медична діагностика — приклад такої проблеми. Певний набір ознак може мати декілька причин; тому лікарі використовують евристику, щоб поставити найбільш точний діагноз і підібрати відповідні методи лікування. Система технічного зору — інший приклад завдання з невизначеністю. Візуальні сцени часто неоднозначні, викликають різні (часто не пов'язані один з одним) припущення щодо протяжності і орієнтації об'єктів. Оптичний обман — хороша ілюстрація таких двозначностей. Системи технічного зору часто використовують евристику для вибору найбільш вірогідної інтерпретації з декількох можливих.
2. Проблема може мати точне рішення, але вартість його пошуку може бути дуже високою
На жаль, подібно до всіх правил відкриття і винаходу, евристика може помилятися. Евристика — це тільки пропозиція наступного кроку, який буде зроблений на шляху вирішення проблеми. Такі припущення часто грунтуються на досвіді або інтуїції. Оскільки евристика використовує таку обмежену інформацію, як опис поточних полягань в списку open, то вона рідко здатна передбачити подальшу поведінку простору станів. Евристика може привести алгоритм пошуку до субоптимального рішення або не знайти рішення взагалі. Це обмеження властиво евристичному пошуку і не може бути усунено "кращою" евристикою або ефективнішим алгоритмом пошуку [Garey і Johnson, 1979].
Евристика і розробка алгоритмів для евристичного пошуку протягом достатнього довгого часу залишаються основним об'єктом дослідження в проблемах штучного інтелекту. Гра і доведення теорем — два найстаріші додатки в області штучного інтелекту; обидва вони потребують евристики для скорочення числа полягань в просторі пошуку. Неможливо розглянути кожен висновок, який може бути зроблений в тій або іншій області математики, або кожен можливий хід на шахівниці. Евристичний пошук — часто єдиний практичний метод вирішення таких проблем.
Дослідження в області експертних систем підтвердило важливість евристики як основного компоненту при рішенні задач. Експерт-людина, вирішуючи проблему, аналізує доступну інформацію і робить висновок. Інтуїтивні