Задача коммивояжера — страница 9

тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма

чисел подчеркнутых элементов есть стоимость тура. На табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором. Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы

получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров. Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной

матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по нулю» из города 1 в город 2, то надо заплатить не меньше 1.

Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились). Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)). Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры

этого класса стоят 35 или больше. Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом. 1 2 3 4 5 6 1 - 01 0 3 3 6 2 01 - 1 4 1 0 3 1 2 - 01 0 3 4 4 5 01 - 1 3 5 4 2 0 1 - 0 6 7 1 3 3 01 - табл. 5 1 3 4 5 6 2 01 1 4 1 0 3 1 - 01 0 3 4 4 01 - 1 3 5 4 0 1 - 0 6 7 3 3 01 - табл. 6 1 3 4 5 6 2 01 1 4 1 0 3 03 - 01 0 3 4 3 01 - 1 3 5 3 0 1 - 0 6 6 3 3 01 - табл. 7 3 4 5 6   2 1 4 1 0   4 01 - 1 3   5 0 1 - 0   6 3 3 01 -   табл. 8 Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т.