Методы решения задачи коммивояжёра
Автор: luigik • Август 1, 2020 • Лабораторная работа • 371 Слов (2 Страниц) • 385 Просмотры
- В соответствии с вариантом выбрать из табл. 5.6 координаты узлов проектируемой ЛВС на двумерной плоскости.
[pic 1]
- Рассчитать расстояния между узлами и занести их в соответствующую таблицу.
q2 | q3 | q4 | q5 | q6 | q7 | q8 | q9 | q10 | |
q1 | 91.78 | 21.38 | 43.14 | 78.79 | 85.71 | 57.07 | 86.83 | 37.05 | 94.37 |
q2 | 70.41 | 77.47 | 107.07 | 29.43 | 34.71 | 61.61 | 56.65 | 3.61 | |
q3 | 36.14 | 76.79 | 65.73 | 35.69 | 71.7 | 17.09 | 73.01 | ||
q4 | 41.05 | 58.52 | 49.4 | 47.3 | 29.83 | 80.92 | |||
q5 | 80.81 | 86.4 | 53.25 | 70.18 | 110.68 | ||||
q6 | 36.4 | 32.28 | 48.84 | 32.76 | |||||
q7 | 56.65 | 23.05 | 37.36 | ||||||
q8 | 55.87 | 65.0 | |||||||
q9 | 59.62 |
- Рассчитать длину маршрута Т1 = <1,2,3,4,5,6,7,8,9,10,1>.
[pic 2]
- Определить длину маршрута на основе ближайшей свободной вершины
Маршрут, построенный на основе метода ближайшей свободной вершины: T2 = <1-3-9-7-6-10-2-8-4-5-1> = 363
5. Выбрать минимальный из рассчитанных маршрутов в качестве текущего оптимального маршрута Т0т.
Т0т = T2
6. Методом ветвей и границ проанализировать первых 20 уникальных
маршрутов.
Уровни | ||||||||||
Маршруты | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1-3-9-7-6-10-2-8-4-5-1 | 21.38 | 38.47 | 61.49 | 97.89 | 130.64 | 134.25 | 195.86 | 243.16 | 284.21 | 363.0 |
1-2-3-4-5-6-7-8-10-9-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 356.58 | ||||
1-2-3-4-5-6-7-9-8-10-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 356.58 | ||||
1-2-3-4-5-6-7-9-10-8-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 356.58 | ||||
1-2-3-4-5-6-7-10-8-9-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 356.58 | ||||
1-2-3-4-5-6-7-10-9-8-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 356.58 | ||||
1-2-3-4-5-6-8-7-9-10-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-8-7-10-9-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-8-9-7-10-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-8-9-10-7-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-8-10-7-9-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-8-10-9-7-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.46 | ||||
1-2-3-4-5-6-9-7-8-10-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-9-7-10-8-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-9-8-7-10-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-9-8-10-7-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-9-10-7-8-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-9-10-8-7-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 369.02 | ||||
1-2-3-4-5-6-10-7-8-9-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.94 | ||||
1-2-3-4-5-6-10-7-9-8-1 | 91.78 | 162.19 | 198.33 | 239.38 | 320.18 | 352.94 |
7. Рассчитать для них по выражению (5.1) КУВ
[pic 3]
8. Найти оптимальный вариант топологии геометрическим методом и рассчитать его длину.
[pic 4]
Очевидно, что граничными точками являются узлы 1,3,9,7,10,6,8,5,4. Через них строится граничный многоугольник
[pic 5]
Каждая из внутренних точек i (i=2, 9) образует со стороной многоугольника (j, k) треугольник (j=k; k=1,3,9,7,10,6,8,5,4). Определим для каждой внутренней точки и каждой стороны многоугольника удлинение, вносимое точкой при включении её в контур.
...