Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Анализ методов решения задачи коммивояжера

Для подведения итогов в изучении методов решения ЗК протестируем наиболее оптимальные алгоритмы на компьютере по следующим показателям: количество городов, время обработки, вероятность неправильного ответа. Данные занесём в таблицу.

табл. 1.4.1
Алгоритм лексического перебора
Кол-во городов Время обработки, c Вероятность неправильного ответа, % Тип алгоритма
точный
12000=3С‡.20РјРёРЅ
-*
-*
Метод ветвей и границ
~0 точный
~0.0001
1.2

*- ЗК с таким количеством городов методом лексического перебора современный компьютер не смог бы решить даже за всё время существования Вселенной.

Как видим по результатам этой таблицы, алгоритм лексического перебора можно применять лишь в случае с количеством городов 5...12. Метод ветвей и границ можно применять всегда.


Глава 2. Практическая реализация задачи коммивояжёра

Решить задачу коммивояжёра, то есть построить оптимальный кольцевой маршрут для орграфа (рис.) с вершинами . Стоимость единицы пути равна 10. Пропускные способности дуг (расстояния между населёнными пунктами) указаны в таблице:

табл. 2.1
  X1 X2 X3 X4 X5
X1 -
X2 -
X3 -
X4 -
X5 -

Решение задачи коммивояжёра методом ветвей и границ

 

табл. 2.1.1  
-  
-
-
-
-
-
табл. 2.1.2  
-  
-  
-  
-  
-  
-  
         

 

 

табл. 2.1.3  
-  
- 00 01  
00 - 05  
00 - 02  
04 -  
02 -  
             

d(x) - минимальная стоимость тура

 
 

 

 


табл. 2.1.4  
-  
- 0 0
0 - -
0 - 0
0 -
0 -
   

 

Стоимость маршрута, не содержащего путь {2,3} будет не менее 63.

табл. 2.1.5  
-    
- 0 0  
0 - 0  
0 -  
0 -  
     

табл. 2.1.6  
-    
- 00 02  
02 - 03  
04 -  
02 -  
     
     
табл. 2.1.7  
-  
- 0 0
0 - 0
- -
0 -
           

 

 

Стоимость маршрута содержащего путь {2,3} будет не менее 58. Для дальнейшего решения выбираем путь содержащий граф с вершинами {2,3}.

табл. 2.1.8  
-    
- 0 0    
0 - 0    
- -    
0 -    
     

табл. 2.1.9
-    
- 0  
0 -  
-  
           
табл. 2.1.10
-    
- 0    
0 -    
-    
     
табл. 2.1.11
-    
- 0    
0 -    
-    
           

 

 

Стоимость маршрута, не содержащего путь {4,2} будет не менее 62.Стоимость маршрута содержащего путь {4,2} будет не менее 63. Для дальнейшего решения выбираем путь не содержащий граф с вершинами {4,2}.

 

табл. 2.1.12  
-    
- 00 01    
00 - 03    
01 - -    
02 -    
             

 

табл. 2.1.13  
-    
- 0 0  
0 - -  
0 - -  
0 -  
     
табл. 2.1.14  
-    
- 0 0    
0 - -    
0 - -    
0 -    
             

 

табл. 2.1.15  
-    
- 0 0  
0 -  
0 -  
     
             

 

табл. 2.1.16  
-    
- 00 01    
03 -    
02 -    
           
             

 

 

табл. 2.1.17
-  
- 0 0
- -
0 -
         
табл. 2.1.18
-  
- 00 01  
- -  
02 -  
   
табл. 2.1.19    
-  
- 00 01  
- -  
02 -  
         
             

 

 

табл. 2.1.20
-    
- 0  
0 -  
     

Поучаем путь {2,3}{3,4}{4,1}{1,5}{5,2}стоимость которого равна (10+20+14+10+8)*10=620.

Решение задачи с помощью программы «Нахождение оптимального маршрута»

Последнее изменение этой страницы: 2016-07-22

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...