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

способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов,

чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной. - 1 2 3 4 5 6 1 - 0 0 3 3 6 2 0 - 1 4 1 0 3 1 2 - 0 0 3 4 4 5 0 - 1 3 5 4 2 0 1 - 0 6 7 1 3 3 0 - 2 1 4 табл. 4 Изложим алгоритм Литтла на примере 1 предыдущего раздела.. Повторно запишем матрицу: - 1 2 3 4 5 6 1 - 6 4 8 7 14 2 6 - 7 11 7 10 3 4 7 - 4 3 10 4 8 11 4 - 5 11 5 7 7 3 5 - 7 6 14 10 10 11 7 - табл. 2 - 1 2 3 4 5 6 1 -

2 0 4 3 10 4 2 0 - 1 5 1 4 6 3 1 4 - 1 0 7 3 4 4 7 0 - 1 7 4 5 4 4 0 2 - 4 3 6 7 3 3 4 0 - 7 табл. 3   Нам будет удобнее трактовать Сij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь

стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма. Вычитая любую

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

матрицу, приведенную по столбцам, см. табл. 4). Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34. Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для