Тема 30. Алгоритми пошуку найкоротших шляхів

30.1. Пошук маршруту у графі

При розв’язанні широкого кола прикладних задач нерідко виникає необхідність знайти маршрут, що зв’язує задані вершини в графі G. Наведемо алгоритм розв’язання такої задачі. В ньому задача зводиться до пошуку маршруту в зв’язаному графі G = (V, E), який з’єднує задані вершини v, u  V, де vu.

Алгоритм Террі знаходження маршруту

У зв’язаному графі завжди можна знайти такий маршрут, що зв’язує дві задані вершини v та u, якщо, виходячи з вершини v і здійснюючи послідовний перехід від кожної досягнутої вершини до суміжної з нею, керуватися такими правилами:

1. йдучи по довільному ребру, кожний раз відмічати напрямок, в якому воно було пройдене;

2. виходячи з деякої вершини v₁, завжди рухатися тільки по тому ребру, яке не було пройдене або було пройдене у зворотному напрямку;

3. для кожної вершини v₁, відмінної від v, відмічати те ребро, яке першим заходить у v₁, якщо вершина v₁, зустрічається вперше;

4. виходячи з деякої вершини v₁, відмінної від v, по першому ребру, яке заходить у v₁, рухатися лише тоді, коли немає інших можливостей.

Обґрунтування алгоритму. Припустимо, що, керуючись цим алгоритмом, зупинимося в деякій вершині w (не досягши вершини u), а всі ребра, інцидентні w, вже пройдено в напрямку з w (тоді внаслідок правила 2 вже не можна вийти з w). Покажемо, що в цьому випадку: а) вершина w збігається з v; б) всі вершини графу G пройдено.

Доведемо спочатку твердження а). Якщо вершина w не збігається з v, то нехай у вершині w ми побували k разів (включаючи останній). Тоді ребра, інцидентні w, були пройдені k разів у напрямку до w, k – 1 разів у напрямку з w (оскільки кількість заходів у w, за винятком останнього, відповідає кількості виходів із цієї вершини). Таким чином, використовуючи те, що за припущенням були пройдені всі ребра, інцидентні вершині w, в напрямку з w, а також те, що з урахуванням правила 2 по кожному ребру, інцидентному w, маємо d(w) = k – 1, а це суперечить тому, що у напрямку до w були пройдені k різних ребер (згідно з правилом 2); отже d(w)  k. Одержана суперечність підтверджує, що w = v.

Доведемо тепер правильність б). Нехай (за твердженням а)): v₁, v₂, …, v_k, де v₁ = v_k = v – послідовність вершин, розташованих у тому самому порядку, в якому ми рухалися, діючи згідно з алгоритмом. Очевидно, ця послідовність є маршрутом у графі G. Покажемо, що цей маршрут містить усі вершини графу G. Спочатку доведемо, що кожне ребро, інцидентне будь-якій вершині v_j, 1  j  k, було пройдене по одному разу в обох напрямках. Доведення проведемо індукцією за кількістю вершин j.

Оскільки в замкненому маршруті для кожної вершини, яка міститься в ньому, кількість виходів з неї дорівнює кількості заходів у неї, внаслідок того, що згідно з твердженням а) і правилом 2 всі ребра, інцидентні вершині v = v₁, були пройдені по одному разу в напрямку з v (тобто ми d(v) разів виходили з v), встановлюємо, що рівно d(v) разів ми заходили у v, а оскільки внаслідок правила 2 кожний такий захід у v здійснювався по новому ребру, всі ребра, інцидентні вершині v = v₁, були пройдені по разу в обох напрямках.

---

Припустимо, що при деякому j, 2  j  k, твердження, яке доводиться, справджується для всіх вершин v₁, …, v_j–1. Доведемо його для вершини v_j. Якщо при деякому i виконується рівність v_i = v_j, то правильність твердження, що доводиться для вершини v_j, випливає з того, що за індуктивним припущенням воно випливає з v_i. Нехай тепер для всіх i{1, 2, …, j–1} v_iv_j, тобто вершина v_i зустрілася вперше. Тоді (v_j–1, v_j) – перше ребро, яке заходить у вершину v_j, за індуктивним припущенням воно буде пройдене в обох напрямках, що з урахуванням правила 4 можливо лише тоді, коли всі інші ребра, інцидентні v_j, будуть пройдені в напрямку з v_j. Далі, оскільки в замкненому маршруті, як уже зазначалося, для кожної вершини, яка міститься в цьому маршруті, кількість виходів із неї дорівнює кількості заходів в неї, використовуючи правило 2, встановлюємо, що всі ребра, інцидентні v_j, будуть пройдені по разу в обох напрямках.

