6.3. Алгоритм штрафования вершин

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

Теорема 3. Если матрица С преобразована в матрицу С так, что

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

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

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

6.3.1. Решение задачи (б)

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

Пример. Рассмотрим полный граф с 10 вершинами, матрица весов которого дается табл. 10.1, и предположим, что мы хотим найти кратчайшую гамильтонову цепь с концевыми вершинами 8 и 9.

Таблица 10.1 (см. скан) Матрица весов примера

В соответствии с теоремой 2 добавим к каждому элементу, стоящему либо в строках 8 и 9, либо в столбцах 8 и 9 таблицы 10.1, достаточно большое число к (скажем, 1000). Получившуюся после этого добавления таблицу назовем результирующей матрицей весов С.

Далее поступаем следующим образом.

Находим кратчайший остов графа Если он окажется гамильтоновой цепью, то задача решена. В рассматриваемом примере кратчайший остов, показанный на рис. 10.12 (а), не является гамильтоновой цепью. Степени вершин 1 и 7 равны 4, а не 2, как это требуется для гамильтоновой цепи. Следуя духу теоремы

3, мы можем «оштрафовать» эти вершины. Допустим, что мы произвольно выбрали малый шаг (скажем, 5 единиц), так что все штрафы кратны ему. (Можно выбрать величину шага равной

1, но это будет неоправдано мало и приведет к увеличению числа требуемых итераций.) Таким образом, если мы решили штрафовать только те вершины, степени которых больше чем 2, то

Заметим, что метод штрафования вершин выбран произвольно и существует много других альтернатив (см. разд. 6.3.4).

Рис. 10.12. Кратчайшие остовы при итерациях со штрафами.

В соответствии с уравнением (10.13) штрафы вершин 1 и 7 равны причем для всех остальных вершин они равны 0. Следуя (10.11), вычислим новую матрицу весов и найдем для нее кратчайший остов. Результат показан на рис. 10.12 (б), из которого видно, что это дерево много ближе к гамильтоновой цепи, поскольку для него вместо в предыдущем случае.

Поступая как и ранее, оштрафуем вершину 6 и положим (Следует заметить, что этот новый штраф добавляется к предыдущей матрице весов, а не к первоначальной матрице С.) Таким образом, штрафы равны для всех остальных вершин. Соответствующий кратчайший остов изображен на рис. 10.12 (в), и для него как и для предыдущего остова. Оштрафуем вершину 7, полагая новый кратчайший остов будет тем же, что и на рис. 10.12 (б). Продолжая далее, штрафуем вершину 6 еще раз, полагая и опять находим кратчайший остов. Результат показан на рис. 10.12 (г), из которого видно, что теперь это гамильтонова цепь и, следовательно, по теореме 3 — кратчайшая гамильтонова цепь. Вес этой цепи с первоначальной матрицей весов равен 258.

Здесь полезно отметить, что если на некотором этапе получается кратчайший остов, уже встречавшийся ранее, то это не означает, что произошло зацикливание, и любой такой цикл автоматически устраняется при продолжении алгоритма. (Однако, как будет выяснено ниже, сходимость последовательности кратчайших остовов к кратчайшей гамильтоновой цепи не может быть гарантирована без конкретизации выбираемого способа штрафования вершин.) Мы получили кратчайшую гамильтонову цепь с концевыми вершинами 8 и 9 за 5 итераций, включая 5 вычислений кратчайших остовов, в то время как полный перебор содержал бы вычислений матриц весов и сравнений цепей.

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

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

Интересно отметить, что не существует единственного вектора штрафов для которого матрица весов будет преобразовываться так, что кратчайший остов будет и гамильтоновой цепью и, следовательно, кратчайшей такой цепью. В приведенном примере окончательное значение вектора штрафов при первой политике такое: все остальные в то же время при второй политике, принятой, начиная с шага 2, для окончательного вектора штрафов все остальные

6.3.2. Решение задачи (а).

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

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

К множеству X вершин графа добавим еще две вершины, например и образуем новое множество К множеству ребер А графа добавим два множества ребер:

и образуем новое множество Для всех зададим веса а — для ребер и для ребер где две произвольные постоянные.

Теорема 4. Решение задачи (б) для графа с концевыми вершинами является решением задачи (а) для графа

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

6.3.3. Сходимость метода штрафования вершин.

Метод штрафования вершин, описанный выше, был развит Кристофидесом [7] и, в несколько иной форме, примерно в то же время Хелдом и Карпом [18].

Рис. 10.13.

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

Во-первых, в большинстве случаев он сходится (как будет показано ниже, все 33 случайно выбранные задачи были решены

этим методом по крайней мере при одной стратегии наложения штрафов).

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

где вес остова вычисленный для первоначальной матрицы весов.

