Задача коммивояжера с использованием венгерского метода

Опубликовано: 20 Сентября, 2022

Коммивояжер планирует посетить N городов таким образом, чтобы побывать в каждом городе ровно один раз и вернуться в тот город, откуда он вышел . Расстояние между городом i и городом j равно C ij . Найдите кратчайший путь, который он может совершить.

Примечание. Путешествие из города i в город i невозможно, и C ij может не равняться C ji .

Примеры:

Input: See the routes in the image.

Output: 80
Explanation: The shortest route can be achieved following the path C1 -> C2 -> C4 -> C3 -> C1. 
So the route length is 10 + 25 + 30 + 15 = 80.

Input: See the routes in the image.

Output: 15
Explanation: The shortest route is C1 -> C2 -> C3 -> C4 -> C5 -> C1. So the path length is 2 + 3 + 4 + 5 + 1 = 15.

Интуиция: предположим, что есть 3 города, а именно город 1, город 2 и город 3. Все возможные комбинации для посещения городов

1->2->3->1       (1->2, 2->3, 3->1)
1->3->2->1       (1->3, 3->2, 2->1)
2->1->3->2       (2->1, 1->3, 3->2)
2->3->1->2       (2->3, 3->1, 1->2)
3->1->2->3       (3->1, 1->2, 2->3)
3->2->1->3       (3->2, 2->1,1->3)

Таким образом, города можно посетить 6 различными способами , но при внимательном рассмотрении можно увидеть, что 1-й, 4-й и 5-й туры эквивалентны, а 2- й, 3-й и 6-й туры эквивалентны . Следовательно, возможных комбинаций на самом деле 2 , и это

1->2->3->1
1->3->2->1

Следовательно, если есть N городов для посещения, то их может быть (N-1)! способов поехать в каждый город ровно один раз и вернуться в начальный город. Задачи этого типа могут быть решены венгерским методом, методом ветвей и границ, методом штрафа и методом ближайшего соседа. Мы увидим, как решить этот тип проблемы, используя венгерский метод.

Подход: Ниже перечислены шаги, которые необходимо выполнить для решения проблемы с использованием венгерского метода .
Рассмотрим пример, показанный на изображении:

Следуйте иллюстрациям решения приведенного выше примера для лучшего понимания.

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

Illustration:

  1. Subtracting 1st row with the minimum value 1.
  2. Subtracting 2nd row with the minimum value 2.
  3. Subtracting 3rd row with the minimum value 4.
  4. Subtracting 4th row with the minimum value 4.
  5. Subtracting 5th row with the minimum value 1.

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

Illustration:

  1. Subtracting 1st column with the minimum value 0.
  2. Subtracting 2nd column with the minimum value 0.
  3. Subtracting 3rd column with the minimum value 1.
  4. Subtracting 4th column with the minimum value 0.
  5. Subtracting 5th column with the minimum value 0.

Шаг 3: Сделайте присвоение в матрице следующим образом.

  1. Двигайтесь строка за строкой, пока не будет найдена строка с одним нулем.
  2. Назначьте ячейку, содержащую ноль, и вычеркните все остальные нули в ее столбце.
  3. Продолжайте этот процесс, пока не будут назначены все строки с одним нулем.
  4. Повторите процедуру для каждого столбца.
  5. Если строка и (или) столбец имеют два или более нулей и один из них не может быть выбран путем проверки, то присвойте произвольно любой из этих нулей и вычеркните все остальные нули этой строки/столбца.

Illustration:

Row wise cell (1,5) is assigned. So, column wise cell (2,5) is crossed off.
Row wise cell (2,3) is assigned. So, column wise cell (5,3) is crossed off.
Row wise cell (3,4) is assigned.
Row wise cell (4,2) is assigned.
Row wise cell (5,1) is assigned.

Here, the number of assignment is equal to the number of cities and the tour is 1->5->1 and 2->3->4->2 which means salesman will travel from city 1 to city 5 and return to city 1 and then again start from city , travel to city 3, city 4 and return to city 2. Therefore, we are getting two cycle and hence it is not the solution.

Шаг 4: Следующее лучшее решение можно получить, приведя минимальный ненулевой элемент и повторив шаг 2 и шаг 3.

Illustration: In this case, minimum non-zero element is 1.

Row wise cell (3,4) is assigned.      
Row wise cell (1,2) is assigned. So, column wise cell (4,2) is crossed off and row wise cell (1,5) is crossed off.
Row wise cell (2,5) is assigned. So, row wise cell (2,3) is crossed off and column wise cell (4,5) is crossed off.
Row wise cell (4,3) is assigned. So, column wise cell (5,3) is crossed off.
Row wise cell (5,1) is assigned.

Now, the sequence is 1->2->5->1 and 3->4->3. Again, we are getting two cycle therefore this is also not the solution.

Шаг 5: Сделайте другое возможное назначение

Illustration:

Row wise cell (3,4) is assigned.
Row wise cell (1,2) is assigned. So, column wise cell (4,2) is crossed off and row wise cell (1,5) is crossed off.
Row wise cell (2,3) is assigned. So, column wise cell (4,3) and (5,3) is crossed off and row wise cell (2,5) is crossed off.
Row wise cell (4,5) is assigned.
Row wise cell (5,1) is assigned.

The sequence is 1->2->3->4->5->1. So, this solution is optimal and total distance of this tour is 

Cell12 + Cell23 + Cell34 + Cell45 + Cell51 = (2+3+4+5+1) =15.

РЕКОМЕНДУЕМЫЕ СТАТЬИ