Эвристический поиск

в кожному стані, порівнюючи його з цільовим станом.  

Мал. 6. Початковий стан, набір можливих перших ходів і цільове полягання в грі "8-головоломка " 

Стан з меншим числом фішок, що знаходяться не на своїх місцях, розташовано ближче до цільового стану, і тому буде розглянуто першим.

Проте ця евристика не використовує всю наявну інформацію, тому що вона не приймає до уваги відстань, на яку фішки повинні бути переміщені. "Краща" евристика підсумовувала б всі відстані між фішкою, що знаходиться не на своєму місці, і полем, в яке вона повинна бути переміщена для досягнення цільового стану.

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

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

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

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

Цей приклад ілюструє, наскільки важко знайти хорошу евристику. Наша мета полягає в тому, щоб, використовуючи обмежену інформацію, що міститься в описі окремого стану, все ж таки зробити правильний вибір. Кожна з евристик, запропонованих вище, ігнорує деякі критичні елементи інформації, і тому може бути покращувана. Розробка хорошої евристики — це емпірична проблема, в рішенні якої допомагають міркування і інтуїція. Але все таки вирішальний критерій оцінки евристики — це її ефективність при рішенні практичних задач.

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

Мал. 8. Три можливі варіанти евристики в 8-головоломке

Для початкового стану це значення рівне 0 і збільшується на 1 для кожного рівня пошуку. Це дозволяє записати фактичне число кроків, необхідних для досягнення

1 2 3 4 5 6 7

Похожие работы