І-АБО граф
Планування в просторі завдань Полягає в розбітті задачі на підзадачі, поки под завдання не зведеться до елементарної (для Якої існує готовий алгоритм розв'язку).
Для планування в просторі завдань втрадіційно Використовують І-АБО графи.
І-АБО графом назівають орієнтований граф, вершини Якого відповідають завданням, а дуги - відношенням между завданнями (І - АБО).
І-АБО графи Фактично є фрагментами мереж Виведення продукційніх систем. Розглянемо продукцій ну систему
A в†’ C
B в†’ C
D, C в†’ G
Для Такої системи існує І-АБО граф
В
рис.15.1. І-АБО граф
Вершина C пов'язана з вершинами A i B відношенням АБО (Достатньо Виконання однієї підзадачі), а вершина G пов'язана з вершинами D i C відношенням І (необхідне Виконання всех підзадач).
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
Combine (SubTask (p, m), SubTask (m +1, q));
end;
End;