Отже, кожну вершину в маршруті v₁, v₂, …, v_k проходимо разом з усіма суміжними їй вершинами, звідки внаслідок зв’язності графа G випливає, що цей маршрут проходить через усі вершини графу G, а це суперечить початковому припущенню, за яким вершин u не була досягнута. ►

Наведемо приклад використання алгоритму Террі. Необхідно знайти у графі G (рис. 30.1, а) маршрут, який з’єднує вершини v₁ та v₅.

а)	б)

Рис. 30.1. Приклад роботи алгоритму Террі.

Пошук вершини v₅ у G будемо здійснювати так, неначе нічого невідомо про цей граф (це можна порівняти з тим, що G – це лабіринт, v₁ та v₅ – вхід та вихід з лабіринту. На рис. 30.1, б показаний один із можливих варіантів руху по графу G згідно з алгоритмом Террі. Пронумерованими штриховими дугами зображено схему руху по графу G. Ця схема руху відповідає маршруту (v₁, v₂, v₁, v₃, v₄, v₃, v₅). Зазначимо, що після того, як із вершини v₁ зайшли у вершину v₃ (дуга 3), внаслідок правила 4 неможна повернутися у v₁, оскільки існують інші можливості, а (v₁, v₃) є першим ребром, що заходить у v₃. Далі, після того, як із вершини v₄ зайшли у вершину v₃ (дуга 5), внаслідок правила 2 не можна рухатися до вершини v₁, і, таким чином, залишається єдина можливість – рухатися до вершини v₅.

30.2. Пошук відстані між вершинами графу

Розглянемо деякі властивості мінімальних (шляхів) маршрутів.

Означення 30.1. Назвемо образом вершини x в орієнтованому графі G множину кінців дуг, початком яких є вершина x (позначається D(x)), а множину початків дуг, кінцем яких є вершина x, назвемо прообразом вершини х (позначається D^–1(x)).

Зрозуміло, що D(x)  D^–1(x) = Г(x), де Г(x) – множина суміжності вершини x.

Нехай G = (V, E) – орієнтований граф з n вершинами (n  2), а v, u – задані вершини з V, де vu. Опишемо алгоритм пошуку відстані та відповідного їй мінімального шляху з v до u в орієнтованому графі G. Цей алгоритм також має назву хвильового.

Алгоритм (хвильовий)

1. Позначаємо вершину v індексом 0, а вершини, що належать образу вершини v, – індексом 1. Множину вершин з індексом k позначаємо F_k(v). Вважаємо k = 1.

2. Якщо F_k(v) =  або виконується k = n – 1 і uF_k(v), то вершина u є незв’язаною з v і робота алгоритму на цьому завершується. В іншому випадку перейти до пункту 3.

3. Якщо uF_k(v), то переходимо до пункту 4. В іншому випадку існує шлях із v до u завдовжки k, причому цей шлях є мінімальним. Послідовність вершин v, u₁, u₂,…, u_k–1, u, де

---

u_k–1  F_k–1(v)  D^-1(u),

u_k–2  F_k–2(v)  D^-1(u_k–1),

……………..

u₁  F₁(v)  D^-1(u₂),

і є шуканим мінімальним шляхом з v у w. На цьому робота алгоритму завершується.

4. Позначаємо індексом k + 1 всі непозначені вершини, які належать образу множини вершин з індексом k. Множину вершин з індексом k + 1 позначаємо F_k+1(v). Збільшуємо індекс k на 1 і переходимо до пункту 2.

Назва алгоритму – хвильовий – пов’язана з тим, що визначення індексів k вершин графу G відбувається, як розповсюдження з початкової вершини v певної хвилі, яка спрямовується за напрямком дуг. Коли хвиля дійде до кінцевої вершини u, це буде означати, що алгоритм закінчив свою роботу. Значення індексу, „принесеного хвилею”, у вершині u буде відповідати довжині знайденого маршруту. А для того, щоб визначити цей маршрут (послідовність вершин), потрібно з кінцевої вершини u повертатися в зворотному до розповсюдження хвилі напрямку і відзначати послідовно одну довільну вершину зі значеннями індексу k–1, k–2, …, 1, 0. Зрозуміло, що вершина з індексом 0, – це початкова вершина v.

Вершини u₁, u₂, …, u_k–1, взагалі, можуть бути визначені неоднозначно. Ця неоднозначність відповідає випадкам, коли існує кілька різних мінімальних шляхів з v до u в орграфі G.

Наприклад, визначимо мінімальний шлях з v₁ до v₆ в орієнтованому графі G, заданому матрицею суміжності (відповідний граф представлено на рис. 30.2):

	v1	v2	v3	v4	v5	v6
v1	0	0	0	1	1	0
v2	1	0	0	0	0	1
v3	0	1	0	0	0	1
v4	0	1	0	0	1	0
v5	1	0	1	0	0	0
v6	0	0	1	0	1	0

Рис. 30.2. Приклад роботи хвильового алгоритму.

Діючи згідно з хвильовим алгоритмом, послідовно знаходимо F₁(v₁) = {v₄, v₅}; F₂(v₁) = D(F₁(v₁)) \ {v₁, v₄, v₅} = {v₂, v₃}; F₃(v₁) = D(F₂(v₁)) \ {v₁, v₂, v₃, v₄, v₅} = {v₆}. Таким чином, v₆  F₃(v₁), а, отже, за пунктом 3 існує шлях з v₁ до v₆ завдовжки 3, і цей шлях є мінімальним.

Знайдемо тепер мінімальний шлях із v₁ до v₆. Визначимо множину

F₂(v₁)  D^-1(v₆) = {v₂, v₃}  {v₂, v₃} = {v₂, v₃}.

Виберемо будь-яку вершину зі знайденої множини, наприклад, v₃. Визначимо далі множину

F₁(v₁)  D^-1(v₃) = {v₄, v₅}  {v₄, v₅, v₆} = {v₄, v₅}.

Виберемо будь-яку вершину зі знайденої множини, наприклад, v₅. Тоді (v₁, v₅, v₃, v₆) – шуканий мінімальний шлях з v₁ до v₆ в орієнтованому графі G, а відстань між v₁ та v₆ дорівнює 3.

Очевидно, хвильовий алгоритм може застосовуватися не тільки для орієнтованих, а й для неорієнтованих графів. В останньому випадку, пересування з однієї вершини до іншої можливі в обидві сторони.

Хвильовий алгоритм широко застосовується у розробці комп’ютерних ігор – коли необхідно визначити оптимальний маршрут пересування гравця або певного „юніта” з однієї точки віртуальної місцевості (карти) до іншої. Наведемо приклад такої задачі. Нехай потрібно знайти найкоротший маршрут з точки А до точки В на карті, яка зображена на рис. 30.3, а. На ній заштриховані комірки відповідають певним перепонам на шляху, тобто в цих частинах місцевості гравець не зможе пройти. Також будемо вважати, що гравець може пересуватись тільки по вертикалі та горизонталі. Відповідний цієї карті граф представлено на рис. 30.3, б.

---

	а)

