Ім'я файлу: ДО_Курсова1.docx
Розширення: docx
Розмір: 633кб.
Дата: 21.10.2021
скачати
Пов'язані файли:
avtomatizirovannaya-sistema-diagnostiki-i-ispytaniy-oborudovaniy
Діагностика карбюраторних двигунів.doc
Конспект лекцій ЕК.docx

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ БУДІВНИЦТВА І АРХІТЕКТУРИ

КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ПРОЕКТУВАННЯ ТА ПРИКЛАДНОЇ МАТЕМАТИКИ


КУРСОВА РОБОТА З ДИСЦИПЛІНИ: «ДОСЛІДЖЕННЯ ОПЕРАЦІЙ»


на тему: «Рішення задач алгоритмом Дейкстри»

варіант: «Вибір схеми транспортування вантажів»

Виконав студент 3-го курсу групи КН - 31

Маріупольський Олексій Костянтинович

Спеціальності 122. «Комп’ютерні науки»

Терентьєв О.О.

Керівник: д.т.н., професор Терентьєв О.О.

Національна шкала_______________________

Кількість балів: _________ Оцінка: ECTS ___

Київ – 2021 р.

ЗМІСТ



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

  2. Розробка математичної моделі

  3. Аналіз та вибір методів рішення задач

    1. Вибір методу

    2. Алгоритм Дейкстри

  4. Розв’язання задач алгоритмом Дейкстри

    1. Схема структури програми

    2. Схема алгоритму Дейкстри

    3. Рішення задачі

    4. Код програми

5.Висновок

  1. Результати програми

  2. Список використаної літератури


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


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



З пунктів 1 і 8 вантаж може тільки відправлятися, а пункти 2–7 можуть також і отримувати вантаж. Числа, приписані дугам, дорівнюють відстаням між відповідними пунктами.

2. Розробка математичної моделі:

Алгоритм використовує три масиву з N (= числу вершин мережі) чисел кожен. Перший масив A містить мітки з двома значення: 0 (вершина ще не розглянута) і 1 (вершина вже розглянута); другий масив B містить відстані - поточні найкоротші відстані від до відповідної вершини; третій масив з містить номери вершин - k-й елемент З [k] є номер передостанній вершини на поточному найкоротшому шляху з Vi в Vk.

Матриця відстаней D [i, k] задає довжини дузі D [i, k]; якщо такий дуги немає, то D [i, k] присвоюється велика кількість Б, рівне "машинної нескінченності".

Тепер можна описати:

  1. (ініціалізація). У циклі від 1 до N заповнити нулями масив A; заповнити числом i масив C; перенести i-й рядок матриці D в масив B, A [i]: = 1; C [i]: = 0 (i - номер стартовою вершини)

2. (загальний крок). Hайти мінімум серед невідмічених (тобто тих k, для яких A [k] = 0); нехай мінімум досягається на індексі j, тобто B [j] <= B [k] Потім виконуються наступні операції:

A [j]: = 1; якщо B [k]> B [j] + D [j, k], то (B [k]: = B [j] + D [j, k]; C [k]: = j) (Умова означає, що шлях Vi. Vk довше, ніж шлях Vi. Vj Vk). (Якщо все A [k] відзначені, то довжина шляху від Vi до Vk дорівнює B [k]. Тепер треба) перерахувати вершини, що входять в найкоротший шлях).

3. (видача відповіді). (Шлях від Vi до Vk видається в зворотному порядку наступною процедурою :)

z: = C [k];

Видати z;

z: = C [z]. Якщо z = О, то кінець, інакше перейти до 3.2.

Для виконання алгоритму потрібно N раз переглянути масив B з N елементів, тобто алгоритм Дейкстри має квадратичну складність: O (n2).

3. Аналіз та вибір методів рішення задач


Розглянемо методи, за допомогою яких можна розв’язати дану задачу, а також переваги та недоліки методів вирішення задач з орієнтованими графами.

3.1 Вибір методу

Вибираємо для вирішення завдання алгоритм Дейкстри. Цей алгоритм запропонований в 1959 р Дейкстрой, вважається одним з найбільш ефективних алгоритмів розв'язання задачі.

    1. Алгоритм Дейкстри

Описуваний алгоритм дозволяє знаходити в графі найкоротший шлях між двома виділеними вершинами s і t при позитивних довжинах дуг. Головна ідея, що лежить в основі алгоритму Дейкстри, гранично проста. Припустимо, що нам відомі m вершин, найближчих до вершини s (близькість будь-якої вершини x до вершини s визначається довжиною найкоротшого шляху, що веде з s в x). Нехай також відомі самі найкоротші шляхи, що з'єднують вершину s з виділеними m вершинами).

Покажемо тепер, як може бути визначена (m + 1) - найближча до s вершина.

