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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: ответы 9 класс, матершинные частушки
| Добавил(а) на сайт: Коченков.

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

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

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

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

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

Второй шаг. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в клетке [pic]; фиксируем ребро графа [pic] и раз- делим множество ( на две части: на часть [pic], состоящую из обходов, которые проходят через ребро [pic], и на часть [pic], состоящую из обходов, которые не проходят через ребро [pic].
Сопоставим множеству [pic] следующую матрицу M1,1: в матрице M1 заменим на ( число в клетке [pic]. Затем в получен-ной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к ((() и результат, обозначаемый в даль-нейшем через
(([pic]), сопоставим множеству [pic].

Теперь множеству [pic] тоже сопоставим некую матрицу
M1,2. Для этого в матрице M1 заменим на ( число в клетке [pic] и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу ((() и полученное число, обозначаемое в дальнейшем че- рез (([pic]), сопоставим множеству [pic].

Теперь выберем между множествами [pic] и [pic] то, на котором минимальна функция ( (т.е. то из множеств, которому соответствует меньшее из чисел (([pic]) и (([pic]).

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

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

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