6.2. Алгоритм поиска, использующий дерево решений

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

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

Пример. В качестве примера возьмем полный граф с 6 вершинами из работы Део и Хакими [13] со следующей матрицей весов:

С помощью метода гл. 7 легко найти кратчайший остов этого графа (без ограничений на он показан на рис. 10.10 (а). Из этого рисунка видно, что а так как нам нужен кратчайший остов, для которого то можно сказать, что в окончательном ответе должно отсутствовать по крайней мере одно из ребер (2,1), (2,6) или (2,5). Таким образом, решение первоначальной задачи является решением по крайней мере одной из следующих трех частных задач, изображаемых узлами дерева решений на рис. 10.11. На этом рисунке узел А представляет первоначальную задачу, а узлы отвечают задачам, матрицы весов которых те же самые, что и матрица весов задачи А, но только ребрам (2,1), (2,6) или (2,5) соответственно приписан бесконечный вес.

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

Найдем теперь кратчайшие остовы и соответствующие узлам Результаты изображены соответственно на рис. 10.10 (б), (в) и (г); веса этих остовов указаны вблизи узлов.

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

Рис. 10.10. Кратчайшие остовы в процессе поиска.

Рис. 10.11. Поиск с деревом решений.

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

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

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

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

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

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

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

Доказательство. Каждая гамильтонова цепь относится к одной из следующих категорий:

(1) не совпадают ни с одной из ее концевых вершин;

(2) одной из ее концевых вершин является или или

(3) одной концевой вершиной является а другой Вес гамильтоновой цепи с матрицей весов С больше веса этой же цепи с матрицей С на величину:

Так как к превосходит вес любой гамильтоновой цепи, то вес (для матрицы С) самой длинной гамильтоновой цепи категории

(3) меньше, чем вес самой короткой гамильтоновой цепи категории (2), а вес самой длинной гамильтоновой цепи категории (2) меньше, чем вес самой короткой цепи категории (1). Таким образом, решение задачи (а) с матрицей весов С даст кратчайшую

гамильтонову цепь категории (3), т. е. она будет решением задачи

(б) с матрицей весов С. Это доказывает теорему.

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