Алгоритм самой близкой вставки

1. Выбрать любую вершину. Выбрать инцидентное вершине ребро е с самым маленьким весом, и пусть С является последовательностью ребер: е, е. С - стартовый "цикл", (хотя строго говоря это не цикл, так как данная последовательность содержит повторяющееся ребро).

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

3. Увеличении цикла в результате включения выбранной вершины V₀. Чтобы решить, как вставить V₀, следует рассмотреть все пары V₁ , V₂ смежных вершин цикла С и выбрать такую пару, для которой выражение:

I = d₁₀ + d₀₂- d₁₂

является минимальным, где d_ij - обозначает вес ребра, соединяющего V_i и V_j. Это выражение I представляет увеличение полного веса цикла С, после включения в него вершины V₀. Мы увеличиваем цикл С, включая вершину V₀ путем присоединения ребра соединяющего вершины V₁ и V₀, и ребра, соединяющего вершины V₀ и V₂, и удаляя затем ребро соединяющее вершины V₁ и V₂.

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

Пример 5.1. Проиллюстрируем алгоритм ближайшего включения для сети, представленной на рис. 13 (которая удовлетворяет неравенству треугольника). Веса ребер представлены в матрице расстояний, см. табл.9.

Табл. 9. Матрица расстояний d_ij, пример 4

Чтобы выполнить шаг I, мы снача­ла выберем вершину маркированную на рисунке буквой А (мы могли бы, конечно, выбрать любую другую из вершин). Ребро e_AF является ребром, инцидентным вершине А, и имеет самый маленький вес из числа ребер, инцидентных вершине А. Поэтому первый цикл будет: e_AF, e_FA (от вершины А до вершины F и назад к вершине А).

Рис. 13

Ребро с самым маленьким весом, инцидентное вершине А или вершине — F это ребро е_АВ, поэтому вершина В — это первая вершина, которую следует вставить. Самый короткий путь, которым вершина В может быть вставлена в цепь будет: от вершины А до вершины В и назад через вершину F. Это порождает цепь е_АВ, e_BF, e_FA, показанную на рис. 14.

Рис. 14

Вершина, которая является самой близкой к вершине этой цепи — это вершина С, поэтому мы должны найти лучший способ вставить ее. Цены I для трех ребер текущей цепи будут:

I (е_AB) = d_AC + d_CB - d_AB = 9 + 6 - 4 = 11,

I (e_BF) = d_BC + d_CF - d_BF = 6 + 12 - 6 = 12 ,

I (e_FA) = d_FC + d_CA - d_FA = 12 + 9 - 3 = 18.

Мы таким образом увеличиваем цепь путем удаления ребра е_AB и вставляя на его место ребра е_АС, е_CB. Это дает цепь, показанную на рис. 15.

Рис. 15

Повторяя этот процесс дважды, мы увеличиваем цепь, включая сначала вершину D и затем вершину Е. Заключительная цепь, e_AC, e_CD, e_DE, e_EB, e_BF, e_FA, является тре­буемой цепью Гамильтона с полным весом 9 + 5 + 4+ 10+ 6 + 3 = 37.

Этот пример иллюстрирует тот факт, что алгоритм самой близкой вставки может не производить минимальную цепь Гамильтона. Граф действительно имеет единственную минимальную цепь Гамильтона - е_АВ, е_BC, e_CD, e_DE, e_EF, e_FA с полным весом 29.

ЛЕКЦИЯ 6. Сетевое планирование. Задача о кратчайшем сроке.