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

Теорема. У графі існує ейлерів шлях тільки тоді, коли граф зв’язний і містить не більше двох вершин непарного ступеня.

Знаходження найкоротших шляхів у графі

Потрібно знайти мінімальний шлях (контур) у навантаженому графі, де d(u,v) - відстань між вершинами u і v, якщо не існує шляху, то d(u,v)=.

4. Загальна схема алгоритму Харта, Нельсона і Рафаеля

Узагальненням алгоритмів пошуку найкоротшого шляху на графах є алгоритм Харта, Нельсона і Рафаеля.

Введемо такі позначення:

s - початкова вершина;

q - цільова вершина;

c(i,j) - довжина ребра між вершинами і та j;

d(i, j) - довжина найкоротшого шляху між і-ю та j-ю вершинами;

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

h(n) - довжина найкоротшого шляху між від n-ї вершини до цільової;

f(n) - довжина найкоротшого шляху між від початкової вершини до цільової, які проходять через вершину n, при цьому f(n)=g(n)+h(n);

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), то отримується алгоритм Дейкстри.