Таблица 10.3

Начальная матрица весов

Таблица 10.4 Матрица относительных весов

Таблица 10.5а

Решение задачи о назначениях

Матрица весов

Таблица 10.56

Таблица 10.в

Таблица 10.7

Стягивание графа из рис. 10.24 дает граф с 2 вершинами, матрица весов которого (вычисленная по (10.20)) дана в табл. 10.7 (Эта тривиальная (2 X 2)-матрица не должна подвергаться компрессии, так как она удовлетворяет условию треугольника.)

Решение задачи о назначениях с матрицей из табл. 10.7 имеет значение V (АР) = 10, а само решение дается графом на рис. 10.25, который переходит в единственную вершину после следуюш,его сжатия. Таким образом, нижняя граница значения для задачи коммивояжера с матрицей из табл. 10.3 равна

L = V (APo)+V{APi) + V [APi) = 214.

Сравнив ее со значением оптимального решения задачи коммивояжера, равного 216, получим ошибку в 0,93 %, в то время как использование в качестве нижней границы величины V (АРоУ дает ошибку в 14,8 %. Хотя настояш,ая нижняя граница и не является в обш,ем случае такой близкой, как в приведенном примере, но результаты [8] показывают, что эта граница в среднем значительно лучше, чем V {АРо).

Время вычисления границы в задаче коммивояжера в среднем только на 9% больше времени, требуемого для решения задачи о назначениях с той же самой матрицей весов. Время вычисления при решении задачи о назначениях с использованием венгерского метода оценивается как кп (см. гл. 12), где к - некоторая постоянная, an - порядок матрицы. Самый плохой случай при вычислении границы (что касается времени вычисления) возникает тогда, когда все циклы при каждом стягивании содержат только по две вершины. В этом случае обш,ее время вычисления при решении задачи о назначениях таково:

кп + к(.У + к (-J)-f... -f-A;re3 1,143 кп\ (10.23)

Из (10.23) видно, что в худшем случае требуемое время для вычисления предложенной границы в задаче коммивояжера только на 14,3% больше, чем время, требуемое для решения задачи о назначениях того же самого размера. (Здесь следует заметить, что время, необходимое для выполнения той части процесса, которая связана с стягиванием и компрессией , оценивается как п^.)

7.5. Пример из раздела 7.2 с ул}чшенной границей

Рассмотрим еш,е раз пример из раздела 7.2, используя улучшенную границу, описанную выше (вместо использования в качестве такой границы просто значения решения задачи о назначениях). Граница, соответствуюш,ая начальной задаче с матрицей весов Сд (разд. 7.2), должна тогда быть V (АРо) + F(4Pi)-f 232-f 13=245. (Необходимо второе стягивание, и решение новой задачи о назначениях равно 13.) Подзадачи В, С ш D получены, как и раньше,