Реферат: Задача о коммивояжере
в строке, содержащей нуль, имеется также нуль со звездочкой (0*) ;
эта строка не содержит нуль со звездочкой.
(Проверка случая производится в процедуре 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: "По возрастанию номеров".
Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем работает следующий алгоритм нахождения маршрута:
Рассчитывается число пройденных городов.
Если пройдены все города, то выход, иначе из последнего города незаконченного маршрута добавляется переход в еще непройденный город с минимальным номером и возврат к шагу 1.
Программная реализация ‑ VHCOUNT. V_1
Метод 2: "С оптимизацией".
Рассчитывается цена маршрута по зафиксированным для данной вершины городам. Затем работает следующий алгоритм нахождения маршрута:
Рассчитывается число пройденных городов.
Если пройдены все города, то выход, иначе из последнего города незаконченного маршрута добавляется переход в город, переход в который имеет минимальные затраты и возврат к шагу 1.
Программная реализация - VHCOUNT. V_2
Метод 3: "Венгерский метод".
Данный метод основан на нижней оценке, получаемой венгерским методом. При установке расчета верхней оценки данным методом расчет нижней оценки автоматически устанавливается на венгерский метод, так как необходимым условием является то, что в каждой строке и каждом столбце только одна пометка. Алгоритм работы метода следующий:
Получаем решение релаксированной задачи венгерским методом.
Проверяем сколько городов пройдено.
Если пройдены все города, то значит получено решение нерелаксированной задачи то переход к пункту 5, иначе переход к пункту 4.
В строке города, из которого был возврат в первый, находим минимальное значение среди столбцов еще не пройденных городов и первого города.
Если в новом маршруте пройдено N городов, то из последнего города назначаем переход в первый.
Если маршрут замкнут, то выход из алгоритма, иначе переход к пункту 2.
Метод схож с методом "С оптимизацией", но отличается тем, что отсутствуют дополнительные проверки, так как исходное решение уже подчиняется вышеуказанным условиям. Программная реализация - SOLUTION. LEVELS
Описание программного интерфейса.
Интерфейс программы построен по структуре, аналогичной Turbo-средам, но не содержит объекто-ориентированного внутреннего содержания. Главное меню имеет следующую структуру:
Рассмотрим меню по пунктам:
Данные. Новая задача.
Этот пункт меню вызывает сначала процедуру ввода размерности задачи, затем процедуру ее редактирования. При вызове производится обнуление всех текущих значений матрицы.
Данные. Размерность задачи.
Данный пункт меню активизирует процедуру изменения размерности задачи. При этом если матрица уменьшается, то значения в отсеченной части не зануляются и при последующем увеличении размерности могут быть снова использованы. В случае увеличения размера на большее значение крайние элементы оказываются нулевыми.
Данные. Редактирование.
Пункт активизирует процедуру по вводу начальной матрицы условий. В процедуре реализован вертикальный и горизонтальный скроллинг матрицы, а также скроллинг внутри вводимой строки. Кроме того возможна настройка ширины строки ввода, которая описана в пункте меню "Опции. Ввод".
Данные. Генерация.
Пункт активизирует процедуру, генерирующую матрицу случайным образом в заданном диапазоне значений, который задается перед генерацией.
Данные. Работа с диском. Сохранить матрицу.
Данный пункт позволяет сохранить текущую исходную матрицу в файл на диск. Может быть активизирован в любой момент работы меню клавишей F2.
Данные. Работа с диском. Открыть матрицу.
Данный пункт позволяет считать с диска исходную матрицу. Может быть активизирован в любой момент работы меню клавишей F3.
Решение. Начать решение.
Данный пункт запускает работу алгоритма решения, используя текущие настройки.
Решение. Последний результат.
Данный пункт позволяет вывести последний полученный результат решения.
Режим решения. Блок: Минимум - Максимум.
Этот блок позволяет выбрать направление решения задачи на минимум или на максимум. Значение по умолчанию - Минимум.
Режим решения. Блок: Автоматический - Обучающий.
Этот блок позволяет выбрать между автоматическим и обучающим режимами решения задачи. Значение по умолчанию - Автоматический.
Расчет оценок. Блок "Верхняя оценка".
Этот блок позволяет выбрать метод расчета верхней оценки. При выборе третьего метода расчета ("Венгерский метод"), при решении автоматически устанавливается четвертый метод расчета нижней оценки ("Венгерский метод"). Значение по умолчанию - Венгерский метод.
Расчет оценок. Блок "Нижняя оценка".
Этот блок позволяет выбрать метод расчета нижней оценки. Какого-либо влияния на метод расчета верхней оценки выбор не оказывает. Значение по умолчанию - Венгерский метод.
Опции. Часы.
Данный пункт позволяет включить и выключить часы.
Опции. Звук.
Данный пункт позволяет включить и выключить звук.
Опции. Ввод.
Данный пункт позволяет задать ширину строки ввода при редактировании начальной матрицы задачи. Значение по умолчанию - 6.
Опции. Screen Saver.
Данный пункт позволяет задать время задержки срабатывания Screen Saver-а. Время указывается в минутах. Значение по умолчанию - 5 минут.
Опции. Сохранить опции.
Данный пункт позволяет запомнить состояние часов и звука в файле (Shadow.dsk).
Выход.
Данный пункт осуществляет выход из программы.
Описание программы
Структурно программа состоит из девяти модулей:
DESCRIPT.PAS - описание всех глобальных переменных программы. Исполняемых процедур не содержит.
IOMENU.PAS - модуль для обработки меню. Авторы - Илья Осипов, Андрей Шапошников.
IOCRT.PAS - модуль экранных функций вывода. Автор - Илья Осипов.
INOUT.PAS - модуль ввода-вывода. Автор - Андрей Шапошников.
SERVICE.PAS - модуль системных процедур программы. Автор - Андрей Шапошников.
VHCOUNT.PAS - модуль расчета оценок. Автор - Игорь Яров.
SOLUTION.PAS - модуль общего управления решением. Авторы - Игорь Яров, Андрей Шапошников.
VENGRSOL.PAS - модуль расчета оценок венгерским методом. Автор - Андрей Шапошников.
SHADOW.PAS - модуль общего управления программой. Автор - Андрей Шапошников.
Процедуры, которые используются при решении задачи описаны ранее. Можно лишь добавить, что общее управление алгоритмом ветвей и границ осуществляется процедурой OverDrive в автоматическом режиме решения и процедурой StudyMode в обучающем режиме решения.
Процедуры интерфейса программы и глобальные переменные описаны ниже.
Модуль INOUT.PAS
Procedure MatrIn(var a : workmatr ; var sz : byte ; msize, diag : boolean);
Процедура ввода начальной матрицы условий. Передаваемые параметры:
var a : workmatr - указатель на матрицу (описана глобальной переменной).
var sz : byte - текущая размерность задачи (описана глобальной переменной).
msize : boolean - возможность изменения размеров матрицы (True - могут быть изменены).
diag : boolean - доступность главной диагонали (False - ввод на главной диагонали запрещен).
Procedure Inp (x, y, l : byte ; gg : char ; var qq : char ; var a : real ; var s : string ; st_r : boolean; scroll : boolean ; attrib : byte);
Процедура ввода строки с внутренним скроллингом. Передаваемые параметры:
x, y : byte - координаты начала строки ввода.
l : byte - ширина строки ввода.
gg : char - последний введенный символ до начала редактирования.
var qq : char - последний введенный символ при редактировании.
var a : real - возвращаемое real-число.
var s : string - возвращаемая строка.
st_r : boolean - переключатель ввода real / string (True - ввод real-числа).
scroll : boolean - выключатель скроллинга внутри строки (True - скроллинг включен).
attrib : byte - текущие цветовые настройки.
Procedure M_Size (var qq : char);
Процедура изменения размера матрицы. Передаваемые параметры:
var qq : char - последний введенный символ при редактировании.
Procedure New_Task (var b : workmatr);
Процедура генерации новой задачи. Передаваемые параметры:
var b : workmatr - указатель на матрицу (описана глобальной переменной).
Procedure Matr_Rnd (var a : workmatr);
Процедура случайной генерации матрицы. Передаваемые параметры:
var a : workmatr - указатель на матрицу (описана глобальной переменной).
Procedure ShowSolve (Solve : vertex);
Процедура вывода последнего полученного решения. Передаваемые параметры:
Solve : vertex - запись, содержащая все параметры последнего решения.
Function ChooseFile (Title : string ; var qq : char) : string;
Функция ввода имени файла. Передаваемые параметры:
Title : string - заголовок окна.
var qq : char - последний введенный символ при редактировании.
ChooseFile : string - строка, содержащая имя файла.
Procedure FileOpen (var b : workmatr ; var NN : byte);
Процедура чтения с диска матрицы задачи. Передаваемые параметры:
var b : workmatr - указатель на матрицу (описана глобальной переменной).
var NN : byte - текущая размерность задачи (описана глобальной переменной).
Procedure FileSave (var b : workmatr ; var NN : byte);
Процедура записи на диск матрицы задачи. Передаваемые параметры:
var b : workmatr - указатель на матрицу (описана глобальной переменной).
var NN : byte - текущая размерность задачи (описана глобальной переменной).
Procedure InpWidht;
Процедура задания ширины строки ввода при редактировании начальной матрицы задачи.
Procedure InpSaver;
Процедура задания времени задержки срабатывания Screen saver-а.
Function ChooseVertex (var N : Point ; var Count : integer ; var Act : char) : Point;
Процедура выбора вершины для обработки при обучающем режиме решения. Передаваемые параметры:
var N : Point - указатель на начало списка вершин.
var Count : integer - общее количество конечных вершин.
var Act : char - код клавиши, определяющий действия, производимые над вершиной.
ChooseVertex : Point - указатель на вершину, над которой совершаются действия.
Модуль SERVICE.PAS
Function GetKey : char;
Функция, полностью эквивалентная функции Readkey (имеет некоторые отличия по обработке прерываний клавиатуры).
Procedure Knock;
Процедура, производящая щелчок.
Procedure Clock_on;
Процедура включения внутреннего таймера программы.
Procedure Clock_off;
Процедура выключения внутреннего таймера программы.
Procedure SaveIt;
Процедура сохранения текущих установок программы в файле shadow.dsk.
Procedure RestoreIt;
Процедура восстановления установок программы. При отсутствии файла shadow.dsk делает установки по умолчанию.
Function Stop : boolean;
Процедура обработки клавиши Escape в фоновом режиме.
Procedure GetDaTi (var Time : Stime);
Процедура взятия времени и даты во внутренний формат программы. Передаваемые параметры:
var Time : Stime - текущие время и дата во внутреннем формате.
Procedure TIME (var Time1, Time2 : Stime);
Процедура расчета времени работы алгоритма. Передаваемые параметры:
var Time1 : Stime - время начала работы алгоритма.
var Time2 : Stime - время работы алгоритма.
Function ProcExit : word;
Процедура подтверждения выхода из программы.
Модуль DESCRIPT.PAS
Переменные, управляющие работой интерфейса и настройкой решения.
| M : Pmenu ; | Указатель на основное меню программы |
| Sel : Word ; | Текущий выбранный пункт меню |
| ch, sk, gg, qq : char ; | Переменные для работы с клавиатурой |
| MethodH, MethodV, Tip, Direc : word ; | Переменные определяющие режим решения |
| TimeSScr : Longint ; | Время задержки срабатывания Screen Saver-а |
| w : boolean ; | Временная булевская переменная |
| SScrAct, | Активность Screen Saver-а |
| ClockAct, | Активность часов |
| SoundAct, | Активность звука |
| SoluAct : boolean ; | Активность решения |
| TimeN, TimeE : Stime ; | Время начала и завершения решения |
| TempStr : string ; | Временная string-переменная |
| TempReal : real ; | Временная real-переменная |
| Len, | Длина элемента матрицы |
| Step : byte ; | Интервал вывода элементов матрицы |
Типы, используемые при работе алгоритма решения.
| WorkMatr = array [ 1 .. Nmax+1, 1..Nmax+1 ] of real ; | Тип рабочей матрицы |
| Solu = array [ 1..Nmax ] of byte ; | Вектор решения |
|
Labels = record |
Запись, содержащая вектора фиксированных городов |
| Lab = array [ 1..Nmax ] of boolean ; | Массив меток |
| Point = ^Vertex ; | Указатель на вершину |
|
Vertex = record |
Запись, содержащая все свойства единичной вершины |
Переменные, используемые при работе алгоритма решения.
|
b, |
Исходная матрица задачи
и |
| x : Solu ; | Вектор решения |
| i, j, | Индексные переменные |
| NN : byte ; | Текущая размерность задачи |
| MaxR, MinR : real ; | Переменные, определяющие диапазон генерации матрицы |
| LastSolve : Vertex ; | Запись, содержащая параметры последнего решения |
Литература
Мамиконов А.Г. "Основы построения АСУ", Москва, "Высшая школа" - 1981.
Схрейвер А. "Теория линейного и целочисленного программирования", Москва, "Мир" - 1981.
Таха Х. "Введение в исследование операций", Москва, "Мир" - 1985.
Волчков Б.А., Лифшиц И.И. "Автоматизированные системы в планировании", Москва, "Экономика" - 1980.
Касаткин А.И. "Управление ресурсами", Минск, "Высшая школа" -1992.
Журнал "PC Magazine" (№3 - 1994), стр. 45 - 48.
