• Курсова робота по програмному забезпеченню
  • Метод 1: "З кожного міста".
  • Метод 2: "В кожне місто".
  • Метод 3: "Комбінований".
  • Метод 4: "Угорський метод".
  • Метод 1: "По зростанню номерів".
  • Метод 2: "З оптимізацією".
  • Метод 3: "Угорський метод".
  • модуль INOUT.PAS
  • Procedure Inp (x, y, l: byte; gg: char; var qq: char; var a: real; var s: string; st_r: boolean; scroll: boolean; attrib: byte);
  • Procedure M_Size (var qq: char);
  • Procedure Matr_Rnd (var a: workmatr);
  • Function ChooseFile (Title: string; var qq: char): string;
  • Procedure FileOpen (var b: workmatr; var NN: byte);
  • Procedure FileSave (var b: workmatr; var NN: byte);
  • Procedure InpWidht;
  • Function ChooseVertex (var N: Point; var Count: integer; var Act: char): Point;
  • модуль SERVICE.PAS
  • Procedure SaveIt;
  • Function Stop: boolean;
  • Procedure TIME (var Time1, Time2: Stime);
  • Function ProcExit: word;


  • Дата конвертації12.12.2019
    Розмір29.89 Kb.
    Типреферат

    Скачати 29.89 Kb.

    Завдання про комівояжера

    Нижегородський Ордена Трудового Червоного Прапора
    Державний Університет ім. Н.І. Лобачевського

    Економічний факультет

    Кафедра інформатики та обчислювальної техніки

    Курсова робота
    по програмному забезпеченню

    тема:

    Рішення задачі про комівояжера

    виконали:

    Шапошников А.Д.

    Ярів Є.І.

    Науковий керівник:

    Громницький В.С.

    Нижній Новгород
    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-сумісних комп'ютерів (їх виробляє безліч фірм, таких як Hewlett Packard, AT & T, Compaq і інші), а також повної сумісності пізніх моделей з більш ранніми, що дозволяло IBM довгий час утримувати ринок збуту, незважаючи на те, що на початку 90-х років Macintosh-і помітно перевершували PC продуктивністю (зараз, з появою Pentium і PowerPC, Macintosh-і втратили беззастережне лідерство по виро водительности).

    Персональні комп'ютери зараз в основному використовуються в чотирьох областях:

    · Обробка текстів і комп'ютерна верстка;

    · Зберігання баз даних з можливістю швидкої їх обробки;

    · Управління виробничими процесами;

    · Аналіз складних процесів;

    Також зараз інтенсивно розвиваються ще кілька областей застосування ПЕОМ, таких як комп'ютерні ігри (в 1994 році 43% ринку програмних продуктів становили ігрові програми), гео-інформаційні системи, навчальні системи та системи мультимедіа.

    Програма даної курсової роботи входить в розділ "аналіз складних процесів". Дана область почала розвиватися в середині 80-х років, коли продуктивність ПЕОМ досягла достатнього рівня для обробки необхідних обсягів інформації в реальному масштабі часу, що дозволило розпочати застосування комп'ютерів в областях, пов'язаних з контролем складних процесів і їх аналізом. Однією з таких проблем стала оптимізація систем з багатьма невідомими, коли певний параметр було необхідно звести до якого-небудь значенням або просто максимізувати.

    Найбільш яскравим і характерним прикладом застосування завдання "Про комівояжера" стала оптимізація операцій на конвеєрі: в 1984 році, після того як був проведений аналіз послідовності і тимчасових витрат на операції на конвеєрах заводів компанії "General Motors" і прийняті рекомендовані заходи, вдалося збільшити загальну продуктивність майже на 13% при незмінному числі робітників і тому ж обладнанні. Розрахунки проводилися на комп'ютерах IBM 360gr, які в той час були одними з найбільш продуктивних систем в світі. Прорахунок і оптимізація 200 основних і 87 допоміжних операцій тривав близько 230 годин. Вважається, що це було перше комерційне застосування комп'ютерних технологій в галузі управління виробництвом в цілому.

    Зараз рішення даного завдання необхідно в багатьох областях пов'язаних із замкненими і при цьому жорстко пов'язаними за часом системами, такими як: конвеєрне виробництво, багатоопераційні оброблювальні комплекси, суднові і залізничні вантажні системи, перевезення вантажів по замкнутому маршруту, розрахунок авіаційних ліній.

    Тому дана проблема на сучасному етапі розвитку суспільства має не найостанніше за значимістю місце.


    Постановка задачі

    Класична постановка задачі про комівояжера виглядає наступним чином:

    Є N міст, які повинен обійти комівояжер з мінімальними витратами. При цьому на його маршрут накладається два обмеження:

    · Маршрут повинен бути замкнутим, тобто комівояжер повинен повернутися в те місто, з якого він почав рух;

    · В кожному з міст комівояжер повинен побувати точно один раз, тобто треба обов'язково обійти всі міста, при цьому не побувавши ні в одному місті двічі.

    Для розрахунку витрат існує матриця умов, яка містить витрати на перехід з кожного міста в кожен, при цьому вважається, що можна перейти з будь-якого міста в будь-який, крім того ж самого (в матриці як би викреслюється діагональ). Метою рішення є знаходження маршруту, що задовольняє всім умовам і при цьому має мінімальну суму витрат.


    алгоритм рішення

    В роботі для вирішення задачі про комівояжера застосовується метод гілок і меж, що відноситься до методів дискретної оптимізації. По суті, це повний перебір рішень, який оптимізується за рахунок того, що при переборі варіантів за певними ознаками відсікаються неоптимальні безлічі перебору. Так як кількість вершин від рівня до рівня зростає в факторіальною прогресії, то відсікання вершин верхніх рівнів значно скорочує загальне число перебираються варіантів.

    Загальна схема методу така (дана програмна реалізація):


    Математична модель задачі

    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 × R £ (N -1), де R

    Отже, не існує замкнутого подцикла з числом міст меншим, ніж 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) описує завдання про комівояжера.


    Опис програмної реалізації алгоритму

    У програмі реалізований класичний варіант методу гілок і меж, тобто алгоритм рішення наступного:

    При цьому передбачена можливість зміни напряму критерію, тобто можливість вирішення завдання на максимум.

    Найбільший вибір програма надає в кроці 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.

    Рішення. Почати рішення.

    Даний пункт запускає роботу алгоритму рішення, використовуючи поточні настройки.

    Рішення. Останній результат.

    Даний пункт дозволяє вивести останній отриманий результат рішення.

    Режим рішення. Блок: Мінімум - Максимум.

    Цей блок дозволяє вибрати напрямок вирішення завдання на мінімум або на максимум. Значення за замовчуванням - Мінімум.

    Режим рішення. Блок: Автоматичний - Навчальний.

    Цей блок дозволяє вибрати між автоматичним і навчальним режимами рішення задачі. Значення за замовчуванням - Автоматичний.

    Розрахунок оцінок. Блок "Верхня оцінка".

    Цей блок дозволяє вибрати метод розрахунку верхньої оцінки. При виборі третього методу розрахунку ( "Угорський метод"), при вирішенні автоматично встановлюється четвертий метод розрахунку нижньої оцінки ( "Угорський метод"). Значення за замовчуванням - Угорський метод.

    Розрахунок оцінок. Блок "Нижня оцінка".

    Цей блок дозволяє вибрати метод розрахунку нижньої оцінки. Якогось впливу на метод розрахунку верхньої оцінки вибір не робить. Значення за замовчуванням - Угорський метод.

    Опції. Годинники.

    Даний пункт дозволяє включити і вимкнути годинник.

    Опції. Звук.

    Даний пункт дозволяє вмикати і вимикати аудіо.

    Опції. Введення.

    Даний пункт дозволяє задати ширину рядка введення при редагуванні початковій матриці завдання. Значення за замовчуванням - 6.

    Опції. Screen Saver.

    Даний пункт дозволяє задати час затримки спрацьовування Screen Saver-а. Час вказується в хвилинах. Значення за замовчуванням - 5 хвилин.

    Опції. Зберегти опції.

    Даний пункт дозволяє запам'ятати стан годин і звуку в файлі (Shadow.dsk).

    Вихід.

    Даний пункт здійснює вихід з програми.


    опис програми

    Структурно програма складається з дев'яти модулів:

    Процедури, які використовуються при вирішенні задачі описані раніше. Можна лише додати, що загальне керівництво алгоритмом гілок і меж здійснюється процедурою 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; Запис, що містить параметри останнього рішення