next up previous
Next: Алгоритм Up: Элементы теории Previous: Нижняя оценка стоимости оптимального

Достаточный признак оптимальности

Теперь можно сформулировать достаточный и легко вычисляемый признак оптимальности обхода:

Если подграф $ \mathbf{\Gamma_{MST}}$ является линейным графом и максимальная стоимость ребра $ \mathbf{s_{MSTMax}}$ из этого графа равна стоимости ребра, замыкающего обход, то есть соединяющего концы линейного графа, то этот замкнутый обход будет оптимальным обходом первоначальной $ \mathbf{TSP}$ - задачи.

Доказательство очевидно из линейности $ \mathbf{MST}$ и предыдущих рассуждений.


Бродников А.П. 2006-11-05
Используются технологии uCoz