Пусть имеется некоторая числовая матрица

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

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

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

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

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

Опишем  метод  ветвей и границ для решения задачи о коммивояжере.

            Первый шаг. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф — полный, это множество заведомо непустое. Сопоставим ему число, которое будет играть роль значения на этом  множестве оценочной функции: это число равно сумме констант  приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким образом, итог первого шага:

Ссылка на основную публикацию
Adblock detector