Page 113 - 6109

графа.
Існують методики комбінування методів пошуку в просторі станів і в
просторі задач.
Пошук рішень в просторі станів може виконуватися в декількох
напрямах: з початкового стану в цільовий стан (пошук, керований даними); з
цільового стану в початковий стан (пошук, керований метою, або зворотний
пошук); одночасно в двох напрямах (комбінований пошук). Оскільки пошукові
графи (дерева) для практичних задач – великі, то двонаправлений пошук може
бути ефективно однонаправленого.
Пошук рішень в просторі станів – комбінаторна задача. Рішення виходить
на основі перебору всіх станів. Проте для багатьох практичних задач повний
перебір неможливий. Були запропоновані різні заходи для оцінки складності
вирішуваної задачі. Одна з них – це ступінь розгалуження вершин графа стану.
Вона рівна середньому числу дочірніх вершин, що доводяться на один стан
задачі. Якщо розглядати дерево станів, то можна вивести формулу, що
встановлює залежність загального числа станів N від ступеня розгалуження В і
глибини дерева L:
L
N = B (B – 1)/(B – 1)
Наприклад, необхідно підрахувати загальне число станів для гри-
головоломки "8". Вкажемо можливі переміщення фішок:
– по два переміщення з кожного кута, тобто для чотирьох кутів вісім
переміщень;
– по три переміщення з центральних позицій уздовж кожної із сторін,
тобто всього дванадцять переміщень;
– чотири переміщення з центральної позиції.
Загальне число можливих переміщень 24. Розділивши це число на 9
(число різних положень для порожньої ячейки), одержимо ступінь
розгалуження 2,67. Тепер можна визначити загальне число станів при
прогляданні дерева станів глибини L (табл. 2.2).

Таблиця 11.2 – Число станів при грі "у вісім"

I 2 3 4 5 6 7 8 9 10
N 10 29 80 215 577 1545 4127 11024 29436

Як видно з таблиці 11.2, навіть для такої простої задачі кількість станів,
що проглядаються, різко зростає при збільшенні глибини пошуку.
Складність вирішуваної задачі можна також оцінювати розмірами списків
Open і Сlosed. Для того, щоб ці списки не розросталися, можна зберігати в
списку Open тільки декілька "найперспективніших" станів. Це, звичайно,
скорочує простір пошуку, але виникає небезпека пропуску рішення. Такі
стратегії пошуку, що накладають обмеження на розмір списку Open,
відповідають променевому пошуку (Beam Search). Більш безпечні стратегії
евристичного пошуку, розглянуті вище. Чим більше інформованість про
вирішувану задачу, тим більша вага має евристична частина оцінної функції і
тим більше скорочується простір пошуку. Слід звернути увагу на те, що

113