Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


«адача побудови найкоротших к≥льцевих маршрут≥в м≥ж вузлами мереж≥ перевезень пошти




 ≥льцев≥ маршрути використовуютьс€ €к маршрути обм≥нюванн€ пошти м≥ж окружними вузлами звТ€зку ≥ п≥дпор€дкованими њм в≥дд≥ленн€ми звТ€зку, маршрути м≥ськоњ службовоњ пошти, маршрути вийманн€ лист≥в з поштових скриньок, маршрути розвезенн€ письмовоњ кореспонденц≥њ та газет в≥д доставних в≥дд≥лень звТ€зку до опорних пункт≥в.

«адача формулюЇтьс€ так: побудувати найкоротший к≥льцевий маршрут, що розпочинаЇтьс€ ≥ зак≥нчуЇтьс€ у де€кому центральному вузл≥ та, €к найменше, один раз проходить через кожний з решти вузл≥в мереж≥.

—формульована задача називаЇтьс€ задачею ком≥во€жера ≥ маЇ надто складне розвТ€занн€.

јлгоритм, €кий забезпечуЇ знаходженн€ оптимального або достатньо близького до оптимального р≥шенн€, в терм≥нах теор≥њ граф≥в пол€гаЇ в побудов≥ найкоротших рад≥альних маршрут≥в м≥ж центральною вершиною графа ≥ рештою його вершин та посл≥довному обТЇднанн≥ рад≥альних маршрут≥в в к≥льцевий маршрут.

јлгоритм заснований на тому, що дв≥ дов≥льн≥ вершини графа r та s, розташован≥ на в≥дстан€х Lkr та Lks в≥д центральноњ вершини k ≥ на в≥дстан≥ Lrs одна в≥д одноњ, при використанн≥ рад≥альних маршрут≥в k Ц r Ц k та k Ц s Ц k обумовлюють њх загальну прот€жн≥сть 2 Lkr + 2 Lks, а при використанн≥ к≥льцевого маршруту k Ц r Ц s Ц k Ц загальну прот€жн≥сть Lkr + Lks + Lrs.

–≥зниц€ м≥ж зазначеними загальними прот€жност€ми Lkr + Lks - Lrs визначаЇ величину, на €ку скорочуЇтьс€ загальна прот€жн≥сть поштових маршрут≥в при обТЇднанн≥ рад≥альних маршрут≥в в к≥льцевий маршрут.

ќск≥льки Lkr + Lks - Lrs ³ 0 (р≥вн≥сть маЇ м≥сце, коли найкоротший шл€х м≥ж вершинами r та s проходить через центральну вершину k), прот€жн≥сть обТЇднаного к≥льцевого маршруту н≥коли не перевищуЇ загальноњ прот€жност≥ рад≥альних маршрут≥в, з €ких в≥н складаЇтьс€.

ѕри обТЇднанн≥ двох рад≥альних маршрут≥в в к≥льцевий маршрут в €кост≥ вершин r та s виступають к≥нцев≥ вершини рад≥альних маршрут≥в.

ѕри обТЇднанн≥ рад≥ального ≥ к≥льцевого маршрут≥в в €кост≥ вершини r виступаЇ к≥нцева вершина рад≥ального маршруту, а в €кост≥ вершини s Ц перша п≥сл€ центральноњ або останн€ перед нею за напр€мом руху вершина к≥льцевого маршруту.

ѕри обТЇднанн≥ двох к≥льцевих маршрут≥в в €кост≥ вершин r та s виступають перш≥ або останн≥ за напр€мами руху вершини к≥льцевих маршрут≥в.

Ќа рис. 2.7 наведено ≥люстрац≥ю обТЇднанн€ рад≥альних та к≥льцевих поштових маршрут≥в (верхн≥й р€д Ц початков≥ маршрути, нижн≥й Ц обТЇднан≥ к≥льцев≥ маршрути).

 

r s r s r s

                   
 
   
     
     
       
 
 
 
 


q p q

           
   
   
 


k k k

 

r s r s r s

           
   
 
   
 
 


q p q

           
   
   
 


k k k

 

¬ар≥ант 1 ¬ар≥ант 2 ¬ар≥ант 3

 

–исунок 2.7. ќбТЇднанн€ рад≥альних та к≥льцевих поштових маршрут≥в

