ПЕРШИЙ СПОСІБ ФОРМАЛІЗАЦІЇ ЗАДАЧ

Елементи х предметної області X розглядаються як стану деякого, можливо абстрактного, об'єкта. Серед усіх станів з безлічі X виділяються два види станів: одні називають початковими станами х _поч , інші - кінцевими , або цільовими , станами х _кін . Решта стану грають роль проміжних станів.

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

Сенс завдання при такому її формалізованому поданні полягає в тому, щоб перевести об'єкт з заданого початкового стану х _іач в одне з кінцевих станів х _кін , використовуючи тільки дозволені операції Про _ь 0 ₂ , ..., Про _п . Коли кінцеві (цільові) стану неможливо заздалегідь вказати явно, як у випадку з грою в шахи або го, задаються цільові умови. Це - умови, однозначно визначають, які стану слід вважати кінцевими. Роль цих умов в шахах грають ті положення Правил гри в шахи, в яких описуються ситуації закінчення гри: мат, пат, вічний шах і ін.

Відповідна завдання в замкнутій формі, т. Е. Завдання, формалізована першим способом, видається тепер так: знайти таку послідовність

дозволених операцій Про ,, Про _ь ..., 0 ", що переводять об'єкт з заданого початкового станах ,, ^ водно з кінцевих станів х _{КО | 1} . Або, якщо кінцеві стану не задані явно, зазначена послідовність дозволених операцій повинна переводити об'єкт з заданого початкового стану х _поч в стан, що задовольняє цільовим умовам.

Як приклад такого способу подання (формалізації) завдання розглянемо гру «П'ятнадцять». Є квадратне ігрове поле розміром 4x4

і 15 квадратних фішок, пронумерованих числами від одного до п'ятнадцяти

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

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

У цьому завданні зручно переміщення пронумерованих клітин інтерпретувати як переміщення порожньої клітки

Так що дозволених операцій виявляється всього чотири: рух порожньої клітки вправо, вліво, вниз і вгору. Позначимо ці операції R, L, D, U відповідно. У формалізованому вигляді постановка задачі тепер має наступний вигляд: знайти таку послідовність

операцій R, L, D, U руху порожньої клітки, що переводять стан х _поч в кінцевий стан х _вряди .

Таким чином, при першому способі формалізації завдання повинні бути задані:

• 1) безліч Р всіх станів, яке називають простором станів ', в ньому має бути зазначено початковий стан;
• 2) безліч всіх дозволених операцій Про ,, 0 ₂ , ..., 0 " над станами;
• 3) безліч всіх кінцевих станів ; при неможливості задати ці стани явно задаються умови, однозначно характеризують цільові стану - цільові умови.