Моделі і методи прийняття рішень (стр. 3 из 3)

g*(n) – оцінка довжини найкоротшого шляху між від початкової вершини до n-ї;

h*(n) – евристична функція, яка задає оцінку довжини найкоротшого шляху між від n-ї вершини до цільової;

f*(n)=g*(n)+h*(n) - оцінка f(n);

L(n) - множина всіх наступників вершини n.

Введемо робочі множини: OPEN I CLOSE.

Загальна схема пошуку найкоротшого шляху:

1. Сформувати шраф пошукуG, який спочатку складається з початкової вершини s. Занести sдо OPEN.Прокласти g*(s)=g(s)=0.

2. Сформувати множину CLOSE, яка спочатку буде порожня.

3. Якщо множинаOPENпорожня, то вихід – потрібного шляху не існує;

4. Взяти з множини OPENперший елемент m(відповідно до порядку, встановленого кроком 9), вилучити m зOPEN та занести її до CLOSE.

5. Якщоm - цільова вершина, то успіх. Відновити шлях від sдоm на основі відновлюючи вказівників, що встановлені на кроках 6-8 і завершити алгоритм.

6. Розкрити вершину m, отримати множину наступників L(m). Додати до графуG всі вершини, які належать L(m), але не належать G, разом з відповідними дугами. Додати ці вершини до OPEN. Для кожної вершини

обчислити оцінки f*(k)=g*(k)+h*(k), поклавши g*(k)=g*(m)+c(m,k), встановити з k до m відновлюючий вказівник;

7. Для кожної вершини nз тих, які потрапили до L(m), але вже належали OPENабо CLOSE, переобчислити оцінки g*(n)=min((g*(m)+c(m,n), g*(n)). Якщо оцінка зменшилася, то перевстановити з неї відновлюючийвказівник до m.

8. Для всіх вершин з L(m), які до цього знаходилися в CLOSE, перевстановити відновлюючи вказівними для кожного з наступників цих вершин у напрямі найкоротшого шляху.

9. Перевпорядкувати множину OPENза зростанням значень f*.

10. Повернутися на крок 3.

Якщо евристична функція не використовується, тобто h*(n)=0 і f*(n)=g*(n), то отримується алгоритм Дейкстри.

Якщо взяти g*(n)=0, утворюється алгоритм Дорана і Мічі.

4.1 Планування в просторі задач. І-АБО граф

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

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

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

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

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;