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

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 gor, ver : Solu ; end ;	Запись, содержащая вектора фиксированных городов
Lab = array [ 1..Nmax ] of boolean ;	Массив меток
Point = ^Vertex ;	Указатель на вершину
Vertex = record Hi, Lo : real ; Go : Solu ; Res : Solu ; Attr : Char ; Prev, Next : Point ; end ;	Запись, содержащая все свойства единичной вершины

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

b, c : workmatr ;	Исходная матрица задачи и матрица, используемая алгоритмом венгерского метода
x : Solu ;	Вектор решения
i, j,	Индексные переменные
NN : byte ;	Текущая размерность задачи
MaxR, MinR : real ;	Переменные, определяющие диапазон генерации матрицы
LastSolve : Vertex ;	Запись, содержащая параметры последнего решения

Литература

       Мамиконов А.Г. "Основы построения АСУ", Москва, "Высшая школа" - 1981.

       Схрейвер А. "Теория линейного и целочисленного программирования", Москва, "Мир" - 1981.

       Таха Х. "Введение в исследование операций", Москва, "Мир" - 1985.

       Волчков Б.А., Лифшиц И.И. "Автоматизированные системы в планировании", Москва, "Экономика" - 1980.

       Касаткин А.И. "Управление ресурсами", Минск, "Высшая школа" -1992.

       Журнал "PC Magazine" (№3 - 1994), стр. 45 - 48.