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

Одним із критерії, що дозволяють охарактеризувати якість евристичної функції, є ефективний коефіцієнт розгалуження b*. Якщо загальна кількість вузлів, що виробляються в процесі пошуку А* розв'язання конкретної задачі, дорівнює N, а глибина розв'язку дорівнює d, то b* являє собою коефіцієнт розгалуження, який повинно мати однорідне дерево з глибиною d для того, щоб в ньому містилося N+1 вузлів. Тому справедлива наступна формула:

N+1=1+b*+(b*)²+…+(b*)^d

Наприклад, якщо алгоритм А* знаходить рішення на глибині 5 з використанням 52 вузлів, то ефективний коефіцієнт розгалуження дорівнює 1,92. Ефективний коефіцієнт розгалуження може змінюватися від одного екземпляра однієї і тієї ж задачі до іншого, але зазвичай у випадку достатньо складних задач залишається відносно постійним. Тому експериментальні зміни коефіцієнта b* на невеликій множині задач може стати гарним критерієм загальної корисності евристичної функції, що розглядається. Добре спроектована евристична функція повинна мати значення b* близьке до 1, що дозволяє швидко розв'язувати доволі великі задачі.

Для перевірки евристичних функцій h1 і h2 було сформовано випадковим чином 1200 екземплярів задачі з довжиною рішення від 2 до 24 (по 100 екземплярів для кожного чіткого значення довжини) та знайшли їх рішення за допомогою пошуку з ітеративним заглибленням та пошуку в дереві по алгоритму А* із застосуванням евристичних функцій h1 та h2. Дані про середню кількість вузлів, розвернутих при використанні кожної стратегії та ефективний коефіцієнт розгалуження показані в таблиці 1. Ці результати показують, що евристична функція h2 краща, ніж h1 та набагато краще в порівнянні з використанням пошуку з ітеративним заглибленням. Табл.1 Порівняння значень вартості пошуку та ефективного коефіцієнта розгалуження для алгоритмів Iterative-Deepening-Search та A* з h1 та h2.

Інтерес представляє питання про те, чи завжди евристична функція h2 краща за h1. Відповідь на це питання є позитивною. На основі визначень цих двох евристичних функцій можна легко дійти до висновку, що для будь-якого вузла n справедливий вираз h_2(n)≥h_1(n). Таким чином, можна стверджувати, що евристика h₂ домінує над h₁. Домінування напряму пов'язане з ефективністю: при пошуку А* з використанням функції h₂ ніколи не відбувається розгалуження більшої кількості вузлів, ніж при пошуку А* з використанням h₁ (можливо, за виключенням декількох вузлів з f(n)<C*). Доведення цього твердження є нескладним. Кожен вузол із значенням f(n)<C* повинен бути розгорнутим. Це аналогічно твердженню, що напевно повинен бути розгорнутим кожен вузол зі значенням h(n)<C*-g(n). Але оскільки для всіх вузлів значення h₂, принаймні, не менше значення h₁, то кожен вузол, котрий повинен бути розгалужений в пошуку А* з h₂, буде також напевно розгорнутий при пошуку з h₁, а застосування евристичної функції h₁, може до того ж викликати і розгортання інших вузлів. Тому завжди краще використовувати евристичну функцію з більш високими значеннями, при тих умовах, що ця функція не переоцінює довжину шляху рішення та що час обчислення цієї евристичної функції не надто великий.

Евристичні функції h₁ (в якій використовується кількість фішок, що стоять не на своєму місці) та h₂ (в якій використовується манхеттенська відстань) є досить непоганими евристичними функціями для задачі гри в вісім і що функція h₂ — з них найкраща. Але на основі чого саме була запропонована функція h₂? Чи можливо, щоб комп'ютер міг скласти деяку евристичну функцію механічно?

