Page 62 - 6103

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

63