Если кратчайшая гамильтонова цепь графа, то вес цепи с модифицированной матрицей равен

Так как по определению то разность

является мерой близости дерева к кратчайшей гамильтоновой цепи причем если

Величину можно рассматривать как функцию вектора штрафов Хелд и Карп предложили два метода нахождения штрафов минимизирующих Один основан на технике преобразования столбцов, а второй является методом наискорейшего спуска. (Другой, несколько более общий последовательный подход, основанный на эвристическом поиске, был недавно успешно применен Камерини и др. [4].) Если метод штрафования вершин сходится, то для минимального значения так как для всех другой стороны, как было отмечено выше, метод сходится не всегда, и при отсутствии сходимости минимальное значение величины равно некоторому положительному числу. Совершенно очевидно, что в этом случае величина

дает нижнюю границу веса кратчайшей гамильтоновой цепи. В этом последнем случае получаемая граница является очень точной и может быть использована с большим эффектом [19] в алгоритме поиска, применяющем дерево решений, — в духе того, как это делалось в разд. 6.2.1.

6.3.4. Стратегии наложения штрафов.

Хотя, как уже отмечалось в разд. 6.3.3, существуют два метода [18] для определения последовательности штрафов, вынуждающих кратчайший остов становиться кратчайшей гамильтоновой цепью (если только вообще сходимость возможна), оба эти метода являются слишком изысканными и требуют больших затрат времени. В настоящем разделе мы экспериментально исследуем влияние различных стратегий штрафования вершин на скорость сходимости метода. Для всех 33 случайно выбранных полных графов, использованных для проверки стратегий, по крайней мере одна стратегия приводила к кратчайшей гамильтоновой цепи. Это убеждает нас в том, что, хотя и существуют задачи, в которых алгоритм штрафования вершин не сходится (на самом деле любой связный граф без гамильтонова цикла приводит нас к такой ситуации), но все же в большинстве задач, при составлении которых не старались специально найти контрпримеры, будет иметь место сходимость.

(I) Фиксированные штрафы

(a) Только положительные штрафы

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

(b) Только отрицательные штрафы

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

(c) Положительные и отрицательные штрафы

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

(II) Последовательно уменьшаемые штрафы

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

Было найдено, что в такой ситуации для большинства графов лучший метод состоит в уменьшении ранее наложенного штрафа, так что на следующей итерации для вышеприведенного примера следовало бы оштрафовать вершину на вместо где

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

В численных экспериментах, результаты которых приведены в табл. 10.2, было использовано значение

(III) Вычисляемые штрафы

(а) Только положительные штрафы

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

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

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

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

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

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

(b) Только отрицательные штрафы

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

Значение для данной вершины вычисляется следующим образом. Добавим ребро к дереву Это добавление приведет к замыканию цикла, составленного из ребра вместе с ребрами дерева входящими в цепь от до Пусть множество ребер дерева в цепи от до (исключая последнее ребро, инцидентное будет Если тогда добавить ребро к ребрам и удалить одно какое-либо ребро из то получится другое дерево, в котором степень вершины равна двум. Если, таким образом, накладывается единственный штраф на вершину где

(т. е. равен наименьшему дополнительному весу добавления ребра от к какой-нибудь другой вершине и удаления ребра

(см. скан)

Рис. 10.14. Задача с 24 вершинами, (а) Начальный кратчайший остов, (б) Кратчайший гамильтонов цикл, полученный после 40 итераций с использованием штрафов III(с).

наименьшего веса в цепи от то степень вершины станет равной 2 после единственной итерации.

Если все штрафы накладываются одновременно, то, как и в случае взаимодействие этих штрафов делает невозможным предсказание изменения степеней вершин после одной итерации.

(с) Положительные и отрицательные штрафы

Эта стратегия заключается в наложении штрафов на вершины в соответствии с (III (а)) или (III (b)) в зависимости от того, будет ли или

В таблице 10.2 приводятся результаты и делается сравнение семи стратегий штрафования, описанных выше. Графы в этой таблице были получены случайным выбором точек в квадрате при равномерном распределении, а в качестве весов ребер собралось евклидово расстояние между Таблица дает числа итераций и времена вычислений время в секундах), необходимые для получения ответа. Из этой таблицы видно, что действие всех стратегий штрафования зависит от задачи, хотя можно заметить, что наилучшей является стратегия (III (с)). Используя эту стратегию, можно найти кратчайшую гамильтонову цепь в графе примерно с 60 вершинами менее чем за 15 с.

На рис. 10.14 для некоторого графа с 24 вершинами показаны начальный кратчайший остов и окончательная кратчайшая гамильтонова цепь. Первая и последняя пронумерованные вершины являются отмеченными концевыми вершинами.