Зафарбуємо вершину s і m найближчих до неї вершин. Побудуємо для кожної не пофарбованої вершини y шляху, безпосередньо з'єднують за допомогою дуг (х, у) кожну пофарбовану вершину х з у. Виберемо з цих шляхів найкоротший, і будемо вважати його умовно найкоротшим шляхом з вершини s у вершину y.

Яка ж з нефарбованих вершин є (m + 1) - найближчій до s вершиною? Та, для якої умовно найкоротший шлях має найменшу довжину.

Це обумовлюється тим, що найкоротший шлях з вершини s в (m +1) -у найближчу вершину при позитивному значенні довжин всіх дуг повинен містити в якості проміжних лише пофарбовані вершини, тобто вершини, що входять в число m вершин, найближчих до вершини s.

Отже, якщо відомі m найближчих до s вершин, то (m + 1) - найближча до s вершина може бути знайдена так, як це описано вище. Починаючи з m = 0, описана процедура може повторюватися до тих пір, поки не буде отримано найкоротший шлях, що веде з вершини s до вершини t.

Маючи на увазі наведені міркування, ми можемо тепер формально описати алгоритм Дейкстри.

  1. Кожній вершині X в ході алгоритму присвоюється число d (x), яка дорівнює довжині найкоротшого шляху з вершини S в вершину X і включає тільки пофарбовані вершини. Покласти d (s) = 0 і d (x) = ∞ для всіх інших вершин графа. Офарблюємо вершину S і вважаємо y = S, де y - остання пофарбована вершина.

  2. Для кожної не пофарбованої вершини X перераховується величина d (x) за такою формулою:

d(x)=min{d(x); d(y)+ ay,x} (1)

3. Якщо d (x) = ∞ для всіх нефарбованих вершин, то алгоритм закінчується так як відсутні шляхи з вершини S в нефарбовані вершини. Інакше забарвлюється та вершина, для якої величина d (x) є мінімальною. Забарвлюється і дуга, що веде в цю вершину відповідно до вираження (1) і вважаємо y = x.

  1. Якщо y = t, найкоротший шлях з s в t знайдений. Інакше переходимо до кроку 2.

  2. Кожен раз забарвлюється вершина і дуга, що заходить в цю вершину. Пофарбовані дуги не можуть утворювати цикл, а утворюють у вихідному графі дерево з коренем (початком) в вершині s. Це дерево називають орієнтованим деревом найкоротших шляхів. Шлях з s в t належить цьому дереву. При пошуку одного найкоротшого шляху процедура нарощування завершується при досягненні кінцевої вершини цього шляху. Нам же необхідно отримати всі найкоротші шляхи починаються в вершині №1. Для цього процедуру нарощування орієнтованого дерева триває до тих пір, поки всі вершини не будуть включені. Таким чином, ми отримуємо орієнтоване дерево найкоротших шляхів, яке і є деревом графа.

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

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

Складність алгоритму Дейкстри залежить від способу знаходження вершини v, а також способу зберігання безлічі невідвіданих вершин і способи оновлення міток.

4.Розв’язання задач алгоритмом Дейкстри.

4.1Схема структури програми:



Програма виводить мінімальний шлях між двома зазначеними вершинами в графі і його довжину.

При запуску програми на екран виводиться запит про введення ваг ребер досліджуваного графа. Дані, введені користувачем, відображаються у вигляді матриці суміжності, в якій не існують ребра позначаються нулями. Після зазначеним ребрах присвоюється значення 65535, яке приймається за нескінченність. Наступним етапом виконання програми є запит про введення номерів вершин, між якими необхідно дізнатися шлях. У разі, якщо початкова і кінцева вершини збігаються, з'являється повідомлення і робота програми завершується. В іншому випадку виконується безпосередньо алгоритм Дейкстри. Результатом програми є висновок на екран вершин, через які проходить мінімальний шлях, а також висновок довжини маршруту. Якщо шляху між заданими точками не існує - виводиться відповідне повідомлення.

4.2 Схема алгоритму Дейкстри





    1. Рішення задачі


















0
9
0
3
0
0
0
0



9
0
2
0
7
0
0
0



0
2
0
2
4
8
6
0



3
0
2
0
0
0
5
0



0
7
7
4
0
10
0
9



0
0
8
0
10
0
7
12



0
0
0
6
5
7
0
10



0
0
0
0
9
12
10
0

Після введення значень до програми, нам вибиває шлях та найменьше значення:



