Рішення задач методом пошуку в просторі станів

Методи рішення задач

Функціонування багатьох ІС носить цілеспрямований характер (прикладом можуть служити автономні інтелектуальні роботи). Типовим актом такого функціонування є рішення задачі планування шляхів досягнення потрібної мети з деякої фіксованої початкової ситуації. Результатом рішення задачі повинен бути план дій із сукупності дій. Такий план нагадує сценарій, у якому в якості відносин між вершинами виступають відносини типу: "ціль – підціль" "цілі – дія", "дія – результат" і т.п. Будь-який шлях у цьому сценарії, що веде від вершини, яка відповідає поточній ситуації, у кожну із цільових вершин, визначає план дій.

Пошук плану дій виникає в ІС лише тоді, коли вона зіштовхується з нестандартною ситуацією, для якої немає заздалегідь відомого набору дій, який приводять до потрібної мети. Всі задачі побудови плану дій можна розбити на два типи, яким відповідають різні моделі: планування в просторі станів (SS-проблема) і планування в просторі задач (PR-проблема).

У першому випадку вважається заданим деякий простір станів. Опис станів включає стан зовнішнього світу і стан ІС, які характеризуються рядом параметрів. Стани утворять деякі узагальнені стани, а дії ІС або зміни в зовнішньому середовищі приводять до зміни актуалізованих у цей момент станів. Серед узагальнених станів виділені початкові стани (як правило, один) і кінцеві (цільові) стани. SS-проблема полягає в пошуку шляху, який веде з початкового стану в один з кінцевих. Якщо, наприклад, ІС призначена для гри в шахи, то узагальненими станами будуть позиції, які є на шахівниці. В якості початкового стану може розглядатися позиція, яка зафіксована в даний момент гри, а в якості цільової позиції – множина нічийних позицій. Відзначимо, що у випадку шахів пряме перерахування цільових позицій неможливе. Матові й нічийні позиції описані мовою, відмінною від мови опису станів, що характеризуються розташуванням фігур на полях дошки. Саме це ускладнює пошук плану дій у шаховій грі.

При плануванні в просторі задач ситуація трохи інша. Простір утвориться в результаті введення на множині задач відносин типу: "частина – ціле", "задача – підзадача", "загальний випадок – окремий випадок" і т.п. Інакше кажучи, простір задач відбиває декомпозицію задач на підзадачі (цілі на підцілі). PR-проблема полягає в пошуку декомпозиції вихідної задачі на підзадачі, що приводить до задач, рішення яких системі відомо. Наприклад, ІС відомо, як обчислюються значення sin(x) і cos(x) для будь-якого значення аргументу і як здійснюється операція розподілу. Якщо ІС необхідно обчислити tg(x), то рішенням PR-проблеми буде подання цієї задачі у вигляді декомпозиції tg(x)=sin(x)/cos(x) (крім х=π/2+kπ).

Рішення задач методом пошуку в просторі станів

Подання задач у просторі станів припускає подання ряду описів: станів, множини операторів і їхніх впливів на переходи між станами, цільових станів. Описи станів можуть являти собою рядки символів, вектори, двовимірні масиви, дерева, списки і т.п. Оператори переводять один стан в інший. Іноді вони подаються у вигляді продукцій A => B, які означають, що стан А перетвориться в стан В.

Простір станів можна подати як граф, вершини якого позначені станами, а дуги – операторами. Таким чином, проблема пошуку рішення задачі < А, В > при плануванні за станами подається як проблема пошуку на графі шляху з А в В. Як правило графи не задаються, а генеруються в міру потреби.

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

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

Алгоритми пошуку шляху на графі розрізняються також напрямком пошуку. Існують прямі, зворотні й двонаправлені методи пошуку. Прямий пошук іде від вихідного стану і, як правило, використовується тоді, коли цільовий стан заданий неявно. Зворотний пошук іде від цільового стану і використовується тоді, коли вихідний стан заданий неявно, а цільовий – явно. Двонаправлений пошук вимагає задовільного рішення двох проблем: зміни напрямку пошуку й оптимізації "точки зустрічі". Одним із критеріїв для рішення першої проблеми є порівняння "ширини" пошуку в обох напрямках – вибирається той напрямок, який звужує пошук. Друга проблема викликана тим, що прямий і зворотний шляхи можуть розійтися і чим вужчий пошук, тим це більш імовірно.