Обмежуючі правила та евристики як засіб скорочення перебору

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

При розгляді задач, що належать до класу NP, важливе місце посідає знаходження варіантів розв'язку цих задач для певних наборів даних (але не для всіх даних!) за поліноміальний час. Для цього досліднику бажано підказати шлях, який звільняє від необхідності, базуючись на тих особливостях, що характеризують задачу розгляду. Ці особливості і називають евристиками, а правила їх використання називають евристичними правилами. Евристичні правила можуть бути як дуже простими, так і досить складними. Прикладом простої евристики можуть служити прислів'я. Багато з них можна розглядати керівництвом до дії в повсякденному житті: "Сім разів відміряй, а потім відріж." Оскільки евристичні правила носять рекомендаційний характер, то евристичні методи не завжди приводять до бажаних результатів розв'язку задачі. Отже, бажано мати якомога більший набір евристик

Для розуміння евристичного підходу розглянемо два типи задач: добре визначені задачі і погано визначені задачі.

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

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

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

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

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

Серед загального огляду евристик важливе місце посідає основна евристика – принцип навчання, сформульований Мінським і Селфріджем. Цей принцип формулюється так: "У новій ситуації спробуйте використати методи, що найкраще працювали в аналогічних відомих ситуаціях попередньо". В такому разі важливим є вибір критерію подібності задач, ситуацій, складною. А ця проблема є досить складною. Для визначення міри подібності задач Мінським було введено поняття евристичного зв'язку задачі. Ця ідея приводить до важливих висновків відносно природи інтелекту і досить поширена при вирішенні задач штучного інтелекту.

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

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

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

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

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

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

Часто трапляється, що існує не одна евристика, а декілька, і вони повністю або частково суперечать одна одній. Тоді окремою проблемою стає проблема застосування евристик.

7. Задача розпізнавання як задача прийняття рішень.