В прикладі вибрано найменший шлях від точки 1 до точки 4, тому отримали наші віхідні дані.

    1. Код програми:

  1. #include

  2. #include

  3. #include

  4. #include

  5. #include

  6. #define word unsigned int

  7. using namespace std;

  8. int i, j, n, p, xn, xk;

  9. int flag[11];

  10. word c[11][11], l[11];

  11. char s[80], path[80][11];



  13. int min(int n)

  14. {

  15. int i, result;

  16. for (i = 0;i < n;i++)

  17. if (!(flag[i])) result = i;

  18. for (i = 0;i < n;i++)

  19. if ((l[result] > l[i]) && (!flag[i])) result = i;

  20. return result;

  21. }



  23. word minim(word x, word y)

  24. {

  25. if (x < y) return x;

  26. return y;

  27. }



  29. void main()

  30. {

  31. setlocale(LC_ALL, "Ukrainian");

  32. cout << "Введiть кiлькiсть точек: ";

  33. cin >> n;

  34. for (i = 0;i < n;i++)

  35. for (j = 0;j < n;j++) c[i][j] = 0;

  36. for (i = 0;i < n;i++)

  37. for (j = i + 1;j < n;j++)

  38. {

  39. cout << "Введiть вiдстань вiд x" << i + 1 << " до x" << j + 1 << ": ";

  40. cin >> c[i][j];

  41. }

  42. cout << " ";

  43. for (i = 0;i < n;i++) cout << " X" << i + 1;

  44. cout << endl << endl;

  45. for (i = 0;i < n;i++)

  46. {

  47. printf("X%d", i + 1);

  48. for (j = 0;j < n;j++)

  49. {

  50. printf("%6d", c[i][j]);

  51. c[j][i] = c[i][j];

  52. }

  53. printf("\n\n");

  54. }

  55. for (i = 0;i < n;i++)

  56. for (j = 0;j < n;j++)

  57. if (c[i][j] == 0) c[i][j] = 65535; //бесконечность

  58. cout << "Введiть начальну точку: ";

  59. cin >> xn;

  60. cout << "Введiть кiнцеву точку: ";

  61. cin >> xk;

  62. xk--;

  63. xn--;

  64. if (xn == xk)

  65. {

  66. cout << "Начальна i кiнцева точка спiвпадуть." << endl;



  68. return;

  69. }



  71. for (i = 0;i < n;i++)

  72. {

  73. flag[i] = 0;

  74. l[i] = 65535;

  75. }

  76. l[xn] = 0;

  77. flag[xn] = 1;

  78. p = xn;

  79. _itoa_s(xn + 1, s, 10);

  80. for (i = 1;i <= n;i++)

  81. {

  82. strcpy_s(path[i], "X");

  83. strcat_s(path[i], s);

  84. }

  85. do

  86. {

  87. for (i = 0;i < n;i++)

  88. if ((c[p][i] != 65535) && (!flag[i]) && (i != p))

  89. {

  90. if (l[i] > l[p] + c[p][i])

  91. {

  92. _itoa_s(i + 1, s, 10);

  93. strcpy_s(path[i + 1], path[p + 1]);

  94. strcat_s(path[i + 1], "-X");

  95. strcat_s(path[i + 1], s);

  96. }

  97. l[i] = minim(l[i], l[p] + c[p][i]);

  98. }

  99. p = min(n);

  100. flag[p] = 1;

  101. } while (p != xk);

  102. if (l[p] != 65535)

  103. {

  104. cout << "Шлях: " << path[p + 1] << endl;

  105. cout << "Довжина шляху: " << l[p] << endl;

  106. }

  107. else

  108. cout << "Такого шляху не iснує!" << endl;



  110. }

5. Висновок:

Таким чином, в процесі створення даного проекту розроблена програма, яка реалізує алгоритм Дейкстри в Microsoft Visual C ++ 6.0. Її недоліком є ​​примітивний користувальницький інтерфейс. Це пов'язано з тим, що програма працює в консольному режимі, не додають до складності мови складність програмного віконного інтерфейсу

Також були поглиблені знання, отримані в процесі виконання курсової роботи з предмету «Дослідження операцій».

6. Список використаної літератури




  1. Дослідження операцій: навчальний посібник / О.О. Терентьєв, О.В. Доля, О.І. Баліна. – К.: Компрінт, 2020. – 116 с.:іл.

  2. Дослідження операцій: методичні вказівки до виконання курсових робіт /Уклад. О.О. Терентьєв.– К.: КНУБА, 2020. – 24 с.

  3. Дослідження операцій: методичні вказівки до виконання практичних робіт /Уклад. О.О. Терентьєв.– К.: КНУБА, 2020. – 23 с.

  4. http://library.knuba.edu.ua

  5. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М.: "Вильямс", 2006. - С.189-195.

  6. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М.: "Вильямс", 2006. - С.1296.

  7. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование", Минск, Вышейшая школа, 2001г.

  8. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

  9. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.

  10. Белов Теория Графов, Москва, "Наука", 1968.

  11. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.

  12. Оре О. Теория графов. - М.: Наука, 1980.

скачати

© Усі права захищені
написати до нас