Задача Комівояжера. Лабораторна робота з Дискретні моделі в САПР. Робота № 528394

Перехід до торгівельного партнера Binance

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

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКНІ

Факультет:

Комп’ютерні науки

Кафедра:

Кафедра САПР

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Дискретні моделі в САПР

Завантажити

Частина тексту файла (без зображень, графіків і формул):

НУЛП, ІКНІ, САПР Тема оцінка підпис Алгоритм рішення задачі комівояжера № залікової: Дискретні моделі в САПР Викладач: Мета роботи : метою даної лабораторної роботи є вивчення і дослідження алгоритмів рішення задачі комівояжера. Короткі теоретичні відомості : Невідомо, коли проблему комівояжера було досліджено вперше. Однак, відома видана в 1832 році книжка з назвою «Комівояжер — як він має поводитись і що має робити для того, аби доставляти товар та мати успіх в своїх справах — поради старого Кур'єра», в якій описано проблему, але математичний апарат для її розв'язання не застосовується. Натомість, в ній запропоновано приклади маршрутів для деяких регіонів Німеччини та Швейцарії. Раннім варіантом задачі може розглядатись англ. Icosian Game Вільяма Гамільтона 19 століття, яка полягала в тому, щоб знайти маршрути на графі з 20 вузлами. Перші згадки в якості математичної задачі на оптимізацію нелажать Карлу Менґеру (нім. Karl Menger), який сформулював її в математичному колоквіумі в 1930 році наступним чином: ми називаємо проблемою женця (оскільки це питання виникає в кожного листоноші, зокрема, її вирішують багато мандрівників) завдання віднайти найкоротший шлях між скінченною множиною місць, відстань між якими відома. Невдовзі з'явилась відома зараз назва задача мандруючого продавця (англ. Traveling Salesman Problem), яку запропонував Гаслер Вітні (англ. Hassler Whitney) з Принстонського Університету. З метою спрощення задачі та гарантії існування маршруту, зазвичай вважається, що модельний граф задачі є повністю зв'язним, тобто, що між довільною парою вершин існує ребро. Це можна досягти тим, що в тих випадках, коли між окремими містами не існує сполучення, вводити ребра з максимальною вагою (довжиною, вартістю тощо). Через велику довжину таке ребро ніколи не потрапить до оптимального маршруту, якщо він існує. Загальною задачею комівояжера називають задачу пошуку маршруту найменшої довжини. Задачею комівояжера називають задачу пошуку гамільторового контура найменшої довжини. Контур комівояжера, який має найменшу довжину, називають оптимальним гамільтоновим контуром він є оптимальним рішенням задачі комівояжера. Оптимальний маршрут комівояжера не обов`язково є гамільтоновим контуром. Рішенням задачі комівояжера є оптимальний гамільтоновий контур. Реалізація алгоритму (Java) : public void tsp(int adjacencyMatrix[][]) { /* Ініціалізація змінних */ int[] visited = new int[numberOfNodes + 1];//Пройдені вершини int element, distance = 0, i; int min = Integer.MAX_VALUE; System.out.print(1 + "\t"); while (!stack.isEmpty()) { /* Доки не пройдено всіх вершин, знаходимо мінімальне ребро, суміжне з вершиною і додаємо його до загальної вартості. */ while (i <= numberOfNodes) { if (adjacencyMatrix[element][i] > 1 && visited[i] == 0) { if (min > adjacencyMatrix[element][i]) { min = adjacencyMatrix[element][i]; distance = i; minFlag = true; } } i++; } /*Якщо ребро задовільняє умови мінімальності ,то додаємо його в шлях і виводимо його(шлях). */ if (minFlag) { cost+=min; System.out.print(distance + "\t"); } } } Інструкція по експлуатації: Для роботи програми необхідно запустити файл Lab_4_DM.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю суміжності. Далі програма знаходить мінімальний маршрут та виводить його значення. Граф: Рис.1. Початковий граф. Рис.2. Знайдений маршрут. Результат виконання: ***HELP*** 0. Програма розв'язує задачу комівояжера та знаходить мінімальну вартість маршруту! Для коректної роботи програми необхідно: 1. Ввести кількість вершин графу. 2. Ввести матрицю суміжності(цілі числа). 3. Нумерація вершин графа починається з 1 з інкрементом в 1 (1,2,3...) ! Введіть кількість вершин графа: 5 Введіть матрицю суміжності: 0 5 3 4 0 5 0 1 3 4 3 1 0 5 2 4 3 5 0 3 0 4 2 3 0 Отриманий шлях: 1 3 5 4 2 Отримана вартість:11 Висновок : в результаті виконання лабораторної роботи я вивчив алгоритм рішення задачі комівояжера та реалізував йог на мові Java .

Лабораторна робота Дискретні моделі в САПР

14.05.2016 10:05-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись