Технологія створення програми

Спочатку був спроектований вигляд HTML-меню проекту.

Потім був написаний код шаблону графічної оболонки з використанням мови гіпертекстової розмітки HTML

Наступним етапом було створення проекту в середовищі програмування Microsoft Visual Studio 2008 для кожної прикладної задачі. Були створені такі проекти :

1. “BullsCows”- Задача “Бики та корови “ з кодом у файлі “BullsCows.сpp”

2. “ Sieve eratosthenes ”- Решето Ератосфена з кодом у файлі “sieve.сpp”

3. “Prime”- Пошук простих чисел– з кодом у файлі “prime.сpp”

4. “Salesman”- Задача комівояжера – з кодом у файлі “salesman.сpp”

В кожному з цих проектів був послідовно написаний код для реалізації поданої прикладної задачі, під час цього було виконане налагодження програм та виправлення помилок. Був виконаний процес перевірки правильності роботи програм на вхідних тестах [2].

Був створений проект для багатофайлової програми з іменем “main”, що містить всі виконані прикладні задачі як модулі. Було додано срр файли всіх виконаних задач та заповнено головний файл “main.срр” викликами даних модулів. Був виконаний процес виправлення помилок та налагодження роботи програми.

На цьому етапі було додано теоретичну інформацію про алгоритм та розв’язані задачі в HTML-меню. А також посилання на ехе-файл з вхідними файлами.

Застосування алгоритму для прикладних задач

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

Умова задач[1]

Є міст, відстані(вартість проїзду, витрата пального на дорогу і т.д) між якими відомі. Комівояжер повинен пройти всі міст по одному разу, повернувшись в те місто, з якого розпочав. Вимагається знайти такий маршрут руху, при якому сумарна пройдена відстань (вартість проїзду і т.д.) буде мінімальною.

Вхідні та вихідні тести

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

Програма виводить довжину мінімального шляху комівояжера та сам шлях на екран.

Приклад 1:

Кількість міст:

Матриця відстаней між містами:

0 1 2 3 4 5

2 0 3 4 5 6

3 4 0 5 6 7

7 6 5 0 4 3

6 5 4 3 0 2

5 4 3 2 1 0

Довжина мінімального шляху комівояжера:

Шлях комівояжера:

Приклад 2:

Кількість міст:

Матриця відстаней між містами:

0 32 19 33 22 41 18 15 16 31

32 0 51 58 27 42 35 18 17 34

19 51 0 23 35 49 26 34 35 41

33 58 23 0 33 37 23 46 46 32

22 27 35 33 0 19 10 23 23 9

41 42 49 37 19 0 24 42 42 10

18 35 26 23 10 24 0 25 25 14

15 18 34 46 23 42 25 0 1 32

16 17 35 46 23 42 25 1 0 32

31 34 41 32 9 10 14 32 32 0

Довжина мінімального шляху комівояжера:

Шлях комівояжера:

Опис алгоритму методу[2]

У термінах теорії графів завдання можна сформулювати наступним чином: задано вершин і матриця де - довжина (або ціна) дуги (i, j). Очевидно, що завдання комівояжера - це завдання відшукання найкоротшого гамільтонового маршруту в повному графові.

Рішення задачі комівояжера методом гілок і границь по-іншому називають алгоритмом Літтла. Граф представляють у вигляді матриці ваг ребер. Якщо між вершинами та немає дуги, то ставиться символ " ".

Алгоритм Літтла можна сформулювати у вигляді наступних правил:

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

;

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

3. Підсумовуємо елементи і , отримаємо константу приведення

,

яка буде нижньою границею множини усіх допустимих гамільтонових циклів, тобто

.

4. Знаходимо ступені нулів для приведеної по рядках і стовпцям матриці. Для цього подумки нулі в матриці замінюємо на знак " " і знаходимо суму мінімальних елементів рядка і стовпця, що відповідають цьому нулю. Записуємо її в правому верхньому кутку клітинки :

.

5. Вибираємо дугу , для якої міра нульового елементу досягає максимального значення

.

6. Розбиваємо множину усіх гамільтонових циклів на дві підмножини і Підмножина гамільтонових маршрутів містить дугу , - її не містить. Для отримання матриці шляхів , що включають дугу , викреслюємо в матриці рядок і стовпець . Щоб не допустити утворення негамільтонового циклу, замінимо симетричний елемент на знак " ".

7. Приводимо матрицю гамільтонових щляхів . Нехай - її константа приведення. Тоді нижня границя множини визначиться так:

.

8. Знаходимо множину гамільтонових шляхів , що не включають дугу . Виключення дуги досягається заміною елементу в матриці на " ".

9. Робимо приведення матриці гамільтонових шляхів . Нехай - константа її приведення. Нижня границя множини визначиться так:

.

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

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