Лекции по вычислительной математике (стр. 2 из 2)

Приступим теперь к описанию метода ветвей и границ для

решения задачи о коммивояжере.

Первый шаг. Фиксируем множество всех обходов коммиво-

яжера (т.е. всех простых ориентированных остовных циклов). По-

скольку граф - полный, это множество заведомо непусто. Сопо-ставим ему число, которое будет играть роль значения на этом

множестве оценочной функции: это число равно сумме констант

приведения данной матрицы весов ребер графа. Если множест-во всех обходов коммивояжера обозначить через G, то сумму

констант приведения матрицы весов обозначим через j(G). При-веденную матрицу весов данного графа следует запомнить; обо-значим ее через M₁; таким образом, итог первого шага:

множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M₁.

Второй шаг. Выберем в матрице M₁ самый тяжелый нуль; пусть он стоит в клетке

; фиксируем ребро графа и раз-

делим множество G на две части: на часть

, состоящую из

обходов, которые проходят через ребро

, и на часть ,

состоящую из обходов, которые не проходят через ребро

.

Сопоставим множеству

следующую матрицу M_1,1: в

матрице M₁ заменим на ¥ число в клетке

. Затем в получен-ной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M_1,1; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в даль-нейшем через j( ), сопоставим множеству .

Теперь множеству

тоже сопоставим некую матрицу

M_1,2. Для этого в матрице M₁ заменим на ¥ число в клетке

и полученную в результате матрицу приведем. Сумму констант

приведения запомним, а полученную матрицу обозначим через M_1,2. Прибавим запомненную сумму констант приведения к

числу j(G) и полученное число, обозначаемое в дальнейшем че-

рез j(

), сопоставим множеству .

Теперь выберем между множествами

и то, на

котором минимальна функция j (т.е. то из множеств, которому

соответствует меньшее из чисел j(

) и j( ).

Заметим теперь, что в проведенных рассуждениях исполь-зовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было вы-делено определенное ребро графа и были построены новые

матрицы, к которым, конечно, можно все то же самое применить.

При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: пе-ред тем, как в очередной матрице вычеркнуть строку и столбец,

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

следующей лекции на конкретном примере.

К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это воз-можно.

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

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.