Наибольший выбор программа предоставляет в шаге 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). Если среди них не окажется нулевых элементов, то переходят к третьему этапу.

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

(Проверка случая производится в процедуре 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: "По возрастанию номеров".

Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем работает следующий алгоритм нахождения маршрута:

Программная реализация ‑ VHCOUNT. V_1

Метод 2: "С оптимизацией".

Программная реализация - VHCOUNT. V_2

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

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

Метод схож с методом "С оптимизацией", но отличается тем, что отсутствуют дополнительные проверки, так как исходное решение уже подчиняется вышеуказанным условиям. Программная реализация - SOLUTION. LEVELS

Описание программного интерфейса.

Интерфейс программы построен по структуре, аналогичной Turbo-средам, но не содержит объекто-ориентированного внутреннего содержания. Главное меню имеет следующую структуру:

Рассмотрим меню по пунктам:

Данные. Новая задача.

Этот пункт меню вызывает сначала процедуру ввода размерности задачи, затем процедуру ее редактирования. При вызове производится обнуление всех текущих значений матрицы.

Данные. Размерность задачи.

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

Данные. Редактирование.

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

Данные. Генерация.

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

Данные. Работа с диском. Сохранить матрицу.

Данный пункт позволяет сохранить текущую исходную матрицу в файл на диск. Может быть активизирован в любой момент работы меню клавишей F2.

Данные. Работа с диском. Открыть матрицу.

Данный пункт позволяет считать с диска исходную матрицу. Может быть активизирован в любой момент работы меню клавишей F3.

Решение. Начать решение.

Данный пункт запускает работу алгоритма решения, используя текущие настройки.

Задача о коммивояжере (стр. 2 из 3)

Описание программного интерфейса.