Задача коммивояжера (TSP) с использованием метода редуцированных матриц

Учитывая набор городов и расстояние между каждой парой городов, задача состоит в том, чтобы найти кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходную точку.

Примеры:

Input: 

Example of connections of cities

Output: 80
Explanation: An optimal path is 1 – 2 – 4 – 3 – 1.

Подход динамического программирования: этот подход уже обсуждался в Set-1 этой статьи.

Подход ветвей и границ: подход ветвей и границ уже обсуждался в этой статье.

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

• Строка или столбец матрицы смежности называется сокращенной тогда и только тогда, когда она содержит хотя бы один нулевой элемент и все остальные элементы в этой строке или столбце ≥ 0.
• Если все строки и столбцы сокращены, то только матрица является сокращенной матрицей.
• Длина тура (новая) = Длина тура (старая) – Общая стоимость уменьшена.
• Сначала мы перепишем исходную матрицу смежности стоимости, заменив все диагональные элементы от 0 до бесконечности.

Основная идея решения проблемы:

• The cost to reduce the matrix initially is the minimum possible cost for the travelling salesman problem.
• Now in each step, we need to decide the minimum possible cost if that path is taken i.e., a path from vertex u to v is followed. 
• We can do that by replacing uth row and vth column cost by infinity and then further reducing the matrix and adding the extra cost for reduction and cost of edge (u, v) with the already calculated minimum path cost.
• Once at least one path cost is found, that is then used as upper bound of cost to apply the branch and bound method on the other paths and the upper bound is updated accordingly when a path with lower cost is found.

Ниже приведены шаги для реализации описанной выше процедуры:

1. Шаг 1: Создайте класс (узел), который может хранить уменьшенную матрицу, стоимость, текущий номер города, уровень (количество посещенных городов) и путь, посещенный до сих пор.
2. Шаг 2: Создайте приоритетную очередь для хранения активных узлов с минимальной стоимостью вверху.
3. Шаг 3: Инициализируйте начальный индекс уровнем = 0 и уменьшите матрицу. Вычислите стоимость данной матрицы, сократив строку, а затем столбец. Стоимость рассчитывается следующим образом:
   • Сокращение строк — найдите минимальное значение для каждой строки и сохраните его. Найдя минимальный элемент в каждой строке, вычтите его из всех элементов в этой конкретной строке.
   • Сокращение столбца — найдите минимальное значение для каждого столбца и сохраните его. Найдя минимальный элемент в каждом столбце, вычтите его из всех элементов в этом конкретном столбце. Теперь матрица уменьшена.
   • Теперь добавьте все минимальные элементы в строку и столбец, найденные ранее, чтобы получить стоимость.
4. Шаг 4: Поместите элемент со всей информацией, необходимой узлу, в очередь приоритетов.
5. Шаг 5: Теперь выполните следующие операции, пока очередь приоритетов не станет пустой.
   • Извлеките элемент с минимальным значением из очереди приоритетов.
   • Для каждой операции всплытия проверьте, равен ли уровень текущего узла количеству узлов/городов или нет.
   • Если да, то распечатайте путь и верните минимальную стоимость.
   • Если нет, то для каждого дочернего узла текущего узла рассчитайте стоимость, используя формулу:
     Child->Cost = parent_matrix_cost + cost_from_parentTochild + Child_reducedMatrix_cost.
     • Стоимость сокращенной матрицы можно рассчитать, приведя все значения ее строк и столбцов к бесконечности, а также сделав индекс Matrix[Col][row] = бесконечностью.
   • Затем снова поместите текущий узел в приоритетную очередь.
6. Шаг 6: Повторяйте шаг 5, пока мы не достигнем уровня = Количество узлов — 1.

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

Иллюстрация:

Consider the connections as shown in the graph:

Example of connections

Initially the cost matrix looks like:

row/col no	1	2	3	4
1	–	10	15	20
2	10	–	35	25
3	15	35	–	30
4	20	25	30	–

After row and column reduction the matrix will be:

row/col no	1	2	3	4
1	–	0	5	10
2	0	–	25	15
3	0	20	–	15
4	0	5	10	–

and row minimums are 10, 10, 15 and 20.

row/col no	1	2	3	4
1	–	0	0	0
2	0	–	20	5
3	0	20	–	5
4	0	5	5	–

and the column minimums are 0, 0, 5 and 10.
So the cost reduction of the matrix is (10 + 10 + 15 + 20 + 5 + 10) = 70

Now let us consider movement from 1 to 2: Initially after substituting the 1st row and 2nd column to infinity, the matrix will be:

row/col no	1	2	3	4
1	–	–	–	–
2	–	–	20	5
3	0	–	–	5
4	0	–	5	–

• After the matrix is reduced the row minimums will be 5, 0, 0 

row/col no	1	2	3	4
1	–	–	–	–
2	–	–	15	0
3	0	–	–	5
4	0	–	5	–

• and the column minimum will be  0, 5, 0

row/col no	1	2	3	4
1	–	–	–	–
2	–	–	10	0
3	0	–	–	5
4	0	–	0	–

• So the cost will be 70 + cost (1, 2) + 5 + 5 = 70 + 0 + 5 + 5 = 80.

Continue this process till the traversal is complete and find the minimum cost.

Given below the structure of the recursion tree along with the bounds:

The recursion diagram with bounds

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(2 ^N * N ² ), где N = количество узлов/городов.
Космическая сложность: O(N ² )