Евристичні функції h₁ та h₂ являють собою оцінки довжини шляху, що залишився, для задачі гри в вісім, але вони, крім того, повертають ідеально точні значення довжини шляху для спрощених версій гри. Якби правила гри в вісім змінились таким чином, щоб будь-яку фішку можна було пересувати куди завгодно, а не тільки на сусідній пустий квадрат, то евристична функція h₁ повертала б точну кількість етапів в найкоротшому рішенні. Аналогічним чином, якби будь-яку фішку можна було переміщувати у клітинку в будь-якому напрямку, навіть на зайняту клітинку, то точна кількість етапів в найкоротшому рішенні повертала б евристична функція h₂. Задача з меншою кількістю обмежень на можливі дії називається послабленою задачею. Вартість оптимального рішення послабленої задачі являє собою допустиму евристику для первісної задачі. Така евристична функція є допустимою, оскільки оптимальне рішення первісної задачі, за визначенням, служить також рішенням послабленої задачі і тому повинно бути, як мінімум, таким само дорогим, як і оптимальне рішення послабленої задачі. Оскільки значення похідної евристичної функції являє собою точну вартість рішення послабленої задачі, ця функція повинна підкорятися нерівності трикутника і тому повинна бути монотонною.

Якщо формулювання задачі записано на якійсь формальній мові, то існує можливість сформувати послаблену задачу автоматично. Наприклад, якщо дії в грі в вісім описані наступним чином:

Фішка може бути пересунута з квадрата А в квадрат В, якщо квадрат А є суміжним по горизонталі чи по вертикалі з квадратом В та квадрат В пустий

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

1. Фішка може бути пересунута з квадрата А в квадрат В, якщо квадрат А є суміжним з квадратом В.
2. Фішка може бути пересунута з квадрата А в квадрат В, якщо квадрат В пустий.
3. Фішка може бути пересунута з квадрата А в квадрат В.

На основі послабленої задачі 1) можна вивести функцію h₂ (манхеттенська відстань). В основі цих суджень лежить те,, що h₂ повинна являти собою правильну оцінку, якщо кожна фішка пересувається до місця її призначення по черзі. На основі послабленої задачі 3) можна отримати евристичну функцію h₁ (фішки, що стоять не на своїх місцях), оскільки ця оцінка була б правильною, якби фішки можна було пересувати в призначене для них місце за один етап. Зверніть увагу на те, що тут суттєвою є можливість розв'язувати послаблені задачі, що створені за допомогою вказаного методу, фактично без будь-якого пошуку, оскільки послаблені правила забезпечують декомпозицію цієї задачі на вісім незалежних під задач. Якби було складно розв'язувати і послаблену задачу, то був би дорогим сам процес отримання значень відповідної евристичної функції.

Для автоматичного формування евристичних функцій на основі визначення задач з використанням методу «послабленої задачі» та деяких інших методів може застосовуватись програма під назвою Absolver. Програма Absolver склала для задачі гри в вісім нову евристичну функцію, найкращу в порівнянні з усіма, що існували раніше, а також знайшла першу корисну евристичну функцію для знаменитої головоломки «кубик Рубика».

Одна з проблем, що виникають при складанні нових евристичних функцій, полягає в тому, що часто не вдається отримати евристичну функцію, котра була б «найкращою в усіх відношеннях» в порівнянні з іншими. Якщо для рішення якоїсь задачі може бути застосована ціла колекція допустимих евристичних функцій h₁…h_m, і жодна з них не домінує над якоюсь з інших функцій, то яка з цих функцій повинна бути обрана? Виявилось, що такий вибір робити не потрібно, оскільки можна взяти від них усіх все найкраще, визначивши такий критерій вибору:

h(n)=max{h1()...hm(n)}

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

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

Рис.2 Підзадача для екземпляру гри в вісім, що показаний на рис.1. Завдання полягає в тому, щоб пересунути фішки 1, 2, 3 та 4 в їх правильні позиції, не турбуючись про те, що трапиться з іншими фішками

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

Вибір фішок 1 — 2 — 3 — 4 є доволі випадковим; можна було б так само створити бази даних для фішок 5 — 6 — 7 — 8, 2 — 4 — 6 — 8 тощо. По даним кожної бази даних формується допустима евристична функція, як було описано вище, застосовуючи їх максимальне значення. Евристична функція такого вигляду є набагато точнішою в порівнянні з манхеттенською відстанню; кількість вузлів, що виробляються при рішенні сформованих випадковим чином екземплярів задачі гри в п'ятнадцять, може бути зменшено в 1000 разів.