б)Рис. 30.3. Приклад карти території та відповідного графу.

Після роботи хвильового алгоритму отримаємо наступні індекси вершин – комірок карти (рис. 30.4, а). На рис. 30.4, б зображено два зі знайдених маршрутів з вершини А у вершину В. Як можна побачити, довжина знайденого маршруту дорівнює 12.

а )

б)Рис. 30.4. Робота хвильового алгоритму для графу на рис. 30.3.

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

Рис. 30.5. Двонаправлений хвильовий алгоритм.

Комірки, де дві хвилі зустрічаються, позначені подвійними лініями. З порівняння рис. 30.4 та 30.5 видно, що знайдені найкоротші маршрути співпадають. І хоча в цьому прикладі економія склала всього лиш одну комірку (яка не була відмічена), можна зрозуміти, що на більш складних, тобто насичених „перепонами”, картах робота модифікованого хвильового алгоритму буде більш ефективнішою за простий хвильовий алгоритм.

30.3. Зважені графи

У реальних задачах на графах часто потрібно брати до уваги додаткову інформацію – фактичну віддаль між окремими пунктами, вартість проїзду, час проїзду тощо. Для цього використовують поняття зваженого графа.

Означення 30.2. Зваженим називають граф, кожному ребру e якого приписано дійсне число w(e). Це число називають вагою ребра e. Аналогічно означають зважений орієнтований граф: це такий орієнтований граф, кожній дузі e якого приписане дійсне число w(e), яке називається вагою дуги.

Розглянемо два способи зберігання зваженого графа G = (V, E) в пам’яті комп’ютера. Нехай |V| = n, |E| = m.

