Получаем для оценочной функции  .
Для множества  матрица такова:
1
|
2
|
5
|
|
2
|
|
|
1
|
3
|
|
0
|
0
|
5
|
0
|
1
|
|
|
|
1
|
2
|
5
|
2
|
|
|
0
|
3
|
|
0
|
0
|
5
|
0
|
1
|
|
|
Матрица С1,1,1,2
|
Матрица С1,1,1,2 после приведения
|
Для оценочной функции  .
Получилось, что для дальнейшей разработки можно брать любое из множеств  и . Но в первом случае уже получена матрица размером 22. Её нулевые клетки дают те дуги, которые с найденными ранее составляют обход коммивояжёра, причём вес этого обхода равен значению оценочной функции – 18. Вот этот обход:
(1,4)(4,3) (3,5) (5,2) (2,1) или 143521
Найденный путь коммивояжёра является оптимальным, потому что значения оценочной функции на всех оборванных ветках (на границах) больше либо равны стоимости этого пути. Возможно, что оптимальный цикл будет не единственным. При ином варианте выборов по ходу разбиений можно было получить и другой оптимальный путь коммивояжёра, однако стоимость этих путей будет одинакова.
Достарыңызбен бөлісу: |
