Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
41
Добавлен:
02.05.2014
Размер:
382.98 Кб
Скачать

Задача коммивояжера

Задание:

Решить задачу коммивояжера по следующим данным:

 

1

2

3

4

5

6

1

-

41

60

39

46

10

2

31

-

59

16

1

51

3

29

51

-

14

42

50

4

35

12

52

-

16

26

5

16

39

15

60

-

57

6

15

30

38

47

36

-

Решение:

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

Сложив приведение по строкам и по столбцам, получим: 67 + 0 = 67.

Следовательно, Min оценка = 67.

Оценим нули в полученной матрице:

Max оценка = 43.

Разбиваем на 1,6 и not 1,6.

Минор по 1,6.

Вводим запрет на 6,1.

Оценим нули в полученной матрице:

Max оценка = 29.

Разбиваем на 3,4 и not 3,4.

Минор по 3,4.

Вводим запрет на 4,3.

Оценим нули в полученной матрице:

Max оценка = 33.

Разбиваем на 2,5 и not 2,5.

Минор по 2,5.

Вводим запрет на 5,2.

Оценим нули в полученной матрице:

Max оценка = 37.

Разбиваем на 4,2 и not 4,2.

Минор по 4,2.

Вводим запрет на 5,3.

Приводим матрицу по 3 столбцу.

В итоге получим дереве ветвлений и длин путей:

По этому дереву можно определить, что оптимальным путем является последовательность:

1  6  3  4  2  5  1 и его длинна равна 91.

Вывод:

Путь является оптимальным, по данному методу, но является и наикротчайшим (в соответствии с методом прямого перебора).

Соседние файлы в папке Задача 1