Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

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

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

Мал. 1

Простір подзадач можна представити графічно у вигляді І-АБО дерева наступним способом. Вважаємо, що вершини графа відповідають підзадач з простору подзадач X, а ребра графа відповідають правилам декомпозиції, що обирається з заданого кінцевого набору {Я ,, Я ,, ..., Я "}. Кореневої вершиною (в неї не входить жодне ребро графа) є вершина, відповідна вихідної задачі. Висячими вершинами, «листям», графа (т. Е. Вершин, з яких немає вихідних ребер графа) будуть тупикові вершини або вершини, відповідні примітивним підзадач. Якщо поточна вершина відповідає завданню Р 0 і є правило декомпозиції, яке зводить рішення задачі Р 0 до вирішення підзадач Р ] чР ь ..., Р П9 то з поточної вершини / ^ виходить п спрямованих ребер: по одному ребру до кожної зі згаданих подзадач Р ] 9 Р ь ..., Р, г

Ребра стягуються у вершини Р {) загальною суцільною лінією, якщо для вирішення завдання Р 0 потрібно вирішити всі завдання P l9 Р ь Р п (рис. 2, а). Вершина Р 0 в цьому випадку називається І-вершиною.

Мал. 2

Якщо для вирішення завдання / ^ досить вирішити тільки одну з задач Р ь Р 2 , ..., Р, " то ребра стягуються загальної пунктирною лінією або взагалі не стягуються загальною лінією (див. Рис. 2, б або рис. 2, в ). Вершина Р 0 в цьому випадку називається АБО-вершиною.

Ребро графа направляємо з вершини / *, в вершину Р 2 , якщо є правило декомпозиції, яке зводить рішення задачі Р, до вирішення однієї підзадачі Р 2 (див. Рис. 2, г). Вершину Р, в цьому випадку будемо відносити до Я-вершин.

При побудові графа простору подзадач можуть виникати висячі вершини, «листя», з яких не виходить жодного ребра. Серед них є тупикові вершини, т. Е. Висячі вершини, з яких не виходить жодного ребра через відсутність правил декомпозиції для задач, які відповідають цим вершин. Але може бути й інша ситуація, коли з вершини не виходить жодного ребра. Ця ситуація виникає для кінцевих (цільових) вершин, які відповідають примітивним підзадач.

Орієнтований граф називається І-ІЛ І деревом, якщо всі його вершини - це АБО- вершини або // - вершини.

Можуть бути більш складні випадки декомпозиції (див. Рис. 2, д). Тут вершина Р {) не є ні // - вершиною, ні //.////-вершіной. Введення допоміжних // - вершин (?, І Q 2 дозволяє вершину Р 0 перетворити в АБО- вершину (див. Рис. 2, е). Цим забезпечується перетворення графа, що представляє будь-який простір подзадач, в І-АБО дерево, в якому кожна вершина є //.////-вершіной або // - вершиною.

Для І-АБО дерев є великий арсенал алгоритмів побудови вирішальних піддерев. Цим і диктується необхідність в отриманні саме І-АБО дерева, що представляє простір подзадач. Визначимо точніше поняття «вирішальне поддерево».

Почнемо з поняття «здійсненне вершина». Я-вершина називається вирішуваною, якщо всі ребра, що виходять з неї, спрямовані до вирішуваним вершин. АБО- вершина називається вирішуваною, якщо серед всіх ребер, що виходять з неї, є хоча б одне, що приводить до вирішуваною вершині. Вершина, відповідна найпростішої задачі, вважається можливо розв'язати. Тупикова вершина, т. Е. Вершина, з якої не виходить жодного ребра, вважається нерозв'язною. Вирішальним піддерево І-ІЛ І дерева, що представляє простір подзадач, називається підграф цього І-АБО дерева, у якого коренева вершина відповідає вихідній задачі, всі проміжні вершини можна розв'язати і все висячі вершини теж можна розв'язати.

Як приклад уявлення завдання деревом подзадач розглянемо наступну задачу:

обчислити інтеграл

Як правил декомпозиції будемо використовувати:

П | - алгебраїчні підстановки, наприклад: t [1] = 1 - х,

П 2 - тригонометричні підстановки, наприклад: х = sin t,

/ 7, - тригонометричні тотожності, наприклад: tgx = (ctg х) _ | ,

П 4 - розподіл чисельника на знаменник, наприклад:

Я 5 - виділення повного квадрата, наприклад:

П ь - розбиття інтеграла на суму або різницю інтегралів, наприклад:

Мал. 3

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

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

 
<<   ЗМІСТ   >>