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

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

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

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

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

рез j(), сопоставим множеству .

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

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

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

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

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

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

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

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

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

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

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