Метод ветвей и границ

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

• (1) Построение матрицы с исходными данными.
• (2) Нахождение минимума по строкам.
• (3) Редукция строк.
• (4) Нахождение минимума по столбцам.
• (5) Редукция столбцов.
• (6) Вычисление оценок нулевых клеток.
• (7) Редукция матрицы.
• (8) Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
• (9) Вычисление итоговой длины пути и построение маршрута.

Подробная методика решения В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т. д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие — «дороги».

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

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

Таблица 1.

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т. д.).

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

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

Таблица 2.

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

Таблица 3.

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

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

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

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

Таблица 5.

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

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

Таблица 6.

И так по всем нулевым клеткам:

Таблица 7.

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

Таблица 8.

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

Таблица 9.

8. если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

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

Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) — переходим к пункту 9.

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

В нашем примере маршрут получился следующий: 4 > 2 > 3 > 1 > 4.

Общая длина пути: L = 30.