Виконання умов

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

Галузь інформатики, яка займається цими завданнями, називається програмуванням з обмеженнями. Виконання умов є суттю багатьох логічних задач (як-от, задача про 8 ферзів, задача Ейнштейна, алгеброграма). На Знаємо це ви можете спробувати судоку, паркани і бінарні кросворди. Практичне застосування цих знань – це компіляція конфігурацій продукту, які відповідають заданим обмеженням, або створення розкладів (шкільних розкладів, маршрутів транспорту, виробничої логістики, сітки турнірних матчів).

Розв’язування задач на виконання умов

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

Покрокова побудова рішення

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

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

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

Поширення обмежень

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

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

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

Поступове поліпшення

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

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

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

У пошуку сукупностей ми покращуємо багато оцінок одночасно. Це дає змогу вибрати найкращу із поточної сукупності та, можливо, поєднати різні оцінки. Прикладом є генетичні алгоритми, створені за принципом еволюції. Оцінки, які продовжуються до наступного покоління, вибираються відповідно до їх якості, об’єднуються («схрещування») і, можливо, дещо змінюються випадковим чином («мутація»). Інші природничі алгоритми, які використовують значну кількість взаємодіючих агентів, що представляють повні оцінки, також належать до цієї категорії. (Наприклад, у «оптимізації мурашиної колонії» кожна мураха має пов’язану оцінку і випромінює феромонний слід різної сили залежно від її якості. Що краща ця оцінка, то ймовірніше, що інші мурахи спробують отримати подібну.)