Метод ветвей и границ

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

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

Функция f(x_i, x_j) принимает конечное число значений с_ij, которые мы можем представить в виде таблицы (Рисунок 5.1). Предположим, что мы выбрали некоторый путь S_s. Его длина будет равна

(5.1)

причем сумма (5.1) распространена по i, j так, что каждый из индексов встречается в ней один и только один раз. Величины с_ij с двумя одинаковыми индексами мы приняли равными ∞.

Так как в каждый из вариантов s входит только один элемент из каждой строки и столбца, то мы можем проделать следующую операцию, которая здесь называется приведением матрицы. Обозначим через h_i наименьший элемент из строки номера i и построим новую матрицу С⁽¹⁾ с элементами

Матрица С⁽¹⁾ определяет новую задачу коммивояжера, которая, однако, в качестве оптимальной будет иметь ту же последовательность городов. Между величинами l_s и l_s⁽¹⁾ будет существовать, очевидно, следующая связь:

Заметим, что в каждой из строк матрицы С⁽¹⁾ будет теперь, по крайней мере, один нулевой элемент. Далее обозначим через g_j наименьший элемент матрицы С⁽¹⁾, лежащий в столбце номера j, и построим новую матрицу С⁽² ⁾ с элементами

Величины h_i и g_j называются константами приведения. Оптимальная последовательность городов для задачи коммивояжера с матрицей С⁽²⁾ будет, очевидно, такой же, как и для исходной задачи, а длины пути для варианта номера s в обоих задачах будут связаны между собой равенством

(5.2)

где

(5. 3)

т. Е. d₀ равна сумме констант приведения.

Обозначим через l * решение задачи коммивояжера,т.е.

где минимум берется по всем вариантам s, удовлетворяющим условию (α) Тогда величина d₀ будет простейшей нижней оценкой решения:

(5.4)

Будем рассматривать теперь задачу коммивояжера с матрицей С⁽²⁾ которую мы будем называть приведенной матрицей.

Рассмотрим путь, содержащий непосредственный переход из города номера i в город номера j, тогда для пути s, содержащего этот переход, мы будем иметь, очевидно, следующую нижнюю оценку:

Следовательно, для тех переходов, для которых = 0, мы будем иметь снова оценку (5.4). Естественно ожидать, что кратчайший путь содержит один из таких переходов — примем это соображение в качестве рабочей гипотезы. Рассмотрим один из переходов, для которого =0, и обозначим через множество всех тех путей, которые не содержат перехода из i в j.

Так как из города i мы должны куда-то выйти, то множество содержит один из переходов i→k, где k ≠ j; так как в город номера j мы должны прийти, то множество содержит переход m → j, где т ≠ i.

Следовательно, некоторый путь l_s из множества (ij), содержащий переходы i→k и m → j, будет иметь следующую нижнюю оценку:

Обозначим через

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

(5.5)

Мы предполагаем исключить некоторое множество вариантов , поэтому мы заинтересованы выбрать такой переход i → j, для которого оценка (5.5) была бы самой высокой. Другими словами, среди нулевых элементов матрицы С⁽²⁾ выберем тот, для которого максимально. Это число обозначим через Таким образом, все множество возможных вариантов мы разбили на два множества I₁ и I₂. Для путей из множества I₁, мы имеем оценку (5.4). Для путей из множества I₂ оценка будет следующей:

(5.6)

Рассмотрим теперь множество I₁и матрицу С ⁽²⁾. Так как все пути, принадлежащие этому множеству, содержат переход i → j, то для егоисследования нам достаточно рассмотреть задачу коммивояжера, в которой города номеров i и j совпадают. Размерность этой задачи будет уже равна N – 1, а ее матрица получится из матрицы С⁽²⁾ вычеркиванием столбца номера j и строки но мера i.

Поскольку i → j невозможен, то элемент принимаем равным бесконечности.

Рассмотрим случай N=3 (Рисунок 5.2, а), и предположим, что мы рассматриваем тот вариант, который содержит переход 3 → 2. Тогда задача коммивояжера после вычеркивания третьей строки и второго столбца вырождается в тривиальную. Ее матрица изображена на рисунке 5.2, в. В этом случае мы имеем единственный путь, и его длина будет, очевидно, равна сумме

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

