Определение оптимального замкнутого маршрута

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G0: ξ(G0)=hΣ.

3. Произведем ветвление множества G0 на два непересекающихся подмножества G1 и G2:

· подмножество G1 получается из множества G0 при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;

· подмножество G2 получается из множества G0 при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G1 с наибольшей вероятностью содержало оптимальный цикл, а множество G2 – не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть Сij=0, таким образом, чтобы циклам, входящим в подмножество G2, соответствовали как можно более длинные пути. Так как по определению подмножества G2 путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (j¹s), а в город s коммивояжер приезжает из некоторого пункта i (i¹r), длина этого пути будет не меньше чем

Θ(r, s)=

Поэтому необходимо выбрать пару (r, s) так, чтобы Θ(r, s) было максимально, т. е.

Θ(r,s)= (2.3)

при условии, что Сij=0.

4. Выполним преобразование матрицы расстояний при ветвлении и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С2, соответствующая подмножеству G2, получается из матрицы С в результате следующих преобразований:

· запрещается переезд из города r в город s: Сrs→¥;

· проводится процедура приведения матрицы. Оценка подмножества G2 равна оценке исходного множества G0 и Θ(r, s):

ξ(G2)=ξ(G0)+Θ(r, s).

Для построения матрицы С1 соответствующей подмножеству G1 выполняются следующие преобразования матрицы С:

· вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;

· запрещается переезд из города s в город r (Сsr→¥), а также все другие переезды, которые приводят к образованию замкнутых подциклов;

· выполняется процесс приведения матрицы С.

Оценка подмножества G1 равна оценке исходного множества G0 и сумме приводящих констант:

ξ( G1)=ξ( G0) +.

грузопоток транспортный сеть маршрут

Для дальнейшего ветвления на следующем шаге выбирается то из двух полученных подмножеств G1 и G2, которое имеет наименьшую оценку. Процесс построения и оценивания подмножеств продолжается до тех пор, пока не будет получена матрица размерности 2´2, которая содержит только две допустимые пары городов. Эти пары являются замыкающими для некоторого маршрута без петель.

5. Проверим условие оптимальности. Если оценка полученного замкнутого маршрута не больше оценок всех допустимых для дальнейшего ветвления подмножеств (висячих вершин дерева), то он является оптимальным. Если существует хотя бы одно подмножество с меньшей оценкой, то построенный цикл запоминается. Процесс ветвления продолжается исходя из множества с меньшей оценкой до тех пор, пока нижние границы новых подмножеств остаются меньше длины выделенного цикла. В ходе ветвления либо будет построен цикл меньшей длины, либо обнаружится, что на новых подмножествах он не существует, т. е. оценка для каждого из них не меньше рекорда (длины кратчайшего из ранее полученных циклов).

Популярные материалы:

История развития
Первые полёты. Изобретателем дирижабля считается Жан Батист Мари Шарль Мёнье. Дирижабль Мёнье должен был быть сделан в форме эллипсоида. Управляемость должна была быть осуществлена с помощью трех пропеллеров, вращаемых вручную усилиями 80 ...

Устройство и работа датчика боковых перемещений
В состав УСП КП входят два датчика боковых перемещений. Они предназначены для регистрации вертикальных перемещений кузова автомотрисы АДМ-1 относительно буксы колесной пары и передачи в УСП КП информации о значении указанных перемещений. ...

Установка дейдвудной трубы и гребного вала
Для крепления втулок дейдвудных труб на торцах мортир сверлят отверстия с последующей нарезкой в них резьбы для шпилек. Сверление целесообразно производить по кондукторам — это позволяет избежать запрессовки дейдвудных труб и втулок для р ...