Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


¬ипадок 4: збереженн€ ≥снуючих фрагмент≥в




” цьому випадку хоча б одна з перев≥рних вершин Ї пасивною вершиною будь-€кого ран≥ше сформованого фрагмента або обидв≥ перев≥рн≥ вершини Ї активними вершинами де€кого ран≥ше сформованого фрагмента.

ѕроцес перев≥рки вершин r та s провадитьс€ в пор€дку зменшенн€ значень величин Lkr + Lks - Lrs ≥ зак≥нчуЇтьс€ коли вс≥ пари вершин r та s перев≥рен≥, або коли дл€ ус≥х пар вершин r та s, що залишилис€ неперев≥реними, Lkr + Lks - Lrs = 0.

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

јлгоритм побудови найкоротшого к≥льцевого маршруту наведено на рис. 2.8.

јлгоритм м≥стить 11 блок≥в.

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

” блоц≥ 2 виконуЇтьс€ розрахунок значень Lkr + Lks - Lrs дл€ вс≥х пар вершин r та s за значенн€ми найкоротших в≥дстаней, введених у блоц≥ 1. ¬ €кост≥ вершин r та s виступають вс≥ вершини графа, кр≥м центральноњ.

 

 

ѕочаток

 

 
 


1. ”веденн€ значень

найкоротших в≥дстаней

м≥ж вершинами графа

         
   
 
   
 
 


2. –озрахунок значень Lkr + Lks - Lrs

дл€ вс≥х пар вершин r та s

 

3. —ортуванн€ значень Lkr + Lks - Lrs

в пор€дку њх зменшенн€

4. ‘ормуванн€ черговоњ пари

перев≥рних вершин r та s

 
 


5. ѕерев≥рн≥ вершини “ак 6. ‘ормуванн€ нового фрагмента з

в≥дпов≥дають умовам центральноњ вершини ≥ обох

випадку 1 перев≥рних вершин

 

       
 
 
 
 
   


Ќ≥

8. ‘ормуванн€ розширеного

7. ѕерев≥рн≥ вершини “ак фрагмента з ран≥ше

в≥дпов≥дають умовам сформованого фрагмента ≥

випадку 2 другоњ перев≥рноњ вершини

 

 

Ќ≥

 

9. ѕерев≥рн≥ вершини “ак 10. ‘ормуванн€обТЇднаного

в≥дпов≥дають умовам фрагмента з обох ран≥ше

випадку 3 сформованих фрагмент≥в

 

Ќ≥

 

 

Ќ≥ 11. ‘ормуванн€

обТЇднаного к≥льцевого

маршруту зак≥нчено

 

 
 


“ак

 ≥нець

 

–исунок 2.8. јлгоритм побудови к≥льцевого маршруту

 

” блоц≥ 3 провадитьс€ сортуванн€ (упор€дкуванн€) отриманих у блоц≥ 2 значень Lkr + Lks - Lrs в пор€дку њх зменшенн€. –≥вн≥ значенн€ Lkr + Lks - Lrs можуть подаватис€ в дов≥льному пор€дку.

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

” блоц≥ 5 анал≥зуЇтьс€, чи в≥дпов≥дають перев≥рн≥ вершини умовам випадку 1 (жодна з перев≥рних вершин не Ї жодною з вершин ран≥ше сформованих фрагмент≥в). якщо У“акФ Ц перех≥д до блоку 6, €кщо УЌ≥Ф Ц до блоку 7.

” блоц≥ 6 формуЇтьс€ новий фрагмент з центральноњ вершини графа та обох перев≥рних вершин.

” блоц≥ 7 анал≥зуЇтьс€, чи в≥дпов≥дають перев≥рн≥ вершини умовам випадку 2 (перша перев≥рна вершина Ї активною вершиною де€кого ран≥ше сформованого фрагмента, а друга перев≥рна вершина не Ї жодною з вершин ран≥ше сформованих фрагмент≥в). якщо У“акФ Ц перех≥д до блоку 8, €кщо УЌ≥Ф Ц до блоку 9.

” блоц≥ 8 формуЇтьс€ розширений фрагмент з ран≥ше сформованого фрагмента та другоњ перев≥рноњ вершини, визначених у блоц≥ 7.

” блоц≥ 9 анал≥зуЇтьс€, чи в≥дпов≥дають перев≥рн≥ вершини умовам випадку 3 (перша перев≥рна вершина Ї активною вершиною одного, а друга Ц активною вершиною ≥ншого ран≥ше сформованих фрагмент≥в). якщо У“акФ Ц перех≥д до блоку 10, €кщо УЌ≥Ф Ц до блоку 11.

” блоц≥ 10 формуЇтьс€ обТЇднаний фрагмент з обох ран≥ше сформованих фрагмент≥в, визначених у блоц≥ 9.

” блоц≥ 11 анал≥зуЇтьс€, чи зак≥нчено формуванн€ обТЇднаного к≥льцевого маршруту (вс≥ пари вершин r та s перев≥рен≥, або дл€ ус≥х пар вершин r та s, що залишилис€ неперев≥реними, Lkr + Lks - Lrs = 0). якщо УЌ≥Ф Ц поверненн€ до блоку 4, €кщо У“акФ Ц зак≥нченн€ роботи алгоритму.

