Реферат: Задача о коммивояжере
Нижегородский ОрденаТрудового Красного Знамени
Государственный Университет им. Н.И. Лобачевского
Экономическийфакультет
Кафедра информатики ивычислительной техники
Курсовая работа
по программному обеспечению
тема:
Решение задачи окоммивояжере
Выполнили:
ШапошниковА.Д.
ЯровЕ.И.
Научныйруководитель:
ГромницкийВ.С.
Нижний Новгород
1995 год
/>/>/>/>Оглавление
Оглавление… 2
Введение… 3
Постановка задачи… 4
Алгоритм решения… 4
Математическая модель задачи… 5
Описание программной реализации алгоритма… 6
Описание программного интерфейса… 9
Описание программы… 12
Литература… 15
/>/>/>/>Введение
В настоящее время быстроразвивается научно-техническая революция. Появившись в 40-х годах нашегостолетия компьютеры и компьютерные технологии прошли за это время путь отламповых систем с прямым заданием кодов операций до сверхбыстрых персональныхкомпьютеров на монокристальной технологии, использующих при работемногопользовательские операционные системы с графическим интерфейсом. Наиболеебурное развитие компьютерных технологий произошло за последние 10-15 лет, послетого как была разработана технология производства СБИС, а на их основемикрочипов. Также в начале 80-х годов начала развиваться концепция персональнойЭВМ, которая со временем выразилась в существовании двух наиболеераспространенных аппаратных платформ: Macintosh (производится фирмой Apple,процессоры фирмы Motorola) и IBM PC (производится фирмой IBM, процессоры фирмыIntel).
Каждая из этих платформ имеет своюнаправленность и особенности. Компьютеры Macintosh в основном ориентированы наработу в глобальных сетях и обработку информации, как бы внешнего восприятия,то есть графической и звуковой. Их главными особенностями являются встроенная вПЗУ (ROM) графическая операционная система и несовместимость различных моделейэтой фирмы, однако за счет этого достигнут очень быстрый ростпроизводительности процессоров и системы в целом.
Фирма IBM, в отличие от Apple,придерживается концепции открытой системы, что выражается в том, что,во-первых, IBM не имеет эксклюзивного права на производство и продажуIBM-совместимых компьютеров (их производит множество фирм, таких как HewlettPackard, AT&T, Compaq и другие), а также полной совместимости позднихмоделей с более ранними, что позволяло IBM долгое время удерживать рынок сбыта,несмотря на то, что в начале 90-х годов Macintosh-и заметно превосходили PC попроизводительности (сейчас, с появлением Pentium и PowerPC, Macintosh-ипотеряли безоговорочное лидерство по производительности).
Персональные компьютеры сейчас восновном используются в четырех областях:
· обработка текстов и компьютерная верстка;
· хранение баз данных с возможностью быстрой их обработки;
· управление производственными процессами;
· анализ сложных процессов;
Также сейчас интенсивноразвиваются еще несколько областей применения ПЭВМ, таких как компьютерные игры(в 1994 году 43% рынка программных продуктов составляли игровые программы),гео-информационные системы, обучающие системы и системы мультимедиа.
Программа данной курсовой работывходит в раздел «анализ сложных процессов». Данная область началаразвиваться в середине 80-х годов, когда производительность ПЭВМ достигладостаточного уровня для обработки необходимых объемов информации в реальноммасштабе времени, что позволило начать применение компьютеров в областях,связанных с контролем сложных процессов и их анализом. Одной из таких проблем сталаоптимизация систем со многими неизвестными, когда некоторый параметр былонеобходимо свести к какому-либо значению или просто максимизировать.
Наиболее ярким и характернымпримером применения задачи «О коммивояжере» стала оптимизацияопераций на конвейере: в 1984 году, после того как был проведен анализпоследовательности и временных затрат на операции на конвейерах заводовкомпании «General Motors» и приняты рекомендованные меры, удалосьувеличить общую производительность почти на 13% при неизменном числе рабочих итом же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые вто время являлись одними из самых производительных систем в мире. Просчет иоптимизация 200 основных и 87 вспомогательных операций занял около 230 часов.Считается, что это было первое коммерческое применение компьютерных технологийв области управления производством в целом.
Сейчас решение данной задачинеобходимо во многих областях связанных с замкнутыми и при этом жесткосвязанными по времени системами, такими как: конвейерное производство,многооперационные обрабатывающие комплексы, судовые и железнодорожныепогрузочные системы, перевозки грузов по замкнутому маршруту, расчетавиационных линий.
Поэтому данная проблема насовременном этапе развития общества имеет не самое последнее по значимостиместо.
/>/>/>/>Постановказадачи
Классическая постановка задачи окоммивояжере выглядит следующим образом:
Имеется N городов, которые долженобойти коммивояжер с минимальными затратами. При этом на его маршрутнакладывается два ограничения:
· маршрут должен быть замкнутым, то есть коммивояжер долженвернуться в тот город, из которого он начал движение;
· в каждом из городов коммивояжер должен побывать точно один раз,то есть надо обязательно обойти все города, при этом не побывав ни в одномгороде дважды.
Для расчета затрат существует матрица условий, содержащаязатраты на переход из каждого города в каждый, при этом считается, что можноперейти из любого города в любой, кроме того же самого (в матрице как бывычеркивается диагональ). Целью решения является нахождения маршрута,удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
/>/>/>/>АлгоритмрешенияВ курсовой работе для решениязадачи о коммивояжере применяется метод ветвей и границ, относящийся к методамдискретной оптимизации. В сущности, это полный перебор решений, которыйоптимизируется за счет того, что при переборе вариантов по определеннымпризнакам отсекаются неоптимальные множества перебора. Так как количествовершин от уровня к уровню возрастает в факториальной прогрессии, то отсечениевершин верхних уровней значительно сокращает общее число перебираемыхвариантов.
Общая схема метода такова (даннаяпрограммная реализация):
Все множестворазбивается на N-1 подмножеств, каждое из которых оценивается верхней и нижнейоценками.
Производится отсевнеоптимальных множеств по следующему критерию: если нижняя оценка (решениерелаксированной задачи) больше минимальной из верхних оценок (решенийнерелаксированной задачи), то множество считается очевидно неоптимальным иотсекается, иначе остается до следующей итерации.
Находится множество случшей нижней оценкой (прогнозом) и дробится на количество равное размерностьисходной матрицы минус количество уже пройденных (фиксированных для данногомножества) городов.
Находятся минимальныеверхняя и нижняя оценка. Если они равны и достигнуты на одном и том жемножестве, то это значит, что получено оптимальное решение и алгоритмзаканчивает работу, иначе возврат к шагу 2.
/>/>/>/>Математическаямодель задачи
N — число городов.
Ci j , i,j=1..N — матрица затрат, где Ci j - затраты на переходиз i-го города в j-й.
Xi j — матрица переходов с компонентами:
Xi j = 1,если коммивояжер совершает переход из i-го города в j-й,
Xi j = 0,если не совершает перехода,
где i, j = 1..N и i¹j.
Критерий:
/> (1)
Ограничения:
/>,i = 1..N (2)
/>,j = 1..N (3)
Ui- Uj + N × Xi j £ N-1, i, j = 1..N, i ¹ j. (4)
Доказательство, что модель (1-4)описывает задачу о коммивояжере:
Условие (2) означает, чтокоммивояжер из каждого города выезжает только один раз; условие (3) — въезжает в каждый город только один раз; условие (4) — обеспечивает замкнутостьмаршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.
Рассмотрим условие (4). Применимметод доказательства от противного, то есть предположим, что условие (4)выполняется для некоторого подцикла T из R городов, где R<N. Сложив всенеравенства (4) вдоль этого подцикла получим
/>.
Так как
/>,
то 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) описывает задачу окоммивояжере.
/>/>/>Описание программнойреализации алгоритма
В программе реализованклассический вариант метода ветвей и границ, то есть алгоритм решенияследующий:
Все множестворазбивается на N-1 подмножеств, каждое из которых оценивается верхней и нижнейоценками.
Производится отсевнеоптимальных множеств по следующему критерию: если нижняя оценка (решениерелаксированной задачи) больше минимальной из верхних оценок (решенийнерелаксированной задачи), то множество считается очевидно неоптимальным и отсекается,иначе остается до следующей итерации.
Находится множество случшей нижней оценкой (прогнозом) и дробится на количество равное размерностьисходной матрицы минус количество уже пройденных (фиксированных для данногомножества) городов.
Находятся минимальныеверхняя и нижняя оценка. Если они равны и достигнуты на одном и том жемножестве, то это значит, что получено оптимальное решение и алгоритмзаканчивает работу, иначе возврат к шагу 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). Если среди них неокажется нулевых элементов, то переходят к третьему этапу.
Если же невыделенный нуль вматрице обнаружен, то возможен один из двух случаев :
в строке,содержащей нуль, имеется также нуль со звездочкой (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
ProcedureMatrIn(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 — указатель наматрицу (описана глобальной переменной).
ProcedureShowSolve (Solve: vertex);
Процедура вывода последнегополученного решения. Передаваемые параметры:
Solve: vertex — запись,содержащая все параметры последнего решения.
Function ChooseFile (Title: string ; var qq: char): string;
Функция ввода имени файла.Передаваемые параметры:
Title: string — заголовок окна.
var qq: char — последнийвведенный символ при редактировании.
ChooseFile: string — строка,содержащая имя файла.
ProcedureFileOpen (var b: workmatr ; var NN: byte);
Процедура чтения с диска матрицызадачи. Передаваемые параметры:
var b: workmatr — указатель наматрицу (описана глобальной переменной).
var NN: byte — текущая размерностьзадачи (описана глобальной переменной).
ProcedureFileSave (var b: workmatr ; var NN: byte);
Процедура записи на диск матрицызадачи. Передаваемые параметры:
var b: workmatr — указатель наматрицу (описана глобальной переменной).
var NN: byte — текущаяразмерность задачи (описана глобальной переменной).
Procedure InpWidht;
Процедура задания ширины строкиввода при редактировании начальной матрицы задачи.
Procedure InpSaver;
Процедура задания времени задержкисрабатывания Screen saver-а.
FunctionChooseVertex (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 (имеет некоторые отличия по обработкепрерываний клавиатуры).
ProcedureKnock;
Процедура, производящая щелчок.
ProcedureClock_on;
Процедура включения внутреннеготаймера программы.
ProcedureClock_off;
Процедура выключения внутреннеготаймера программы.
ProcedureSaveIt;
Процедура сохранения текущихустановок программы в файле shadow.dsk.
ProcedureRestoreIt;
Процедура восстановления установокпрограммы. При отсутствии файла shadow.dsk делает установки по умолчанию.
FunctionStop: boolean;
Процедура обработки клавиши Escapeв фоновом режиме.
Procedure GetDaTi (var Time: Stime);
Процедура взятия времени и даты вовнутренний формат программы. Передаваемые параметры:
var Time: Stime — текущие время идата во внутреннем формате.
Procedure TIME (var Time1, Time2: Stime);
Процедура расчета времени работыалгоритма. Передаваемые параметры:
var Time1: Stime — время началаработы алгоритма.
var Time2: Stime — время работыалгоритма.
FunctionProcExit: 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
gor, ver: Solu ;
end ;
Vertex = record
Hi, Lo: real ;
Go: Solu ;
Res: Solu ;
Attr: Char ;
Prev, Next: Point ;
end ;
Переменные,используемые при работе алгоритма решения.
b,
c: workmatr ;
Исходная матрица задачи и
матрица, используемая алгоритмом венгерского метода
/>/>Литература
Мамиконов А.Г. «Основы построения АСУ», Москва, «Высшаяшкола» — 1981.
Схрейвер А. «Теория линейного и целочисленногопрограммирования», Москва, «Мир» — 1981.
Таха Х. «Введение в исследование операций», Москва, «Мир»- 1985.
Волчков Б.А., Лифшиц И.И. «Автоматизированные системы впланировании», Москва, «Экономика» — 1980.
Касаткин А.И. «Управление ресурсами», Минск, «Высшаяшкола» -1992.
Журнал «PC Magazine» (№3 — 1994), стр. 45 — 48.