|
Постановка задачі про найкоротший шлях. Алгоритм методу Мінті.Розглянемо мережу, що визначається графом 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 мають обмежену пропускну здібність.
де fij – можливий потік через гілку bij; Uij – задане значення пропускної здібності для гілки bij. Величина потоку з джерела не обмежена і в кожному проміжному вузлі виконується умова збереження потоку.
Задача складається у визначенні дугових потоків fij таких, щоб загальний потік з джерела s в стік t був максимальним:
Задача вирішується за допомогою ітераційної процедури розстановки поміток вузлів. Кожна помітка вказує величину потоку та його джерело, і може бути як позитивною, так і негативною.
де 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 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|