Реферат: Задача о коммивояжере

Метод 3: "Комбинированный".

Рассчитываются оценки по предыдущим двум методам и из них выбирается максимальная, то есть худший прогноз для данной вершины. Программная реализация - VHCOUNT. H_12

Метод 4: "Венгерский метод".

Программная реализация - SOLUTION. DOWNLEV

Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем формируется матрица из элементов незанятых строк и столбцов размерностью M´M, где M = N ‑ количество пройденных городов. Эта матрица передается венгерскому алгоритму, который описан ниже (Программная реализация - VENGRSOL. CENTRAL_CONTROL):

Предварительный этап. (В программе реализован процедурой Begin_Set)

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

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

(К+1)-я итерация.

Допустим, что К-я итерация уже проведена и в результате получена некоторая матрица. Если в матрице N нулей со звездочкой (*), то процесс решения заканчивается. Если же в матрице нулей со звездочкой меньше N, то переходим к (К+1)-й итерации. (В программе проверяется процедурой Central_Control)

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться третий этап. Перед началом итерации значком (+) выделяют столбцы матрицы, содержащие нули со звездочкой (0*). (В программе реализовано процедурой Make_Label_Col)

ПЕРВЫЙ ЭТАП.

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

Если же невыделенный нуль в матрице обнаружен, то возможен один из двух случаев :

(Проверка случая производится в процедуре Central_Control)

В первом случае невыделенный нуль отмечают штрихом ( ' ) и выделяют строку, в которой он содержится, постановкой справа от нее значком (+). Затем уничтожают знак (+) над столбцом, содержащим нуль со звездочкой (0*).

Далее просматривают этот столбец, отыскивают в нем невыделенный нуль (поиск идет только среди непомеченных строк), непомеченный звездочкой, отмечают его штрихом и выделяют строку, содержащую такой нуль. Затем просматривают эту строку, отыскивая в ней нуль со звездочкой (0*). Этот процесс за конечное число шагов заканчивается одним из следующих исходов :

* все нули матрицы выделены, то есть находятся в выделенных строках и столбцах. При этом переходят к третьему этапу;

* имеется невыделенный нуль в строке, где нет нуля со звездочкой. В этом случае переходят ко второму этапу, отметив последний по порядку нуль штрихом ( ' ).

(В программе реализовано процедурой Find_Zero и подпроцедурами Find_Zero_in_Col и Find_Zero_in_Line; выбор случая производится процедурой Central_Control)

ВТОРОЙ ЭТАП.

Строят следующую цепочку из элементов матрицы : исходный нуль со штрихом (0' ), нуль со звездочкой (0*), расположенный в одном столбце с первым, нуль со штрихом (0' ), расположенный в одной строке с предшествующим нулем со звездочкой (0*), и так далее. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и так далее. (В программе реализовано процедурой Chain подпроцедурами Find_Link_in_Col и Find_Link_in_Line, а также внутренней подпроцедурой процедуры Chain процедурой NewLink)

Далее над элементами цепочки, стоящими на нечетных местах (0' ), ставим звездочки, уничтожая их над четными элементами (0*). (В программе реализовано процедурой Change_Chain). Затем уничтожаем все штрихи над элементами матрицы и знаки +. (В программе реализовано процедурой Erase_Label) При этом количество независимых нулей будет увеличено на единицу. (К+1)-я итерация закончена.

ТРЕТИЙ ЭТАП.

К этому этапу переходят после первого, если все нули матрицы выделены, то есть находятся в выделенных строках и столбцах. В таком случае среди невыделенных элементов матрицы выбирают минимальный элемент и обозначают его H (H>0). Далее вычитают H из всех элементов матрицы, стоящих в невыделенных строках и прибавляют ко всем элементам матрицам, расположенным в выделенных столбцах. Получают новую матрицу, эквивалентную исходной. (В программе реализовано процедурами Find_Min_No_Label (нахождение минимального элемента) и Plus_Minus (вычитание и прибавление)).

Поскольку среди невыделенных элементов появятся новые нули (согласно определению), переходят к первому этапу, рассматривая преобразованную матрицу. Завершив первый этап, либо переходят ко второму, либо вновь к третьему этапу, если все нули матрицы оказываются выделенными. (В программе выбор реализован в процедуре Central_Control ).

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

Теперь можно перейти к рассмотрению методов получения верхней оценки:

Метод 1: "По возрастанию номеров".