Задача о коммивояжере
Страница 2
.
Так как
,
то N × R £ (N -1), где R<N, R ¹ 0.
Следовательно, не существует замкнутого подцикла с числом городов меньшим, чем N.
Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяют условию (4). При всех Xi j (j-й город не посещается после i-го) в (4) имеем Ui - Uj £ N - 1, что допустимо в силу произвольных Ui и Uj.
Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xi j = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R + 1, тогда из (4) имеем:
Ui - Uj + N × Xi j £ R - (R - 1) + N = N - 1
Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А следовательно, модель (1-4) описывает задачу о коммивояжере.
Описание программной реализации алгоритма
В программе реализован классический вариант метода ветвей и границ, то есть алгоритм решения следующий:
1. Все множество разбивается на N-1 подмножеств, каждое из которых оценивается верхней и нижней оценками.
2. Производится отсев неоптимальных множеств по следующему критерию: если нижняя оценка (решение релаксированной задачи) больше минимальной из верхних оценок (решений нерелаксированной задачи), то множество считается очевидно неоптимальным и отсекается, иначе остается до следующей итерации.
3. Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество равное размерность исходной матрицы минус количество уже пройденных (фиксированных для данного множества) городов.
4. Находятся минимальные верхняя и нижняя оценка. Если они равны и достигнуты на одном и том же множестве, то это значит, что получено оптимальное решение и алгоритм заканчивает работу, иначе возврат к шагу 2.
При этом предусмотрена возможность смены направления критерия, то есть возможность решения задачи на максимум.
Наибольший выбор программа предоставляет в шаге 3, где реализовано четыре метода расчета нижней оценки множества и три метода расчета верхней оценки множества. Сначала рассмотрим методы нахождения нижней оценки, то есть решения релаксированной задачи:
Метод 1: "Из каждого города".
Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем в каждой строке матрицы, в которой нет фиксированных элементов, находится минимальный элемент (в программе реализовано функцией Min_Col) и прибавляется к общей сумме, то есть берутся ближайшие города для выхода из всех еще не пройденных городов. Программная реализация ‑ VHCOUNT. H_1
Метод 2: "В каждый город".
Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем в каждом столбце матрицы, в котором нет фиксированных элементов находится минимальный элемент (в программе реализовано функцией Min_Str) и прибавляется к общей сумме, то есть берутся ближайшие города для входа во все еще не пройденные города. Программная реализация ‑ VHCOUNT. H_2
Метод 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). Если среди них не окажется нулевых элементов, то переходят к третьему этапу.
Если же невыделенный нуль в матрице обнаружен, то возможен один из двух случаев :
1. в строке, содержащей нуль, имеется также нуль со звездочкой (0*) ;
2. эта строка не содержит нуль со звездочкой.
(Проверка случая производится в процедуре 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 (вычитание и прибавление)).