Являє інтерес питання про те, чи можна складати значення евристичних функцій, що отримані з баз даних 1 — 2 — 3 — 4 та 5 — 6 — 7 — 8, оскільки очевидно, що існуючі дві під задачі не перекриваються. Чи буде при цьому все ще отримана допустима евристична функція? Відповідь на це питання є негативною, оскільки в рішеннях підзадачі 1 — 2 — 3 — 4 та підзадачі 5 — 6 — 7 — 8 для даного конкретного стану повинні напевно бути присутніми деякі загальні ходи. Справа в тому, що малоймовірна ситуація, при якій фішки 1 — 2 — 3 — 4 можна було б пересунути на свої місця, не зачіпаючи фішок 5 — 6 — 7 — 8, і навпаки. Але що буде, якщо не враховувати ці ходи? Іншими словами, припустимо, що реєструється не загальна вартість рішення підзадачі 1 — 2 — 3 — 4, а тільки кількість ходів,, в яких зачіпаються фішки 1 — 2 — 3 — 4. В такому випадку можна легко визначити, що сума цих двох вартостей все ще являє собою нижню границю вартості рішення всієї задачі. Саме ця ідея лежить в основі баз даних з шаблонами, що не перетинаються. Застосування таких баз даних дозволяє розв'язувати випадково вибрані екземпляри задачі гри в п'ятнадцять за декілька мілісекунд — кількість сформованих вузлів скорочується приблизно в 10000 разів у порівнянні з використанням манхеттенської відстані. Для задачі гри в 24 може бути досягнуте прискорення приблизно в мільйон разів.

Бази даних з шаблонами, що не перетинаються успішно застосовуються для рішення головоломок з ковзкими фішками, оскільки сама задача може бути розділена таким чином, що кожен хід впливає лише на одну підзадачу, так як одночасно відбувається переміщення лише однієї фішки. При рішенні таких задач, як кубик Рубика, подібне розділення не може бути виконане, оскільки кожен хід впливає на положення 8 чи 9 з 26 елементів кубика. В даний час немає повного розуміння того, як можна визначити бази даних з шаблонами, що не перетинаються, для подібних задач.

Припускається, що евристична функція h(n) оцінює вартість розв'язку, починаючи зі стану, пов'язаного з вузлом n. Як може деякий агент скласти подібну функцію? Одне з рішень було запропоновано вище, а саме: агент повинен сформулювати послаблені задачі, для яких може бути легко знайдений оптимальний розв'язок. Ще один підхід полягає в тому, що агент повинен навчатися на основі отриманого досвіду. Тут під «отриманням досвіду» мається на увазі, наприклад, розв'язання великої кількості екземплярів гри в вісім. Кожен оптимальний розв'язок задачі гри в вісім дає приклади, на основі яких можна вивчати функцію h(n). Кожен приклад складається зі стану, що взятий зі шляху розв'язку, та фактичної вартості шляху від цієї точки до розв'язку. На основі даних прикладів за допомогою алгоритму індуктивного навчання може бути сформована деяка функція h(n), що здатна (при вдалому збігу обставин) передбачати вартість розв'язків для інших станів, які виникають під час пошуку.

Метод індуктивного навчання найкраще діє, коли в ньому враховується характеристики станів, що релевантні для оцінки цього стану, а не просто загальний опис стану. Наприклад, характеристика «кількість фішок, що стоять не на своєму місці» може бути корисною при передбаченні фактичного видалення деякого стану від цілі. Назвемо цю характеристику x₁(n). Наприклад, можна взяти 100 сформованих випадковим чином конфігурацій головоломки гри в вісім та зібрати статистичні дані про фактичні вартості їх розв'язків. Припустимо, це дозволяє знайти, що при x₁(n)=5, середня вартість розв'язку становить приблизно 12, і т. д. Наявність таких даних дозволяє використовувати значення x₁ для передбачення значень функції h(n). Безумовно, можна також застосувати одразу декілька характеристик. Другою характеристикою, x₂(n), може бути «кількість пар суміжних фішок, які є також суміжними в цільовому стані». Яким чином можна скомбінувати значення x₁(n) та x₂(n) для передбачення значення h(n)? Загальноприйнятий підхід полягає у використанні лінійної комбінації, як показано нижче.

h(n)=c1x1(n)+c2x2(n)

Константи c₁ та с₂ корегуються для досягнення найкращої відповідності фактичним даним про вартості розв'язків. Припускається, що константа с₁ повинна бути позитивною, а с₂ — негативною.

1. Рассел С., Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ./Рассел С., Норвиг П. — М.: Издательский дом «Вильямс», 2006. — 1408с.

• Евристичний алгоритм