Реферат: Лекции по вычислительной математике

весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

Пусть конкретный состав множества вершин и

- весовая матрица данного орграфа, т.е.

,

причем для любого .

Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного

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

Введем некоторые термины. Пусть имеется некоторая чис-

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

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

привести матрицу по столбцам .

Наконец, слова привести матрицу означают, что матрица

сначала приводится по строкам, а потом приводится по столб-цам.

Весом элемента матрицы называют сумму констант приве-

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

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

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

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

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

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

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

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

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

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

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

делим множество G на две части: на часть , состоящую из

обходов, которые проходят через ребро , и на часть ,

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

Сопоставим множеству следующую матрицу M _{1 ,1} : в

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