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

Пример. Решение задачи коммивояжера с помощью венгерского алгоритма

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

  M  69  15  41  46  62
 22  M  77  43  41  60
 57  78  M  13  27  82
 61  61  53  M  43  68
 38  54  34  22  M  43
 2  8  78  81  52  M

 1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
 M  54  0  26  31  47  15
 0  M  55  21  19  38  22
 44  65  M  0  14  69  13
 18  18  10  M  0  25  43
 16  32  12  0  M  21  22
 0  6  76  79  50  M  2

 Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
 M  48  0  26  31  26
 0  M  55  21  19  17
 44  59  M  0  14  48
 18  12  10  M  0  4
 16  26  12  0  M  0
 0  0  76  79  50  M
 0  6  0  0  0  21

 После вычитания минимальных элементов получаем полностью редуцированную матрицу.
 2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
 M  48  [0]  26  31  26
 [0]  M  55  21  19  17
 44  59  M  [0]  14  48
 18  12  10  M  [0]  4
 16  26  12  [-0-]  M  [0]
 [-0-]  [0]  76  79  50  M

 В результате получаем эквивалентную матрицу Сэ:
 M  48  0  26  31  26
 0  M  55  21  19  17
 44  59  M  0  14  48
 18  12  10  M  0  4
 16  26  12  0  M  0
 0  0  76  79  50  M

 4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
 M  48  [0]  26  31  26
 [0]  M  55  21  19  17
 44  59  M  [0]  14  48
 18  12  10  M  [0]  4
 16  26  12  [-0-]  M  [0]
 [-0-]  [0]  76  79  50  M

 Cmin = 15 + 22 + 13 + 43 + 43 + 8 = 144

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

загрузка...