” першому вар≥ант≥ прот€жност≥ Lkr та Lks входили у загальну прот€жн≥сть обох рад≥альних маршрут≥в по два рази (в пр€мому та в зворотному напр€м≥), отже у прот€жн≥сть обТЇднаного к≥льцевого маршруту вони ув≥йдуть по одному разу, внасл≥док чого обТЇднаний к≥льцевий маршрут прийме вид

k Ц r Ц s Ц k.

” другому вар≥ант≥ прот€жн≥сть Lkr входила у загальну прот€жн≥сть обох маршрут≥в два рази, а прот€жн≥сть Lks Ц один раз, отже у прот€жн≥сть обТЇднаного к≥льцевого маршруту прот€жн≥сть Lkr ув≥йде один раз, а прот€жн≥сть Lks Ц не ув≥йде жодного разу, внасл≥док чого обТЇднаний к≥льцевий маршрут прийме вид k Ц r Ц s Ц q Ц k.

” третьому вар≥ант≥ прот€жност≥ Lkr та Lks входили у загальну прот€жн≥сть обох к≥льцевих маршрут≥в по одному разу, отже у прот€жн≥сть обТЇднаного к≥льцевого маршруту вони не ув≥йдуть жодного разу, внасл≥док чого обТЇднаний к≥льцевий маршрут прийме вид k Ц p Ц r Ц s Ц q Ц k.

ѕ≥дкреслимо, що визначена прот€жн≥сть обТЇднаного к≥льцевого маршруту не залежить в≥д того, €к фактично проходить найкоротший шл€х м≥ж вершинами r та s.

якщо, наприклад, у третьому вар≥ант≥ найкоротший шл€х м≥ж вершинами r та s проходить через вершини p та q, то загальна прот€жн≥сть обТЇднаного к≥льцевого маршруту скоротитьс€ на Lkr + Lks ≥ зб≥льшитьс€ на Lrs, тобто на Lrp + Lpq + Lqs, внасл≥док чого прот€жност≥ д≥л€нок Lrp та Lqs ув≥йдуть в обТЇднаний к≥льцевий маршрут по два рази, а обТЇднаний к≥льцевий маршрут прийме вид k Ц p Ц r Ц p Ц q Ц s Ц q Ц k.

ƒл€ дос€гненн€ найб≥льшого скороченн€ прот€жностей к≥льцевих маршрут≥в доц≥льно обТЇднувати т≥ окрем≥ маршрути, у €ких розташуванн€ вершин r та s забезпечуЇ максимальне значенн€ величини Lkr + Lks - Lrs.

як обмеженн€ при обТЇднанн≥ поштових маршрут≥в виступають час проходженн€ обТЇднаного к≥льцевого маршруту (з урахуванн€м часу, що витрачаЇтьс€ на обм≥нюванн€ пошти в пром≥жних вузлах маршруту) ≥ вантажоп≥дйомн≥сть транспортного засобу, що використовуЇтьс€ дл€ перевезень пошти на цьому маршрут≥.

¬насл≥док зазначених обмежень дл€ сполученн€ вузл≥в мереж≥ можуть використовуватис€ не один, а дек≥лька к≥льцевих маршрут≥в, на кожному з €ких зазначен≥ обмеженн€ виконуютьс€.

јлгоритм обТЇднанн€ рад≥альних маршрут≥в в к≥льцевий заснований на посл≥довному формуванн≥ фрагмент≥в, що €вл€ють собою частини обТЇднаного к≥льцевого маршруту.

¬ кожному фрагмент≥ розгл€даютьс€ три типи вершин:

- центральна вершина, з €коњ розпочинаЇтьс€ ≥ €кою зак≥нчуЇтьс€ к≥льцевий маршрут;

- активн≥ вершини, в €кост≥ €ких виступають перша п≥сл€ центральноњ вершини ≥ останн€ перед нею за напр€мом руху вершини к≥льцевого маршруту;

- пасивн≥ вершини, в €кост≥ €ких виступають вершини, розташован≥ м≥ж активними вершинами к≥льцевих маршрут≥в.

¬ €кост≥ перев≥рних вершин виступають пари к≥нцевих вершин рад≥альних маршрут≥в.

” залежност≥ в≥д сп≥вв≥дношенн€ перев≥рних вершин ≥ вершин ран≥ше сформованих фрагмент≥в к≥льцевого обТЇднаного маршруту можлив≥ 4 випадки.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 426 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћюди избавились бы от половины своих непри€тностей, если бы договорились о значении слов. © –ене ƒекарт
==> читать все изречени€...

2266 - | 2071 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.016 с.