Постановка задачі про найкоротший шлях. Алгоритм методу Мінті.

Розглянемо мережу, що визначається графом g,з означеною на U функцією вартістю Cij, на цій мережі розглянемо також дві фіксовані вершини і1, іs, та довільний шлях,що з’єднує дві точкі (точкі вершини).

I=I(i1,is)=((i1,is),(i2,i3)…(i5-1,is))(3); Розглянемо функцію Ci=

(4),яка інтерпретується або як собі вартість перевезення вантажу по шляху І або, як довжину шляху І, яка інтерпретується.

Задача про найкоротший шлях:Полягає в пошуку шляху (3), що мінімізує цільову функцію(4).Шуканий шлях I*=argminC(I) називається найкоротшим(оптимальним). З формальноної точки зору задача про мінімальний шлях є частковим випадком задачі про оптимальний потік. Для цього розглядається мережа, вершина і1, якої є джерелом одиничної інтенсивності, вершина іs є стоком одиничної інтенсивності, а решта вершин нейтральна. Для розв’язання задачі про найкоротший шлях розроблена значна кількість методів, що дозволяють її розв’язати та враховують її специфіку та одним з таких методів є метод Мінті(метод позначок). Згідно цього методу процес розв’язання задачі складається із скінченного числа елементарних кроків на кожному з яких позначаються вершини в мережі та виділяються деякі, її дуги.

Крок 1:Позначається вершина і1(коренева вершина)позначкою hi(1)=0, тоді I(1)={I1} записуємо множину позначених вершин. Нехай після виконання r кроків, ми отримали множину. I(r)={i1,…i2,….}позначених вершин з індексом і(ᶋ), кожні з яких поставлена у відповідність позначка hi(ᶋ).

Крок ṛ+1: Розглянемо множину J(n)={….,iµ,..} непозначених вершин іµ, (іᶋ, іµ) є U, iᶋє І(ṛ), Іµ є J(ṛ), I(ṛ)∩j (r)=0⁄, для кожної з таких дуг знаходимо суму hiᶋ+Ciᶋ*iµ. Виділяємо ті дуги для яких ця сума мінімальна, при чому з декількох дуг, що підлягають виділенню і закінчуються в одній і тій же вершині виділяється лише одна.Позначаємо кінці виділення дуг числом, що = minзначенню hiᶋ+Ciᶋ*iµ; За рахунок позначених вершин, множина I(r)розширюється до множини І(ṛ+1). За побудовою кожній з позначених вершин (окрім кореневої) закінчується одна виділена дуга.Тому рух від вершин Іsвздовж виділених дуг у напрямку протилежному їх орієнтації реалізується однозначно.

ТЕОРЕМА: Побудований Мінті шлях, що з’єднує вершини і1,іsє найкоротшим,при чому C(I*(i1,is))=his.

1)Сформульований вище алгоритм методу Мінті розрахований на знаходження єдиного найкоротшого шляху, що з’єднує вершини і1,іs, щоб знайти всю множину найкоротших шляхів на кожному кроці слід виділяти всі дуги з мінімальним показником. Навіть якщо декілька з них закінчується в одній і тій же вершині, а при зворотньому русі з вершини іs, вздовж виділених дуг у кожній з вершин слід розглядати всі можливі продовження.

2) Насправді метод Мінті розв’язує більш загальну задачу: Він знаходив найкоротший шлях з кореневої в кожну з позначених вершин.

3) Якщо процес позначення вершин методом Мінті продовжувати до тих пір, поки не припинеться розширення множини позначених вершин, то буде розв’язана задача знаходження найкоротшого шляху з початкової вершини і1 у кожну позначену. Якщо при цьому деяка вершина мережі непопала до числа позначення, то не існує шляху з кореневої вершини в цю вершину.

Дан граф

, де А − множина вузлів, В − множина дуг. Граф G має одне джерело s і один стік t. Дуги b_ij мають обмежену пропускну здібність.

U_ij – задане значення пропускної здібності для гілки b_ij.

Величина потоку з джерела не обмежена і в кожному проміжному вузлі виконується умова збереження потоку.

Задача складається у визначенні дугових потоків f_ij таких, щоб загальний потік з джерела s в стік t був максимальним:

Задача вирішується за допомогою ітераційної процедури розстановки поміток вузлів. Кожна помітка вказує величину потоку та його джерело, і може бути як позитивною, так і негативною.

Позитивна помітка збільшує потік по гілці b_ij, але так, щоб сумарний потік не перевищував U_ij; негативна помітка зменшує потік по гілці b_ij, але так, щоб він не став від’ємним.

Якщо вузол a_i помічений, то a_j можна помітити з нього по прямій гілці на величину не більшу, за

, а по зворотній гілці на величину

На кожній ітерації джерело помічається міткою

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

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

Потім всі мітки стираються і переходять до наступної ітерації.

Алгоритм закінчує роботу, якщо жоден вузол мережі вже не може бути поміченим.

Теорема про максимальний потік і мінімальний розріз. Нехай буде заданий граф

. Розіб’ємо множину А на дві непересічні підмножини

, так щоб джерело і стік графа не знаходились в одної підмножині. Все дуги, що з’єднують ці дві підмножини, утворюють множину

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

і є перетин.

Кількість дуг в перетині називається рангом перетину, а сумарна пропускна здібність всіх дуг перетину – розрізом.

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

Практичне значення даної теореми наступне: послідовно перебираючи всі розрізи, що розділяють джерело і стік, і обираючи мінімальний з них, можна визначити максимальний потік. Однак, визначити дугові потоки дана теорема не дозволяє. Ця теорема корисна для аналізу вузьких місць в мережі.

6 ітерація. Ще будь-який шлях вибрати неможливо.

Максимальний потік в мережі, поданий графом, що розглядається, дорівнює сумі приростів потоків

на кожній ітерації, тобто V = 6.

В даному прикладі можна визначити максимальний потік, використовуючи теорему про максимальний потік і мінімальний розріз, яким являється розріз

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: