Решение задачи коммивояжера online

Пример решения задачи коммивояжера венгерским методом

Исходная матрица имеет вид:

  M  3  4  2  7
 5  M  8  4  3
 2  3  M  7  5
 3  2  9  M  1
 1  2  3  5  M

 1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
 M  1  2  0  5  2
 2  M  5  1  0  3
 0  1  M  5  3  2
 2  1  8  M  0  1
 0  1  2  4  M  1

 Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
 M  0  0  0  5
 2  M  3  1  0
 0  0  M  5  3
 2  0  6  M  0
 0  0  0  4  M
 0  1  2  0  0

 После вычитания минимальных элементов получаем полностью редуцированную матрицу.
 2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
 M  [-0-]  [-0-]  [0]  5
 2  M  3  1  [0]
 [0]  [-0-]  M  5  3
 2  [0]  6  M  [-0-]
 [-0-]  [-0-]  [0]  4  M

 В результате получаем эквивалентную матрицу Сэ:
 M  0  0  0  5
 2  M  3  1  0
 0  0  M  5  3
 2  0  6  M  0
 0  0  0  4  M

 4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
 M  [-0-]  [-0-]  [0]  5
 2  M  3  1  [0]
 [0]  [-0-]  M  5  3
 2  [0]  6  M  [-0-]
 [-0-]  [-0-]  [0]  4  M

 Cmin = 2 + 3 + 2 + 2 + 3 = 12

Скачать в формате doc

загрузка...