Пусть теперь N >3. После вычеркивания мы получим матрицу порядок

N -1 > 2.

С этой матрицей (N — 1)- гопорядка совершим процеXXXурру приведения. Матрицу, которую таким образом получим, обозначим через С⁽³⁾, а через d⁽¹⁾ – сумму ее констант приведения. Тогда для l_s I₁, мы будем иметь оценку

(5.7)

На этом первый шаг алгоритма закончен. В результате одного шага мы разбили множество всех возможных вариантов на два множества I₁ и I₂ и для путей, принадлежащих этим множествам, мы получили оценки (5.7) и (5.6) (Рисунок 5.3)

Рис.5.3

Введем понятие стандартной операции, которую мы будем обозначать символом Этим термином мы назовем процедуру разбиения произвольного множества вариантов Ω с приведенной матрицей N – п- гопорядка С⁽ⁿ^{+ 2)} и оценкой d_ω на два множества. Одно из этих множеств состоит из всех тех путей, которые содержат переход из города номер s в город номер l и имеют нижнюю оценку d. Другое множество состоит из всех путей, не содержащих этого перехода и имеющих в качестве нижней оценки число d_k. Стандартную операцию можно представить в форме следующей блок-схемы (см. Рисунок 5.4).

задача коммивояжер решение алгоритм обобщение

Рисунок 5.4

Итак, первый шаг метода ветвей и границ состоит в проведении стандартной операции над исходным множеством Ω. На следующем шаге мы продолжаем развивать дерево возможных вариантов. Сначала мы сравниваем две оценки d₁ и d₂ и для последующего анализа выбираем то из множеств I₁ или I₂, для которого соответствующая оценка меньше.

Предположим, что

d₁ < d₂;

тогда над множеством I₁ с матрицей С⁽³ ⁾ мы совершим стандартную операцию. В результате мы разобьем множество возможных вариантов I ₁ на два подмножества II₁₁и II₁₂, первое из которых содержит некоторый переход i₁ → j₁ а другое содержит все пути, не имеющие непосредственною перехода из города i₁ в город j₁. Еще раз повторим рассмотренную выше процедуру: для каждого из нулевых элементов матрицы С⁽³ ⁾ построим число

Определим значение

и элемент матрицы С⁽³ ⁾, для которого достигается это значение. Если l_s II₁₂, то

(5.8)

Затем в матрице С ⁽³⁾ вычеркиваем строку номера i₁ и столбец номера j₁, полагаем и над полученной матрицей совершаем операцию приведения. В результате мы найдем новые константы приведения. Их сумму обозначим через d⁽^II⁾ и в заключение находим оценку d₁₁ для элементов множества II₁₁.

Если l_s II₁₁, то

(5.9)

На этом второй шаг алгоритма ветвей и границ закончен. Мы разбили множество вариантов I₁ на два множества, II₁₁ и II₁₂, и для элементов этих множеств получили нижние оценки (5.9) и (5.8), соответственно.

Теперь мы должны сравнить оценку (5.9) с оценкой (5.6) для элементов множества I₂, которое мы исключили из рассмотрения на предыдущем шаге. Если окажется, что d₂ > d₁₁,

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

Если окажется, что d₁₁ > d₂, то множеством вариантов с оптимальной нижней оценкой будет множество I₂. Другими словами, теперь будем предполагать, что наиболее короткий путь содержится среди элементов множества I₂ — множества всех вариантов, не содержащих перехода i → j. Следовательно, матрица, характеризующая это множество, получается из матрицы С ⁽²⁾ заменой величины на ∞. Над этим множеством мы производим стандартную операцию и разбиваем его на два множества II₂₁ и II₂₂ с оценками d₂₁ и d₂₂, соответственно. Одновременно мы выделяем переход k→l, который содержит все варианты множества II₂₁. Затем мы снова сравниваем все оценки d₁₁, d₁₂, d₂₁ и d₂₂ и выбираем то из множеств, для которого оценка будет наименьшей. Над выбранным множеством совершаем стандартную операцию и т. Д. Так мы продолжаем до тех пор, пока очередная матрица не будет иметь порядок (2x2). В этом случае, как мы видели, расчет заканчивается — мы получаем задачу коммивояжера для двух городов (Рисунок 5.5), и длина единственного маршрута будет

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