Комбінаторний вибух

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

Наприклад, час, необхідний для відшукання шляху в лабіринті, експоненціально збільшується при збільшенні кількості розгалужень у лабіринті. Аналогічно, час, необхідний для пошуку доказу теорем численних тверджень, росте експоненціально стосовно кількості змінних. Такі i проблеми є в загальному випадку неозорими і називаються NP-hard. Читачів, що ними зацікавляться, ми відсилаємо до спеціальної літератури, зокрема книзі Хопкрофта й Ульмана [Hopcroft and Ullman, 1979].

Проблеми, час рішення яких зв'язано з розмірністю задачі поліноміальної функції, вважаються доступними для огляду. Наприклад, перевірка заданого маршруту в лабіринті або перевірка правильності доведення деякої теореми — доступні для огляду проблеми. Але можна показати, що, на жаль, більшість проблем, що цікавлять нас в області штучного інтелекту, відносяться до класу NP-hard. Тому таке важливе значення придаєтся використанню евристичних методів при їхньому рішенні. Доступний виклад теорії обчислювальної складності, розрахований на читача, несхильного до зайвого теоретизування, можна знайти в роботі Паундстоуна [Poundstone, 1988, Chapters]

Розглянемо такий приклад. Нехай є дві аксіоми, представлені на деякій формальній мові: "Якщо комп'ютер може помилятися, він помилиться" і "Мій комп'ютер може помилятися". Тоді, використовуючи механізм числень тільки правил впливу, ми можемо показати, що справедлива теорема. "Мій комп'ютер помилиться". Це твердження логічно випливає з заданих аксіом у тому змісті, що воно не може бути помилковим, якщо вихідні твердження (аксіоми) правильні. Коректність такого наслідку легко доводиться комп'ютером— усе, що від нього потрібно, так це обробити вираз у формі логічної залежності:

("X) (f (x) É G(X))

,

що читається в такий спосіб:

"Всі елементи F є елементами G, a входить у F, отже, F є G ".

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

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

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

Дата добавления: 2014-01-11