ГРАФІЧНЕ ПРЕДСТАВЛЕННЯ ПРОСТОРУ СТАНІВ

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

Уявімо простір станів у вигляді орієнтованості графа наступним способом. Вважаємо, що вершини графа відповідають станам з безлічі X, а ребра графа відповідають дозволеним операціями з заданого кінцевого набору {Про ,, Про _ь ..., Про ,,}. Ребро графа направляємо з вершини U в вершину V, якщо серед дозволених операцій переходу є така, яка переводить стан U в стан V. Тоді рішення вихідної завдання зводиться до побудови на графі, який представляє простір станів, шляху, що веде з початкової вершини А в одну з кінцевих вершин Z. Такий шлях називається вирішальним шляхом.

Для ілюстрації уявлення завдання, формалізовані першим способом, у вигляді орієнтованого графа розглянемо гру «Вісім». Вона повністю аналогічна грі «П'ятнадцять». Гра «Вісім» має квадратний ігрове поле розміром 3x3

і 8 квадратних фішок, пронумерованих числами від одного до восьми

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

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

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

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

Під станом в цьому завданні будемо розуміти матрицю розмірності 3x3. Її елементами можуть бути тільки цифри 0, 1,2, 3, 4, 5, 6, 7, 8. Всі елементи різні. Цифра 0 відповідає порожній позиції ігрового поля, інші розташовуються в матриці відповідно фішках з тими ж номерами. Так що руху порожньої клітки на ігровому полі відповідає таке ж рух цифри 0 в матриці: вона просто змінюється місцями з тією чи іншою цифрою. У формалізованому вигляді постановка задачі тепер має наступний вигляд: знайти таку послідовність

операцій / ?, L, D, (/ руху цифри 0, переводять початковий стан в кінцевий стан

Фрагмент орієнтованого графа, що представляє простір станів в даній задачі, наведено на рис. 1. На цьому фрагменті графа простору станів гри «Вісім» можна побачити вирішальний шлях, що веде з початкового стану в кінцевий стан. Цей шлях складається з виділених дуг графа.