![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В мережі, що задається графом (I, U), де I – множина вершин, U – множина дуг з визначеною на ній функцією вартості cij ((i,j) –дуга з U), для фіксованих i1 та is знайти шлях
L = ((i1, i2),(i2, i3),...,(is-1, is))
з вершини i1 у вершину is, довжина якого
найменша.
Алгоритм методу Мiнтi. Методом Мiнтi розв’язується задача побудови дерева найкоротших шляхів в мережі з коренем у фіксованій вершині i1.
Алгоритм складається із скiнченного числа кроків, на кожному з яких позначаються вершини мережі i виділяються деякі її дуги.
Нехай P r – множина вершин, позначених на кроцi r, а I r – множина вершин, позначених за r кроків.
Крок 0. Корiнь дерева (вершина i1) позначається сталою величиною h1= 0; i1 (h1)= i1 (0). Пiсля нульового кроку P 0 ={ i1 (0)}, I 0 ={ i1 (0)}.
Нехай виконано r кроків, при яких побудована множина
I r ={ i1 (0),..., ik (hk),...}
позначених вершин ik (hk), кожній з яких поставлене у відповідність число hk (чисельно рівне довжині найкоротшого шляху із вершини i1 у вершину ik).
Крок r +1. Будується переріз мережі, який породжується множиною позначених вершин I r i визначається множина J r ={..., im,...} непозначених вершин im мережі, в які заходять дуги перерізу. Для кожної дуги (ik, im) перерізу обчислюють суму hk + i позначають ті з дуг, для яких ця сума мінімальна. Потім, виділяють позначені дуги так, щоб в кожну непозначену вершину множини J r, в яку заходять позначені дуги перерізу, заходила б тільки одна виділена дуга. Пiсля виділення дуг позначають вершини – кінці виділених дуг. Величина позначки рівна мінімальній із сум hk +
, обчислених для всіх дуг перерізу. Об’єднуючи множину I r з множиною P r+1 вершин, позначених на (r+1) – у кроцi, отримують множину I r+1 вершин, позначених за (r+1) кроків. Переходять до наступного кроку, якщо існує розріз, що породжується множиною I r+1.
Описаний процес продовжують до тих пір, поки можливе розширення множини позначених вершин. Якщо деяка вершина in мережі залишилась непозначеною після закінчення процедури Мiнтi, то шляху, що починається у вершині i1 i закінчується у вершині in, не існує.
Дата публикования: 2015-09-18; Прочитано: 339 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!