Heuristic function

rdf:langString Евристична функція

rdf:langString В цій статті будуть розглядатися евристичні функції для задачі гри у вісім, що дозволяє найкраще продемонструвати характерні особливості всіх евристичних функцій в цілому. Головоломка «гра в вісім» була однією з перших задач евристичного пошуку. В ході розв'язання цієї головоломки потрібно переміщувати фішки по горизонталі чи по вертикалі на порожню ділянку до тих пір, доки отримана конфігурація не буде відповідати цільовій конфігурації. Середня вартість розв'язку для сформованого випадковим чином екземпляру головоломки «гра в вісім» становить близько 22 етапів. Коефіцієнт розгалуження приблизно дорівнює 3. (Якщо пустий квадрат знаходиться в середині коробки, то кількість можливих ходів дорівнює чотирьом, якщо знаходиться в кутку — двом, а якщо в середині однієї зі сторін — трьом.) Це означає, що при вичерпному пошуку на глибину 22 доведеться розглянути приблизно 322 ≈ 3.1*1010 станів. Відслідковуючи стани, що повторюються, цю кількість станів можна скоротити приблизно в 170000 разів, оскільки існує тільки 9!/2=181440 різних станів, які є досяжними. Ця кількість станів вже краще піддається контролю, але відповідна кількість для гри в п'ятнадцять приблизно рівна 1013, тому для такої головоломки з більш високою складністю потрібно знайти хорошу евристичну функцію. Якщо потрібно знаходити найкоротші рішення з використанням пошуку А*, то потрібна евристична функція, котра ніколи не переоцінює кількість етапів досягнення цілі. * h1 = кількість фішок, що стоять не на своєму місці. На рис.1 всі вісім фішок стоять не на своєму місці, тому початковим стан, що показаний злів, має евристичну оцінку h1=8. Евристична функція h1 є допустимою, оскільки очевидно, що кожну фішку, що знаходиться не на своєму місці, необхідно перемістити якнайменше один раз. * h2 = сума відстаней всіх фішок від їх цільових позицій. Оскільки фішки не можуть пересуватися по діагоналі, відстань, що розраховується, являє собою суму горизонтальних та вертикальних відстаней, така відстань іноді називається відстанню, що вимірюється в міських кварталах, або манхеттенською відстанню. Евристична функція h2 також є допустимою, оскільки все, що може бути зроблено в одному ході, полягає лише в переміщенні однієї фішки на один етап ближче до цілі. Фішки від 1 до 8 в початковому стані, що розглядається, відповідають такому значенню манхеттенської відстані h2=3+1+2+2+2+3+3+2=18. Як можна було припустити, ні одна з функцій не переоцінює вартість рішення, яка рівна 26.