Реферат: Моделі і методи прийняття рішень

Планування в просторі задач полягає в розбитті задачі на підзадачі, поки під задача не зведеться до елементарної (для якої існує готовий алгоритм розв’язку).

Для планування в просторі задач втрадиційно використовують І-АБО графи.

І-АБО графом називають орієнтований граф, вершини якого відповідають задачам, а дуги – відношенням між задачами (І - АБО).

І-АБО графи фактично є фрагментами мереж виведення продукційних систем. Розглянемо продукцій ну систему

A → C

B → C

D, C → G

Для такої системи існує І-АБО граф

Рис.15.1. І-АБО граф

Вершина Cпов’язана з вершинами AiBвідношеннямАБО (достатньо виконання однієї підзадачі), а вершина Gпов’язана з вершинами DiCвідношенням І (необхідне виконання всіх підзадач).

4.2 Метод „Поділяй і пануй”

Нехай потрібно вирішити задачу для елементів масиву початкових даних від pдо q.

Метод „поділяй і пануй”, або поділ на підзадачі, можна записати у вигляді рекурсивної процедури SubTask.

Булeва функція Small(p, q) визначає, чи не зведена під задача до елементарної. Якщо задача елементарна, то знаходиться її розв’язок за допомогою функції G(p,q).

Якщо задача не елементарна, то вона ділиться на дві частини функцією Divide(p,q). Процедура Combine рекурсивно викликає на виконання процедуру SubTask, але для меншої розмірності вхідних даних. Процес рекурсивно продовжується до тих пір, поки всі задачі не будуть зведені до елементарних.

procedure SubTask(p, q:integer);

Var m:integer;

Begin

if Small(p, q) then G(p,q);

else

begin

m:=Divide(p,q); { p <= m < q }

Combine (SubTask(p,m), SubTask(m+1,q));

end;

End;