АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Пример решения задачи коммивояжера

Читайте также:
  1. Exercises for Lesson 3. Requests and offers / Просьбы и предложения. Способы выражения, лексика, примеры.
  2. Exercises for Lesson 3. Requests and offers / Просьбы и предложения. Способы выражения, лексика, примеры.
  3. Exercises for Lesson 3. Requests and offers / Просьбы и предложения. Способы выражения, лексика, примеры.
  4. I. Прокурор: понятие, положение, функции и профессиональные задачи.
  5. I. СУЩНОСТЬ, ЦЕЛЬ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ
  6. I. ЦЕЛИ И ЗАДАЧИ ОСВОЕНИЯ ДИСЦИПЛИНЫ
  7. II. Задачи территориального фонда
  8. II. ОСНОВНЫЕ ЦЕЛИ И ЗАДАЧИ КОНЦЕПЦИИ
  9. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  10. II. Способы решения детьми игровых задач
  11. II. Способы решения детьми игровых задач
  12. II. Цели и задачи Конкурса

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij

i j           di
  M          
    M        
      M      
        M    
          M  


Затем вычесть его из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j          
  M        
    M      
      M    
        M  
          M


Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij

i j          
  M        
    M      
      M    
        M  
          M
dj          


После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

i j          
  M        
    M      
      M    
        M  
          M


Сумма констант приведения определяет нижнюю границу H:

H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:

Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Определяем ребро ветвления и разобъем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j           di
  M     0(40)    
    M 0(20)      
    0(10) M   0(30)  
  0(10)     M    
  0(0)     0(0) M  
dj            


d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подножества (1,4) и (1*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,4*) = 140 + 40
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j           di
  M     M    
    M        
      M      
        M    
          M  
dj            


Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41 заменяем на М, для исключения образования не гамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

i j         di
    M      
      M    
  M        
        M  
dj          


Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 < 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j         di
    M 0(20)    
    0(10) M 0(30)  
  M   0(30)    
  0(30)     M  
dj          


d(1,3) = 20 + 0 = 20; d(2,2) = 0 + 10 = 10; d(2,4) = 0 + 30 = 30; d(3,3) = 30 + 0 = 30; d(4,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30
Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.

i j         di
    M      
      M M  
  M        
        M  
dj          


Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

i j       di
    M    
  M      
      M  
dj        


Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 < 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут.
Определяем ребро ветвления и разобъем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j       di
    M 0(20)  
  M   0(30)  
  0(20) 0(30) M  
dj        


d(1,3) = 20 + 0 = 20; d(2,3) = 30 + 0 = 30; d(3,1) = 0 + 20 = 20; d(3,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (30 + 0) = 30 для ребра (4,3), следовательно, множество разбивается на два подножества (4,3) и (4*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(4*,3*) = 160 + 30
Исключение ребра (4,3) проводим путем замены элемента d43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j       di
    M    
  M   M  
      M  
dj        


Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d34 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица будет иметь вид:

i j     di
    M  
       
dj      


Нижняя граница подмножества (4,3) равна:
H(4,3) = 160 + 20 = 180 < 190
Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (5,2) и (2,1).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180

 


1 | 2 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)