Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Задача Листоноші
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Дискретні моделі в САПР
Частина тексту файла (без зображень, графіків і формул):
НУЛП, ІКНІ, САПР
Тема
оцінка
підпис
АЛГОРИТМ РІШЕННЯ ЗАДАЧІ ЛИСТОНОШІ
№ залікової:
Дискретні моделі в САПР
Викладач:
Мета роботи : метою даної лабораторної роботи є вивчення алгоритмів рішення задачі листоноші.
Короткі теоретичні відомості :
Задача листоноші може бути сформульована в термінах теорії графів. Для цього побудуємо граф G = (X , E), в якому кожна дуга відповідає вулиці в маршруті руху листоноші, а кожна вершина - стик двох вулиць. Ця задача являє собою задачу пошуку найкоротшого маршруту, який включає кожне ребро хоча б один раз і закінчується у початковій вершині руху.
Ейлеревим циклом в графі називається шлях, який починається і закінчується в тій самій вершині, при чому всі ребра графа проходяться тільки один раз. Ейлеревим шляхом називається шлях, який починається в вершині А, а закінчується в вершині Б, і всі ребра проходяться лише по одному разу.
Теорема 1.
Якщо у графа всі вершини мають парну степінь, то цей граф Ейлерів, тобто має Ейлерів цикл.
Теорема 2 .
Якщо в графі існує Ейлерів шлях, то це означає, що в нього є строго дві непарні вершини. При чому шлях починається в одній з них, а закінчується в іншій.
Задача листоноші для неорієнтованого графа G(Х,E) - це задача для графа, в якому ребра
можна проходити в будь-якому з двох напрямків. Необхідно розгянути окремо наступні два випадки :
Випадок 1 : Граф G парний.
Випадок 2 : Граф G непарний.
Випадок 1 : Якщо граф парний, то оптимальним рішенням задачі є ейлеровий маршрут. В цьому випадку листоноша не повинен обходити більше одного разу будь-яку вулицю, в даному випадку ребро графа. Як найти на графі G ейлеровий маршрут, в якому “S” - початкова вершина? Для цього необхідно пройти будь-яке ребро (S,x) інцидентне вершині “S”, а потім ще невикористане ребро, інцидентне вершині “x”. Кожен раз, коли листоноша приходить в деяку вершину, є невикористане ребро по якому листоноша покидає цю вершину. Дуги, по яким здійснений обхід, створюють цикл С1 . Якщо в цикл С1 ввійшли всі ребра графа G, то С1 є ейлеровим маршрутом (оптимальним для задачі). В іншому випадку треба створити цикл С2, який складається з невикористаних ребер і який починається з невикористаного ребра. Створення циклів С3, С4,..., продовжується доти, доки не будуть використані всі ребра графа. Далі треба об’єднати цикли С1,С2,С3,... в один цикл С, який містить всі ребра графа G. В цикл C кожне ребро графа входить лише один раз, і тому він є оптимальним рішенням задачі листоноші.Два цикла C1 і C2 можуть бути з’єднані тільки тоді, коли вони мають спільну вершину “х”. Для з’єднання двох таких циклів необхідно вибрати в якості початкового довільне ребро циклу С1 і рухатися вздовж його ребер до вершини “х”. Далі потрібно пройти всі ребра циклу С2 і повернутися у вершину “х”.На кінець, потрібно продовжити прохід ребер цикла С1 до повернення. Реалізація алгоритму (Java) :
public void printEulerTour() {
int vertex = 1;
/*
Визначення непарної вершини
*/
if (oddDegreeVertex() != -1) {
vertex = oddDegreeVertex();
}
/*
Вивід ейлерового шляху
*/
printEulerTourUtil(vertex);
return;
}
/*
Перевірка на непарність вершини,-1 - парна, інше - непарна
*/
public int oddDegreeVertex() {
int vertex = -1;
for (int node = 1; node <= numberOfNodes; node++) {
/*
Якщо залишок від ділення на 2 не дорівнює 0
тоді вершина має непарний степінь.
*/
if ((degree(node) % 2) != 0) {
vertex = node;
break;
}
}
return vertex;
}
/*
Обчислення степеня вершини
*/
public int degree(int vertex) {
int degree = 0;
for (int destinationvertex = 1; destinationvertex <= numberOfNodes; destinationvertex++) {
if (adjacencyMatrix[vertex][destinationvertex] == 1
|| adjacencyMatrix[destinationvertex][vertex] == 1) {
degree++;
}
}
return degree;
}
/*
Вивід шляху
*/
public void printEulerTourUtil(int vertex) {
for (int destination = 1; destination <= numberOfNodes; destination++) {
if (adjacencyMatrix[vertex][destination] == 1 && isVaildNextEdge(vertex, destination)) {
System.out.println("Вершина " + vertex + " з'єднана з вершиною " + destination + ".");
removeEdge(vertex, destination);//Видалення пройденого ребра
printEulerTourUtil(destination);
}}}
Інструкція по експлуатації:
Для роботи програми необхідно запустити файл Eyler.java . Спочатку необхідно ввести кількість вершин графа, далі матрицю суміжності. При введенні даних, відмінних від 1 або 0 в матриці суміжності програма припиняє роботу. Далі програма автоматично визначає, чи граф має ейлерів цикл або шлях і проводить обчислення та виводить результати у вигляді: “Вершина №ВЕРШИНИ1 з’єднана з вершиною №ВЕРШИНИ2 .”
Граф:
/
Результат виконання:
***HELP***
1. Програма розвязує задачу листоноші знаходячи ейлерів шлях або цикл в графі !
2. Для введення графу використовується матриця суміжності:
де 1 - вершина a з'єднана з вершиною b, 0 - не з'єднано!
3. При введенні чисел, відмінних від 0 або 1 програма завершує роботу !
4. Нумерація вершин графа починається з 1 з інкрементом в 1 (1,2,3...) !
Введіть кількість вершин в графі:6
Введіть матрицю суміжності:
0 1 0 0 1 0
1 0 1 0 1 1
0 1 0 1 0 1
0 0 1 0 1 1
1 1 0 1 0 1
0 1 1 1 1 0
Ейлерів шлях:
Вершина 3 з'єднана з вершиною 2.
Вершина 2 з'єднана з вершиною 1.
Вершина 1 з'єднана з вершиною 5.
Вершина 5 з'єднана з вершиною 2.
Вершина 2 з'єднана з вершиною 6.
Вершина 6 з'єднана з вершиною 3.
Вершина 3 з'єднана з вершиною 4.
Вершина 4 з'єднана з вершиною 5.
Вершина 5 з'єднана з вершиною 6.
Вершина 6 з'єднана з вершиною 4.
Висновок : в результаті виконання лабораторної роботи я вивчив алгоритм рішення задачі листоноші та реалізував її на мові Java .
13.05.2016 23:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора