Филатов_Отчет5_Системный_Анализ

Таким образом, дополнив «жадный метод» методом «локальных улучшений» мы получили более оптимальный результат.

Ответ: Минимальный маршрут

6

5

4

2

1

3

6

== 126

1. Метод локальных улучшений

Выберем произвольный маршрут:

Нач. путь	1	2	3	4	5	6	1	Сумма
Значения	9	15	55	49	37	12		177
Путь	1	3	2	4	5	6	1
Значения	8	12	40	49	37	12		158
Путь	1	2	4	3	5	6	1
Значения	9	40	40	39	37	12		177
Путь	1	2	3	5	4	6	1
Значения	9	15	39	39	62	12		176
Путь	1	2	3	4	6	5	1
Значения	9	15	55	62	36	37		214
Путь	1	2	3	4	5	1	6
Значения	9	15	55	49	37	13		178
В обрат	1	6	5	4	3	2	1
Значения	13	36	39	40	12	7		147

Минимальный маршрут на предыдущем шаге:

Нач. путь	1	6	5	4	3	2	1	Сумма
Значения	13	36	39	40	12	7		147
Путь	1	5	6	4	3	2	1
Значения	47	37	44	40	12	7		187
Путь	1	6	4	5	3	2	1
Значения	13	44	49	35	12	7		160
Путь	1	6	5	3	4	2	1
Значения	13	36	35	55	29	7		175
Путь	1	6	5	4	2	3	1
Значения	13	36	39	29	15	8		140
Путь	1	6	5	4	3	1	2
Значения	13	36	39	40	8	9		145
В обрат	1	2	3	4	5	6	1
Значения	9	15	55	49	37	12		177

Минимальный маршрут на предыдущем шаге:

Нач. путь	1	6	5	4	3	1	2	Сумма
Значения	13	36	39	40	8	9		145
Путь	1	5	6	4	3	2	1
Значения	47	37	44	40	12	7		187
Путь	1	6	4	5	3	2	1
Значения	13	44	49	35	12	7		160
Путь	1	6	5	3	4	2	1
Значения	13	36	35	55	29	7		175
Путь	1	6	5	4	1	3	1
Значения	13	36	39	35	8	8		139
Путь	1	6	5	4	3	2	1
Значения	13	36	39	40	12	7		147
В обрат	2	1	3	4	5	6	1
Значения	7	8	55	49	37	12		168

Ответ: Минимальный маршрут

1

6

5

4

3

1

2

= 145

Страница 13 из 13