Разбиение множества маршрутов на подмножества

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

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

Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента c_ij на бесконечность.

Пример задачи

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

A.	B.	C.	D.	E.	F.
A.
B.
C.
D.
E.
F.

Решение задачи.

Итерация 1.

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=4, r₂=5, r₃=2, r₄=12, r₅=5, r₆=2.

После их вычитания по строкам получим:

Минимумы по столбцам: h₁=0, h₂=1, h₃=h₄=h₅=0, h₆=1.

После их вычитания по столбцам получим приведенную матрицу:

Найдем нижнюю границу.

ц(Z) = 4+5+2+12+5+2+1+1=32.

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

И₁₄ = 10 + 0, И₂₄ = 1 + 0, И₃₅ = 5+0, И₄₂ = 0 + 4, И₄₅ = 0 + 0, И₅₁ = 4 + 0, И₅₆ = 4 + 0, И₆₃ = 4+13.

Наибольшая степень И₆₃ = 17. Ветвление проводим по дуге (6,3).

Нижняя граница для множества Z₆₃⁽¹⁾остается равной 32. Для всех маршрутов множества Z_63'⁽¹⁾ из города 6 мы не перемещаемся в город 3,.

ц (Z_63'⁽¹⁾) = 32 + 4.

В матрице, соответствующей Z₆₃⁽¹⁾, вычеркиваем шестую строку и третий столбец и положим c₃₆= ?, чтобы предотвратить появления цикла 6> 3 > 6. Получим новую платежную матрицу {c¹_ij}:

Сравнивая нижние границы ц Z_63'⁽¹⁾=40 и ц Z₆₃⁽¹⁾=32 < 40, выделяем подмножество маршрутов Z₆₃⁽¹⁾, которое с большей вероятностью содержит маршрут минимальной длины.

Итерация 2.

Приведенная платежная матрица для Z₆₃⁽¹⁾ (в каждой сроке и в каждом столбце есть 0, после приведения матрица не меняется):

Далее продолжаем процесс ветвления. Найдем степени И_ij нулевых элементов этой матрицы И₁₄ =10, И₂₄ = 1, И₃₅ = 15, И₄₂ = 10, И₄₅ = 0, И₅₁ =4, И₅₆ = 4. Наибольшая степень И₃₅=15. Затем множество Z₆₃⁽¹⁾ разбивается на дуге (3, 5) на два новых Z₃₅⁽²⁾ и Z_35'⁽²⁾.

В матрице для Z₃₅⁽²⁾ вычеркиваем строку 3 и столбец 5. Дуги (6, 3) и (3, 5) образуют связный путь (6, 3, 5); положим c₅₆= ?, чтобы предотвратить появления цикла 6>3> 5 > 6.

Для приведения надо вычесть минимум по столбцу 6: r₆=4. При этом нижняя граница станет равной 32+4=36.

Нижняя граница для Z_35'⁽²⁾, полученная как на предыдущем шаге ветвления, равна 32 + 15 = 47. Сравнивая нижние границы ц Z₃₅⁽²⁾=36 и Z_35'⁽²⁾=47>36 выбираем для дальнейшего разбиения подмножество маршрутов Z₃₅⁽²⁾.

Итерация 3.

Приведенная платежная матрица для Z₃₅⁽²⁾:

Степени И_ij нулевых элементов этой матрицы И₁₄ = 8, И₂₄ = 0, И₂₆ = 1, И₄₂ = 10, И₅₁ =21. Наибольшая степень И₅₁=21_. Затем множество Z₃₅⁽²⁾ разбивается на два новых Z₅₁⁽³⁾ и Z_51'⁽³⁾.

Нижняя граница для Z_51'⁽³⁾ равна 36+21=57. В матрице для Z₅₁⁽³⁾ вычеркиваем строку 5 и столбец 1, положим с₁₆=?. Получим матрицу:

Приведение не требуется. Выбираем для дальнейшего разбиения подмножество маршрутов Z₅₁⁽³⁾.

Итерация 4.

Приведенная платежная матрица для Z₅₁⁽³⁾:

Степени И_ij нулевых элементов этой матрицы И₁₄ = 8, И₂₄ = 0, И₂₆ = 1, И₄₂ =11. Выбираем И₄₂ =11. Разбиваем Z₅₁⁽³⁾ на Z₄₂⁽⁴⁾ и Z_42'⁽⁴⁾.

Нижняя граница для Z_42'⁽⁴⁾ равна 36+11 = 47. В матрице для Z₄₂⁽⁴⁾ вычеркиваем строку 4 и столбец 2 и полагаем c₂₄= ?. Получим.

Приведение не требуется.

Из матрицы 22 получаем два перехода с нулевой длиной: (1, 4) и (2, 6).

Полученный маршрутом коммивояжера: Z₀ = (1, 4, 2, 6, 3, 5, 1) или (A-D-B-F-C-E-A).

Пройденный путь равен 36.

Руководство пользователя.

• 1. Введите размерность матрицы.
• 2. Ведите поэлементно взвешенную матрицу смежности.
• 3. Результат работы программы:

• 4. Введите источник.
• 5. Результат работы программы: