7.4. Лучшие границы для дерева поиска

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

Определим стягивание как замену цикла единственной вершиной. Полученный граф содержит вершин . В качестве матрицы весов нового графа берется -матрица с элементами вида

где окончательная матрица относительных весов, полученная в конце решения задачи венгерским (например) методом (см. гл. 12).

(кликните для просмотра скана)

На рис. 10.20 (а), например,

Теперь второе решение задачи о назначениях в случае задачи с матрицей все еще может содержать циклы, в качестве вершин которых выступают предыдущие циклы. Рис. 10.20 (б) показывает один из возможных способов образования новых циклов где их общее число (на рис. Эти циклы опять могут быть стянуты в вершины и дать новую задачу с новой матрицей весов вычисленной так же, как и в (10.19), т. е.

где множества являются объединениями всех множеств образующих «частные» циклы, и где матрица относительных весов, полученная в конце решения второй задачи о назначениях.

Решение задачи о назначениях для нового, дважды стянутого, графа все еще может содержать циклы, и итерационный процесс решения — стягивания можно продолжать до тех пор, пока задача не сведется к единственной вершине.

Определим компрессию как преобразование матрицы, не удовлетворяющей аксиоме треугольника в метрическом пространстве, в матрицу, удовлетворяющую этой аксиоме. Таким образом, для компрессии матрицы нужно заменить каждый элемент для которого

элементом и продолжать эту замену до тех пор, пока для всякого к не будут справедливы неравенства

Теорема 5. Сумма значений решений задач о назначениях, полученных во время процесса «решение — стягивание — компрессия» осуществляемого вплоть до момента, когда «стянутая» задача будет содержать единственную точку), является точной нижней границей для задачи коммивояжера.

Доказательство. В гл. 12 показано, что элемент в матрице относительных весов, полученной в конце решения задачи о назначениях, дает нижнюю границу для дополнительного веса, который получается из-за включения дуги в решение.

Рассмотрим цикл полученный] в конце решения первой задачи о назначениях. Любой гамильтонов цикл, проходящий

через все вершин, будет иметь по крайней мере две дуги (одну направленную внутрь цикла другую — наружу), инцидентные вершинам, не лежащим в и «приходящие» в одну или более вершин из Число таких дуг будет, очевидно, четным.

Рис. 10.21. Преобразование гамильтоновых циклов при стягивании. (а) Решение задачи о назначениях, (б) Гамильтонов цикл.

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

Если теперь использовать неравенство треугольника, то получим

и, следовательно, назначение из рис. 10.22 (в котором дуги заменены дугой имеет значение, не превосходящее величины назначения из рис. Так как назначение на рис. 10.22 имеет по две дуги, инцидентны? каждой вершине, и решение задачи о назначениях для стянутогс графа имеет меньший вес назначения, то значение решения задачи о назначениях, скажем является нижней границей для

величины назначения на рис. для значения приращения веса, которое было бы необходимо для объединения вместе различных циклов.

Рис. 10.22. Назначение, соответствующее рис. 10.21 (б), с двумя дугами в каждой вершине.

Очевидно, что поскольку граф назначения, полученный с помощью любого гамильтонова цикла, содержит после первого стягивания (т. е. в случае назначения, соответствующего рис. 10.21 (б)) эйлеров цикл, то его всегда можно преобразовать в граф с меньшим (или равным) весом, в котором каждой вершине индицентны только две дуги. Это делается с помощью замены цепи, образованной дугами, ведущими из одной вершины в другую, единственной дугой между этими вершинами (как было продемонстрировано выше).

Если, с другой стороны, матрица относительных весов не удовлетворяет условию треугольника, то соотношение (10.21) может быть не выполнено. В этом случае матрица должна быть сначала подвергнута компрессии. Значение решения задачи о назначениях с компрессированной матрицей следует взять тогда в качестве нижней границы величины приращения веса, что необходимо при объединении циклов. Это так, ибо компрессия матрицы может лишь уменьшить или оставить без изменения вес любого назначения для первоначальной матрицы.

Аналогично вес решения задачи о назначениях после второго стягивания является нижней границей веса связываемых циклов, получаемых при этом стягивании, и так далее для третьего, четвертого и остальных стягиваний. Поэтому величина

где - значение начального решения задачи о назначениях с начальной матрицей С, а к — число стягиваний, необходимых для преобразования графа задачи в единственную вершину, равное весу решения задачи коммивояжера. Теорема доказана.

Вообще здесь следует отметить, что даже если начальная матрица весов удовлетворяет условию треугольника, то последующие матрицы относительных весов могут не удовлетворять этому условию и на каком-то этапе может потребоваться компрессия.

Пример вычисления границы

Рассмотрим задачу коммивояжера с 10 вершинами, матрица весов которой симметрична и приведена в табл. 10.3.

Решение начальной задачи о назначениях дает величину Результирующая матрица относительных весов дана в табл. 10.4, а решение дается графом на рис. 10.23.

Рис. 10.23. Первое решение задачи о назначениях.

Рис. 10.24. Решение после первого стягивания.

Рис. 10.25. Решение после второго стягивания.

Стягивание графа из рис. 10.23 дает граф с 4 вершинами, матрица весов которого может быть вычислена по (10.19), и она дана в табл. 10.5 (а). Эта матрица весов не удовлетворяет условию треугольника и поэтому подвергается компрессии. Результат дан в табл. 10.5 (б).

Решение задачи о назначениях с матрицей из табл. 10.5 (б) дает величину Результирующая матрица относительных весов дана в табл 10.6, а решение задачи о назначениях дается графом на рис. 10.24.

(см. скан)

(см. скан)

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

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

Сравнив ее со значением оптимального решения задачи коммивояжера, равного 216, получим ошибку в в то время как использование в качестве нижней границы величины дает ошибку в Хотя настоящая нижняя граница и не является в общем случае такой близкой, как в приведенном примере, но результаты [8] показывают, что эта граница в среднем значительно лучше, чем

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

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