Практикум по дисциплине «Дискретная математика»



бет23/25
Дата10.01.2020
өлшемі0,98 Mb.
#55624
түріПрактикум
1   ...   17   18   19   20   21   22   23   24   25
Байланысты:
[ZHitnikova N.I.] Teoriya grafov. Praktikum(z-lib.org)


Матрица С1,1,1,1

Матрица С1,1,1,1 после приведения


Получаем для оценочной функции .

Для множества матрица такова:




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 после приведения


Для оценочной функции .

Получилось, что для дальнейшей разработки можно брать любое из множеств и . Но в первом случае уже получена матрица размером 22. Её нулевые клетки дают те дуги, которые с найденными ранее составляют обход коммивояжёра, причём вес этого обхода равен значению оценочной функции – 18. Вот этот обход:

(1,4)(4,3) (3,5) (5,2) (2,1) или 143521



Найденный путь коммивояжёра является оптимальным, потому что значения оценочной функции на всех оборванных ветках (на границах) больше либо равны стоимости этого пути. Возможно, что оптимальный цикл будет не единственным. При ином варианте выборов по ходу разбиений можно было получить и другой оптимальный путь коммивояжёра, однако стоимость этих путей будет одинакова.

Достарыңызбен бөлісу:
1   ...   17   18   19   20   21   22   23   24   25




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет