Пошук у просторі станів

Класичний період: гри і доказ теорем

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

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

• вихідний стан проблеми, наприклад вихідний стан головоломки;

• тест завершення — перевірка, чи досягнутий необхідний кінцевий чи стан знайдений рішенням проблеми (прикладом може послужити правило визначення, чи зібрана головоломка);

• безліч операцій, які можна використовувати для зміни поточного стану проблеми, наприклад чи кроки переміщення фігур при збірці головоломки.

Рис. 2.1. Дерево простору станів головоломки Scrabble з буквами Т, С и А

Один із способів представлення такого концептуального простору станів — граф, у якому станам відповідають вузли, а операціям — дуги. Розглянемо як приклад задачу побудови слова з деякої безлічі букв, як у грі Scrabble. Задавши набором операцій установки букв, можна сформувати простір станів.

Припустимо, що безліч доступних букв включає Т, С і А. На кожному рівні графа ми будемо додавати по одній визначеній букві. Кожна галузь, що виходить з вузла, відповідає позиції букви у визначену позицію в послідовності, а ця послідовність повинна утворити осмислене слово рис. 2.1). Якщо це відбулося, то головоломка вважається зібраною (наприклад, якщо утворилася комбінація "act" чи "cat"). (Зараз ми не будемо прагнути зібрати яке-небудь складне слово на зразок "scrabble", що може принести гравцю більше очків.)

Цей простір станів володіє двома цікавими властивостями, що притаманні далеко не всім просторам станів:

• воно кінцеве, оскільки існує тільки п1 способів розставити п букв;

• воно не містить повторюваних вузлів, що може привести до утворення петель на графі.

Метод формування анаграм послідовним перерахуванням являє приклад застосування алгоритму, що одержав найменування generate-and-test (породження і перевірка).

(1) Генерувати новий стан, модифікуючи існуючий; наприклад, змінити послідовність букв, додавши нову в існуючу послідовність.

(2) Перевірити, чи не являється утворений стан кінцевим (рішенням); наприклад, перевірити, чи не являється утворена послідовність осмисленим словом. Якщо це так, то завершити, інакше перейти до кроку (1).

Безліч рішень, що задовольняють умові на кроці (2), іноді називають простором рішень. У деяких головоломках, наприклад у вже згаданої ''8 ферзів", рішень багато, а в інших існує усього декілька або тільки одне. Дійсно, існує досить багато способів розмістити вісім ферзів на шахівниці так, щоб жодна з них не виявилася під боєм, а от для головоломки "8-Puzzle" існує єдине рішення (див. впр. 7).

Алгоритм має два основних варіанти: пошук у глибину (depth-first search) і пошук у ширину (breadth-first search). Відрізняються варіанти порядком формування станів на кроці (1). Дійсні алгоритми приведені у впр. 5, а тут ми дамо тільки їх неформальний опис.

Для будь-якого даного вузла N алгоритм пошуку в глибину будує нащадок цього вузла, тобто формує стан, який утвориться в результаті застосування операторів до вузла N, а потім переходить до формування вузла, найближчого до N, на тому ж рівні графа ("сусіду" N), тобто формує стан, який утвориться в результаті застосування оператора до вузла-батька N. Алгоритм пошуку в ширину діє навпаки — спочатку формуються всі "сусіди" вузла N, а потім уже будуються його нащадки. Таким чином, в алгоритмі пошуку в ширину проглядаються послідовно стани, які представлені вузлами того самого рівня на графі рис. 2.2), а в алгоритмі пошуку в глибину проглядаються стани на одному шляху, а потім відбувається повернення назад на один рівень і формується наступний шлях (рис. 2.3).

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

Рис. 2.2. Граф простору станів при використанні алгоритму пошуку в ширину

Рис. 2.3. Граф простору станів при використанні алгоритму пошуку в глибину

Обидва алгоритми завершать роботу (знайдуть кінцевий стан) після формування вузла "act'', а не "cat". Але алгоритму пошуку в ширину прийдеться для цього "відвідати" п'ять вузлів (сформувати і проаналізувати п'ять станів), а алгоритму пошуку в глибину — чотири.

Відзначимо, що властивості цих алгоритмів істотно відрізняються.

• Алгоритм пошуку в ширину відшукує рішення, шлях до якого на графі— найкоротший, якщо таке існує. Іншими словами, він знаходить найкоротший шлях між вихідним станом і рішенням. Алгоритми, що володіють такою властивістю, називаються розв'язними (admissible).

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

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

В ігрових програмах також використовується пошук в просторі станів, але стратегія пошуку більш вибірна, ніж у випадку прямого застосування алгоритму generate-and-test. Крім того, потрібно брати до уваги і те, що в грі, як правило, беруть участь дві сторони. Були розроблені досить непогані програми для гри в шашки, нарди і шахи. Створені програми гри в шахи не можна віднести до класу систем, заснованих на знаннях, а скоріше до класу програм, що володіють здатністю вибірково аналізувати простір станів, що значно підвищує швидкість і ефективність аналізу. Методи й алгоритми цього класу в даній книзі розглядатися не будуть,

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

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