Перший – подання графу матрицею ваг W, яка являє собою аналог матриці суміжності. Її елемент w_ij = w(v_i, v_j), якщо ребро або дуга (v_i, v_j)  E. Якщо ж ребро або дуга (v_i, v_j)  E, то w_ij = 0 чи w_ij =  залежно від розв’язуваної задачі.

Другий спосіб – поданням графу списком ребер. Для зваженого графу під кожний елемент списку E можна відвести три комірки – дві для ребра й одну для його ваги, тобто всього потрібно 3m комірок.

Означення 30.3. Довжиною шляху в зваженому графі називають суму ваг ребер (дуг), які утворюють цей шлях. Якщо граф не зважений, то вагу кожного ребра (кожної дуги) уважають рівною одиниці та отримають раніше введене поняття довжини шляху як кількості ребер (дуг) у ньому.

30.4. Алгоритм Дейкстри

Задача про найкоротший шлях полягає в знаходженні найкоротшого шляху від заданої початкової вершини a до заданої вершини z. Наступні дві задачі – безпосередні узагальнення сформульованої задачі про найкоротший шлях.

---

1. Для заданої початкової вершини a знайти найкоротші шляхи від a до всіх інших вершин.

2. Знайти найкоротші шляхи між усіма парами вершин.

Виявляється що майже всі методи розв’язання задачі про найкоротший шлях від заданої початкової вершини a до заданої вершини z також дають змогу знайти й найкоротші шляхи від вершини a до всіх інших вершин графа. Отже, за їх допомогою можна розв’язати задачу 1 із невеликими додатковими обчислювальними витратами. З іншого боку, задачу 2 можна розв’язати або n разів застосувавши алгоритм задачі 1 із різними початковими вершинами, або один раз застосувавши спеціальний алгоритм.

Найефективніший алгоритм визначення довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої запропонував 1959 р. датський математик Е. Дейкстра. Цей алгоритм застосований лише тоді, коли вага кожного ребра (дуги) додатна. Опишемо докладно цей алгоритм для орієнтованого графа.

Нехай G = (V, E) – зважений орієнтований граф, w(v_i, v_j) – вага дуги (v_i, v_j). Почавши з вершини a, знаходимо віддаль від a до кожної із суміжних із нею вершин. Вибираємо вершину, віддаль від якої до вершини a найменша; нехай це буде вершина v*. Далі знаходимо віддалі від вершини a до кожної вершини суміжної з v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця віддаль менша від поточної, то замінюємо нею поточну віддаль. Знову вибираємо вершину, найближчу до a та не вибрану раніше; повторюємо процес.

Описаний процес зручно виконувати за допомогою присвоювання вершинам міток. Є мітки двох типів: тимчасові та постійні. Вершини з постійними мітками групуються у множину M, яку називають множиною позначених вершин. Решта вершин має тимчасові мітки, і множину таких вершин позначимо як T, T = V \ M. Позначатимемо мітку (тимчасову чи постійну) вершини v як l(v). Значення постійної мітки l(v) дорівнює довжині найкоротшого шляху від вершини a до вершини v, тимчасової – довжині найкоротшого шляху, який проходить лише через вершини з постійними мітками.

Фіксованою початковою вершиною вважаємо вершину a; довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа). Тепер формально опишемо алгоритм Дейкстри.

Алгоритм Дейкстри

1. Присвоювання початкових значень. Виконати l(a) = 0 та вважати цю мітку постійною. Виконати l(v) =  для всіх v  a й уважати ці мітки тимчасовими. Виконати x = a, M = {a}.

2. Оновлення міток. Для кожної вершини v  Г(x) \ M замінити мітки: l(v) = min{ l(v), l(x) + w(x, v) }, тобто оновлювати тимчасові мітки вершин, у які з вершини x іде дуга.

3. Перетворення мітки в постійну. Серед усіх вершин із тимчасовими мітками знайти вершину з мінімальною міткою, тобто знайти вершину v* з умови l(v*) = min{l(v)}, vT, де T = V \ M.

4. Уважати мітку вершини v* постійною й виконати M = M  {v*}; x = v* (вершину v* включено в множину M).

5. а) Для пошуку шляху від a до z: якщо x = z, то l(z) – довжина найкоротшого шляху від a до z, зупинитись; якщо a  z, то перейти до кроку 2.

---

Смотрите также файлы

• 35_Merezhi_ta_potoki.doc

• 37_Gramatiki.doc

• 38_Skinchenni_avtomati.doc

• dinamika.docx

• dinamika_1.docx