«азначимо, що оск≥льки перев≥рка будь-€коњ пари вершин r та s завжди призводить до одного з чотирьох зазначених випадк≥в, достатньо перев≥рити умови виконанн€ лише трьох з них, тому в наведеному алгоритм≥ умова виконанн€ випадку 4 не перев≥р€Їтьс€.

Ќаведемо приклад побудови найкоротших к≥льцевих маршрут≥в перевезенн€ пошти.

ѕочатковий граф мереж≥ наведено на рис. 2.9. ¬ершини графа позначен≥ цифрами 0 Е 9 (0 Ц центральна вершина графа). Ѕ≥л€ ребер графа зазначен≥ њх прот€жност≥ (км).

 

1 2 3

9 7

 

6 6 5 6

4 5

3 4 5

0 6

8 5

4 4

7 8 9

–исунок 2.9. ѕочатковий граф мереж≥

«наченн€ найкоротших в≥дстаней м≥ж вершинами графа (км) у вид≥ трикутноњ матриц≥ наведен≥ у табл. 2.20.

“аблиц€ 2.20. «наченн€ найкоротших в≥дстаней м≥ж вершинами графа

                     
-                    
  -                  
  -                
  -              
  -            
  -          
  -        
  -      
  -    
  -  

«наченн€ величин Lkr + Lks - Lrs (км) у вид≥ трикутноњ матриц≥ наведен≥ у табл. 2.21.

“аблиц€ 2.21. «наченн€ величин Lkr + Lks - Lrs (км)

                   
-                  
  -                
  -              
    -            
    -          
    -        
      -      
    -    
    -  

ѕосл≥довн≥сть крок≥в побудови найкоротших к≥льцевих маршрут≥в (Lkr + Lks - Lrs > 0) наведено у табл. 2.22.

“аблиц€ 2.22. ѕосл≥довн≥сть крок≥в побудови найкоротших к≥льцевих маршрут≥в

 рок ѕерев≥рн≥ вершини «наченн€ величин Lkr + Lks - Lrs (км) ‘рагмент 1 ‘рагмент 2
  7,8   0-7-8-0  
  2,3   0-7-8-0 0-2-3-0
  8,9   0-7-8-9-0 0-2-3-0
  1,2   0-7-8-9-0 0-1-2-3-0
  2,5   0-7-8-9-0 0-1-2-3-0
  2,6   0-7-8-9-0 0-1-2-3-0
  3,5   0-7-8-9-0 0-1-2-3-5-0
  3,6   0-7-8-9-0 0-1-2-3-5-0
  5,6   0-7-8-9-0 0-1-2-3-5-6-0
  1,4   0-7-8-9-0 0-4-1-2-3-5-6-0
  2,4   0-7-8-9-0 0-4-1-2-3-5-6-0
  7,9   0-7-8-9-0 0-4-1-2-3-5-6-0
  1,3   0-7-8-9-0 0-4-1-2-3-5-6-0

 

¬ результат≥ роботи алгоритму сформован≥ два к≥льцевих маршрути: 0-7-8-9-0 прот€жн≥стю 21 км ≥ 0-4-1-2-3-5-6-0 прот€жн≥стю 45 км.

«а на€вност≥ достатнього резерву часу проходженн€ маршруту ≥ вантажоп≥дйомност≥ транспортного засобу може бути сформований обТЇднаний к≥льцевий маршрут 0-7-8-9-4-1-2-3-5-6-0 прот€жн≥стю 66 км.

«а браком часу проходженн€ маршруту або вантажоп≥дйомност≥ транспортного засобу в≥дпов≥дний маршрут (найб≥льш прот€жний або найб≥льш завантажений) може бути розд≥лений на два маршрути, наприклад, маршрут 0-4-1-2-3-5-6-0 прот€жн≥стю 45 км може бути розд≥лений на маршрути 0-4-1-2-0 прот€жн≥стю 27 км ≥ 0-3-5-6-0 прот€жн≥стю 30 км. «ростанн€ загальноњ прот€жност≥ маршрут≥в на 12 км обумовлене зам≥ною найкоротшоњ в≥дстан≥ L 23(7 км) сумою найкоротших в≥дстаней L 20 + L 03 (19 км).

’оча формально дл€ побудови найкоротших к≥льцевих маршрут≥в в наведеному приклад≥ знадобилось 13 крок≥в, њх реальне число значно менше, оск≥льки при виконанн≥ на €комусь кроц≥ умов випадку 4 (хоча б одна з перев≥рних вершин Ї пасивною вершиною будь-€кого ран≥ше сформованого фрагмента або обидв≥ перев≥рн≥ вершини Ї активними вершинами де€кого ран≥ше сформованого фрагмента), н≥€ких д≥й не провадитьс€.

” розгл€нутому приклад≥ умови випадку 4 виконуютьс€ на кроках 5, 6, 8, 11, 12, 13, отже фактично побудова найкоротших к≥льцевих маршрут≥в виконуЇтьс€ лише на кроках 1, 2, 3, 4, 7, 9, 10, тобто на 7 з 13 крок≥в.

 





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


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


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

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

„еловек, которым вам суждено стать Ц это только тот человек, которым вы сами решите стать. © –альф ”олдо Ёмерсон
==> читать все изречени€...

2058 - | 1923 -


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

√ен: 0.022 с.