АЛГОРИТМ ПРОГРАМИ GPS

General problem solver (G PS) - Загальний вирішувач завдань - одна з найперших програм штучного інтелекту. Вона була запропонована Ален Нью- Елом, Клиффом Шоу і Гербертом Саймоном в кінці 50-х років XX ст. і стала однією з найперших програм штучного інтелекту. Програма G PS дозволяє вирішувати однотипним способом такі несхожі завдання, як обчислення невизначеного інтеграла, логічні головоломки, доведення теорем засобами числення предикатів, граматичний аналіз фрази.

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

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

Алгоритм програми GPS заснований на ідеї відомості вихідної задачі до підзадач трьох стандартних типів. Для зручності подальшого викладу введемо такі позначення:

I - вихідний об'єкт, Е - кінцевий об'єкт,

Про _і Про ₂ , ..., 0, "- оператори перетворення об'єктів; запис 0, (х) позначає об'єкт х одержуваний в результаті перетворення об'єктах за допомогою оператора Про _п т. е. х '= 0, (х).

А = (/) ,, D ₂ , ..., D _n) - відмінність, за яким порівнюються об'єкти; Dj - j -й вид відмінності (/ -е властивість); в подальшому запис Д = 0 означає, що між об'єктами немає відмінностей, тобто об'єкти збігаються, а запис означає, що між об'єктами є відмінності, тобто об'єкти не збігаються.

Програма GPS будує Я-ЯЛЯдерево подзадач, які можуть бути трьох стандартних типів:

Т (х, у) - перетворити об'єкт х в об'єкту,

S (О, А, х, у) - знайти оператор О, зменшує відмінність Д між об'єктами х і у,

А (0, х, у) - застосувати оператор Про до об'єкту х і порівняти х '= 0 (х) з у.

Коренем І-АБО дерева підзадач, тобто початковою вершиною цього дерева є вершина, відповідна вихідної задачі T (I, Е). І- АБО дерево підзадач будується програмою GPS за такими правилами декомпозиції:

• 1. Якщо поточним завданням є завдання виду Т (х, у), то обчислюється різниця Д між об'єктами хну. Якщо Д = 0, то вершина, відповідна завданню Т (х, у), є цільовою (кінцевої) їх - кінцевий об'єкт. Якщо Д ф 0, то програма GPS для завдання Т (х, у) створює підзадачу S (Q, А, х, у).
• 2. Якщо поточним завданням є завдання виду S (Q, А, х, у), то для кожного з операторів Про _ь 0 ₂ , 0, " перевіряється, чи можна його застосувати до об'єкта х. Якщо є оператори О, -, 0, _г 0, _до , які можна застосувати

до об'єкта х, то для кожного з них для завдання S (Q, А, х, у) створюються підзадачі А (0, _г х), А (О _п , х ), ..., A {O _ik , x) відповідно. Тим самим вершина, відповідна завданню 5 (6, Д, х, у), стає ЯЛЯ-вершиною.

3. Якщо поточним завданням є завдання виду А (0, х, у), то виконується оператор перетворення О, тобто знаходиться об'ектх '= 0 (х), і обчислюється різниця А' між об'єктами х 'і у. Потім Д 'і Д (відмінність між об'єктами х і у) порівнюються. Якщо Д '<Д (об'єкт х' менше відрізняється від об'єкта у, ніж об'ектх від у), то для завдання А (О, х, у) створюється подзадача Т (х ', у). Якщо Д '> Д, то вершина, відповідна завданню А (О, х, у), є тупиковою.

Програма GPS по суті може настроюватися програмною оболонкою, здатної вирішувати різнотипні завдання, такі, наприклад, як синтаксичний розбір пропозицій, символьне інтегрування, доведення теорем і т. Д. Налаштування програми GPS на вирішення конкретного завдання здійснюється завданням Загальним вирішувач завдань (програмі GPS) вихідного об'єкта /, кінцевого об'єкта Е, операторів перетворення об'єктів Про |, 0 ₂ , ..., 0, ", а також, якщо можливо, таблиці залежностей операторів О, та конкретних видів відмінностей (властивостей Dj). Таблиця залежностей служить для прискорення пошуку операторів, що зменшують відмінність, і містить для кожного оператора вказівки на ті відмінності, які можуть бути зменшені, якщо застосовується відповідний оператор. Таблиця залежностей може бути задана в наступній формі.

Таблиця 1

Таблиця залежностей

Тут для операторів Про _і 0 ₂ , 0, " знаком х позначені саме ті конкретні види відмінностей (властивості? *,), Які зменшуються, якщо застосовується відповідний оператор.