Алгоритмрешения задачметодомветвейиграниц




включает следующуюпоследовательность:

1. Проводим операцию редукции матрицы расстояний по строкам и столбцам и находим нижнюю границу всего множествамаршрутов: Hdidj.

2.Вкаждой клетке, вкоторых dij =0,поочередно заменяем нули на ∞затем находим новые суммы констант приведения di + dj, которые записываемвклеткахрядомснулемвскобках

3. Выбираемребро ветвления(i, j)помаксимальнойвеличине суммыконстант приведения. Затемисключаем егоизмножества путемзаменыэлементаматрицы dij =∞.Врезультатебудетобразованоподмножествомаршрутов{(i, j)}.

4.Редуцируемполученнуюматрицурасстоянийиопределяем нижнююграницуэтогоподмножествамаршрутов H (i,j).

5. Включаемдугу (i, j)вмаршрутпутемисключения i -йстрокии j -гостолбцаизматрицы изаменысимметричногоэлемента матрицы dji =∞для исключенияобразованиянегамильтоновацикла.

i, j).
6. Редуцируем сокращенную матрицу и определяем нижнюю границу подмножества Н {(i, j)}

7. Сравниваем нижние границы подмножеств Н {(i, j)} и

Н {(i, j)}

i, j)}
и подвергаем подмножество, имеющее меньшее значение нижней границы, ветвлению.

8.Определяемгамильтоновциклприполученииматрицы2×2.

 

 



 

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

1.Построение матрицы с исходными данными - длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.). Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2.Нахождение минимума по строкам Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

3.Редукция строк Проводим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4.Нахождение минимума по столбцам Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

5.Редукция столбцов Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6.Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках. И так по всем нулевым клеткам:

7.Редукция матрицы Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9 Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д. Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными. В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4. Общая длина пути: L = 30.

 

 

Задача

На территории Крыма для путешествия на автомобиле выделены города: Бахчисарай, Ай-Петри, Ялта, Алупка и Соколиное, расстояния между которыми записаны на ребрах неориентированного графа. Построить оптимальный маршрут проезда по городам Крыма.

 

Решение

1. Расстояниямеждугородамипредставлены ввидематрицы:

 

Lij          
  М        
    М      
      М    
        М  
          М

 

Постройте кратчайшийкольцевоймаршрут объездавсехгородов.

2.Нахождение минимума по строкам di

Lij           di
  М          
    М        
      М      
        М    
          М  

 

3.Редукция строк строк Проводим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Lij          
  М        
    М      
      М    
        М  
          М

 

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4.Нахождение минимума по столбцам dj

 

Lij          
  М        
    М      
      М    
        М  
          М
dj          

5.Редукция столбцов Вычитаем из каждого элемента матрицы соответствующий ему элемент dj.

Lij          
  М        
    М      
      М    
        М  
          М

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6.Вычисление оценок нулевых клеток

Lij          
  М       0(53)
    М      
      М    
        М  
          М

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках. И так по всем нулевым клеткам:

Lij          
  М       0(53)
    М   0(31)  
      М 0(33)  
      0(28) М  
  0(59) 0(2)     М

7.Редукция матрицы Выбираем нулевую клетку с наибольшей оценкой и Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 5-ого к 1-му).

Lij          
  М       М
    М   0(31)  
      М 0(33)  
      0(28) М  
  М 0(2)     М

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Lij        
        М
  М   0(31)  
    М 0(33)  
    0(28) М  

8. Если полный путь еще не найден, переходим к пункту 2.Нахождение минимума по строкам di:

Lij         di
        М  
  М        
    М      
      М    

Редукция строк

Lij        
        М
  М      
    М    
      М  

4.Нахождение минимума по столбцам dj

Lij        
        М
  М      
    М    
      М  
dj        

Редукция столбцов

Lij        
        М
  М      
    М    
      М  

6.Вычисление оценок нулевых клеток

Lij        
  0(52)     М
  М   0(0) 0(21)
    М 0(14)  
    0(32) М  

7.Редукция матрицы Выбираем нулевую клетку с наибольшей оценкой и Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 1-ого к 2-му).

Lij        
  М     М
  М   0(0) 0(21)
    М 0(14)  
    0(32) М  
Lij      
    0(0) 0(21)
  М 0(28)  
  0(51) М  

4-ого к 3-му).

Lij    
  0(0) 0(28)
  М  

 

Ответ: (1-5-2-3-4-1); Lmin=226км.

 

Глава4.Методыимоделитеорииграфовисетевогомоделирования

 

 

Рис.4.5.2. Неориентированныйграфзадачикоммивояжера

 



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-23 Нарушение авторских прав и Нарушение персональных данных


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