01 (Лекции по вычислительной математике), страница 2
Описание файла
Документ из архива "Лекции по вычислительной математике", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "01"
Текст 2 страницы из документа "01"
рез j(
), сопоставим множеству .
Теперь выберем между множествами 
и то, на
котором минимальна функция j (т.е. то из множеств, которому
соответствует меньшее из чисел j( ) и j( ).
Заметим теперь, что в проведенных рассуждениях исполь-зовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было вы-делено определенное ребро графа и были построены новые
матрицы, к которым, конечно, можно все то же самое применить.
При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: пе-ред тем, как в очередной матрице вычеркнуть строку и столбец,
в ней надо заменить на ¥ числа во всех тех клетках, которые со-ответвуют ребрам, заведомо не принадлежащим тем гамильто-новым циклам, которые проходят через уже отобранные ранее ребра; эту довольно трудную фразу мы еще не раз рассмотрим в
следующей лекции на конкретном примере.
К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это воз-можно.
Доказывается, что в результате получится множество, со-стоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказы-ваются выполненными все условия, обсуждавшиеся при описа-нии метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.
Бельский Аркадий Александрович. Вычислительная математика. Часть 2. Лекция 1
