Евристичний пошук

План 

Вступ  

Алгоритм евристичного пошуку

1. "Жадібний" алгоритм пошуку

2. Функції евристичної оцінки станів

 

Вступ

У [Polya, 1945] евристика визначається як "вивчення методів і правил відкриттів і винаходів". Це слово має грецький корінь, дієслово eurisco означає "досліджувати". Коли Архімед вискочив з ванни, тримаючи золотий вінець, він закричав "Еврика!", що означає "Я знайшов!". У просторі станів пошуку евристика визначається як набір правив для вибору тих гілок з простору станів, які з найбільшою вірогідністю приведуть до прийнятного рішення проблеми.

Фахівці з штучного інтелекту використовують евристику в двох ситуаціях.

1. Проблема може не мати точного рішення із-за невизначеності в постановці завдання і/або в початкових даних. Медична діагностика — приклад такої проблеми. Певний набір ознак може мати декілька причин; тому лікарі використовують евристику, щоб поставити найбільш точний діагноз і підібрати відповідні методи лікування. Система технічного зору — інший приклад завдання з невизначеністю. Візуальні сцени часто неоднозначні, викликають різні (часто не пов'язані один з одним) припущення щодо протяжності і орієнтації об'єктів. Оптичний обман — хороша ілюстрація таких двозначностей. Системи технічного зору часто використовують евристику для вибору найбільш вірогідної інтерпретації з декількох можливих.

2. Проблема може мати точне рішення, але вартість його пошуку може бути дуже високою

У багатьох завданнях (наприклад, гра в шахи) зростання простору можливих станів носить експоненціальний характер, іншими словами, число можливих станів росте експоненціально із збільшенням глибини пошуку. У цих випадках методи пошуку рішення "в лоб" типу пошуку в глибину або завширшки можуть зайняти дуже багато час. Евристика дозволяє уникнути цієї складності і вести пошук по найбільш "перспективному" шляху, виключаючи з розгляду неперспективні стани і їх нащадки. Евристичні алгоритми можуть (як правило, на це сподіваються проектувальники) зупинити це комбінаторне зростання і знайти прийнятне рішення.

На жаль, подібно до всіх правил відкриття і винаходу, евристика може помилятися. Евристика — це тільки пропозиція наступного кроку, який буде зроблений на шляху вирішення проблеми. Такі припущення часто грунтуються на досвіді або інтуїції. Оскільки евристика використовує таку обмежену інформацію, як опис поточних полягань в списку open, то вона рідко здатна передбачити подальшу поведінку простору станів. Евристика може привести алгоритм пошуку до субоптимального рішення або не знайти рішення взагалі. Це обмеження властиво евристичному пошуку і не може бути усунено "кращою" евристикою або ефективнішим алгоритмом пошуку [Garey і Johnson, 1979].

Евристика і розробка алгоритмів для евристичного пошуку протягом достатнього довгого часу залишаються основним об'єктом дослідження в проблемах штучного інтелекту. Гра і доведення теорем — два найстаріші додатки в області штучного інтелекту; обидва вони потребують евристики для скорочення числа полягань в просторі пошуку. Неможливо розглянути кожен висновок, який може бути зроблений в тій або іншій області математики, або кожен можливий хід на шахівниці. Евристичний пошук — часто єдиний практичний метод вирішення таких проблем.

Дослідження в області експертних систем підтвердило важливість евристики як основного компоненту при рішенні задач. Експерт-людина, вирішуючи проблему, аналізує доступну інформацію і робить висновок. Інтуїтивні

1 2 3 4 5 6 7