Задача о коммивояжере

Шапошников.

  • 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
    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 ; Запись, содержащая параметры последнего решения

    Литература

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

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

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

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

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

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

    Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
    Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

    Поможем написать работу на аналогичную тему

    Получить выполненную работу или консультацию специалиста по вашему учебному проекту
    Нужна помощь в написании работы?
    Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
  • Похожие рефераты: