Используя венгерский метод решить следующую задачу коммивояжера. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Используя венгерский метод решить следующую задачу коммивояжера

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

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Используя венгерский метод, решить следующую задачу коммивояжера, если матрица затрат на переезд из города в город выглядит следующим образом: город Стоимость проезда 1 2 3 4 5 6 1 - 6 5 2 1 5 2 10 - 6 11 3 5 3 1 10 - 12 15 1 4 2 12 4 - 5 6 5 7 8 3 5 - 3 6 2 12 10 10 5 -

Нужно полное решение этой работы?

Решение

Потяни, чтобы посмотреть

Дана матрица
- 6 5 2 1 5
10 - 6 11 3 5
1 10 - 12 15 1
2 12 4 - 5 6
7 8 3 5 - 3
2 12 10 10 5 -
Шаг 1
Вычтем из каждой строки минимальное значение
- 6 5 2 1 5 -1
10 - 6 11 3 5 -3
1 10 - 12 15 1 -1
2 12 4 - 5 6 -2
7 8 3 5 - 3 -3
2 12 10 10 5 - -2
Получили
- 5 4 1 0 4
7 - 3 8 0 2
0 9 - 11 14 0
0 10 2 - 3 4
4 5 0 2 - 0
0 10 8 8 3 -
Так как у нас не в каждом столбце есть 0, то вычтем так же из каждого столбца его минимальное значение
- 5 4 1 0 4
7 - 3 8 0 2
0 9 - 11 14 0
0 10 2 - 3 4
4 5 0 2 - 0
0 10 8 8 3 -
0 -5 0 -1 0 0
Получили
- 0 4 0 0 4
7 - 3 7 0 2
0 4 - 10 14 0
0 5 2 - 3 4
4 0 0 1 - 0
0 5 8 7 3 -
Шаг 2 Попробуем найти решение (0 точки решения выделим жирным)
- 0 4 0 0 4
7 - 3 7 0 2
0 4 - 10 14 0
0 5 2 - 3 4
4 0 0 1 - 0
0 5 8 7 3 -
На 6 строке получили разрыв
Шаг 3
Вычеркнем нулевые строки и столбцы минимально-возможным количеством линий
- 0 4 0 0 4
7 - 3 7 0 2
0 4 - 10 14 0
0 5 2 - 3 4
4 0 0 1 - 0
0 5 8 7 3 -
Среди не зачеркнутых элементов найдем минимальное значение это значение 2 и вычтем его из всех не зачеркнутых элементов
- 0 4 0 0 4
7 - 1 5 0 2
0 2 - 8 14 0
0 3 0 - 3 4
4 0 0 1 - 0
0 3 6 5 3 -
И ячейки которые находятся на пересечении зачеркивающихся линий увеличим на 2
- 0 4 0 2 6
7 - 1 5 0 2
0 2 - 8 14 0
0 3 0 - 3 4
6 0 0 1 - 2
0 3 6 5 3 -
Шаг 4 Попробуем найти решение (выделяем жирным) идем сверху вниз
- 0 4 0 2 6
7 - 1 5 0 2
0 2 - 8 14 0
0 3 0 - 3 4
6 0 0 1 - 2
0 3 6 5 3 -
Решение найдено теперь посчитаем сумму
город Стоимость проезда
1 2 3 4 5 6
1 - 6 5 2 1 5
2 10 - 6 11 3 5
3 1 10 - 12 15 1
4 2 12 4 - 5 6
5 7 8 3 5 - 3
6 2 12 10 10 5 -
∑=2+8+4+2+3+1=20
Ответ ∑==20

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу