Задача коммивояжера

И все приведенные выше алгоритмы являются «жадными».

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

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

 

3. МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

 

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

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

(3.1)

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

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

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

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

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

 где                   (3.2)

         (3.3)

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

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

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

    (3.4.)

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

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

Следовательно, для тех  переходов, для которых С_ij² =0, мы будем иметь снова оценку l^*≥d₀. Естественно ожидать, что кратчайший путь содержит один из таких переходов — примем это соображение в качестве рабочей гипотезы. Рассмотрим один из переходов, для которого С_ij² =0, и обозначим через множество всех тех путей, которые не содержат перехода из i в j.

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

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

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

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

   (3.5)

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

               (3.6)

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

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

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

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

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

N -1 > 2.

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

                      (3.7)

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

   (3.3)

Введем понятие стандартной  операции, которую мы будем обозначать символом:

Этим термином мы назовем  процедуру разбиения произвольного  множества вариантов Ω с приведенной  матрицей N – п-го порядка С ⁽ⁿ⁺²⁾ и оценкой dω на два множества. Одно из этих множеств состоит из всех тех путей, которые содержат переход из города номер s в город номер l и имеют нижнюю оценку d . Другое множество состоит из всех путей, не содержащих этого перехода и имеющих в качестве нижней оценки число d_k. Стандартную операцию можно представить в форме следующей блок-схемы:

        (3.4)

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

Предположим, что d₁ < d₂;

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

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

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

            (3.8)

Затем в матрице С ⁽³⁾ вычеркиваем строку номера i₁ и столбец номера j₁, полагаем:

и над полученной матрицей совершаем операцию приведения. В  результате мы найдем новые константы  приведения. Их сумму обозначим через d^(II) и в заключение находим оценку d₁₁ для элементов множества II₁₁.

Если ls  II₁₁, то

             (3.9)

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

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

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

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

 

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

 

ЗАКЛЮЧЕНИЕ

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

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

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

Задача о коммивояжере имеет множество обобщений и  методы её решения в различных  проявлениях используются на практике.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ:

 

В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования.,1986 г.

Ф. А. Новиков Дискретная математика для программистов Санкт-Петербург, Питер, 2001, 304 с ил. 8. Приложения

Моисеев Н.Н. Методы оптимизации: Моисеев Н.Н., Иванилова Ю.П., Столярова  Е.М.-М., 1978, 352 с;

 Черноусько Ф.Л. Вариационные  задачи механики и управления: Численные методы/ Черноусько Ф.Л., Баничук Н.В.-М.,1973;

http://www.bestreferat.ru/referat-219032.html