Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Розглянемо мережу, що визначається графом 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. Дуги bij мають обмежену пропускну здібність.

 

, (3.1)

 

де fij – можливий потік через гілку bij;

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

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

 

, (3.2)

 

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

 

, (3.3)

 

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

 

де gi, gj – кількість одиниць потоку.

 

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

Вузли помічаються послідовно від 1 до n.

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

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

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

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

 

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

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

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

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

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

Приклад 3. Дан граф

 

 

 

 

1 ітерація. Шлях: 1-3-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =2

 

 

 

2 ітерація. Шлях: 1-2-3-4-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

 

 

 

3 ітерація. Шлях: 1-2-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

 

 

4 ітерація. Шлях: 1-3-2-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

 

 

 

5 ітерація. Шлях: 1-4-5

Помітки:

Потоки в гілках:

Загальний потік збільшився на =1

 

 

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

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

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







Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...





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


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.