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

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

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

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

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

Кроме этого, так как гамильтонов цикл проходит через все вершины:

• можно начинать построение тура с любого ребра;

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

Точное решение S l = 10

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

• из всех пар смежных ребер выбираем ту, которая имеет минимальный вес;

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

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