1. Постановка завдання
Справжня курсова робота моделює логічну задачу, яка складається з наступних частин:
1) Вивчення конкретного розділу дискретної математики.
2) Рішення 5-ти задач з вивченої теми з методичним описом.
3) Розробка та реалізація у вигляді програми алгоритму з вивченої теми. Розробка програмного інтерфейсу.
2. Введення
2.1 Теоретична частина
дискретний математика програма інтерфейс
Нехай дано граф G = (X, Г), дугам якого приписані ваги (вартості), що задаються матрицею C = [c ij ]. Задача про найкоротший шляху полягає в знаходженні найкоротшого шляху від заданої початкової вершини sX до заданої кінцевої вершини tX, за умови, що такий шлях існує, тобто за умови tR (s). Тут R (s) - безліч, досяжне з вершини s. Елементи c ij матриці ваг C можуть бути позитивними, негативними або нулями. Єдине обмеження полягає в тому, щоб в G не було циклів з негативним сумарною вагою. Якщо такий цикл Ф все ж існує і x i - деяка його вершина, то, рухаючись від s до x i , обходячи потім Ф досить багато раз і потрапляючи нарешті в t, ми отримаємо шлях з як завгодно малим () вагою. Таким чином, в цьому випадку найкоротшого шляху не існує.
Якщо, з іншого боку, такі цикли існують, але виключаються з розгляду, то знаходження найкоротшого шляху (простий ланцюга) між s і t еквівалентно знаходженню в цьому графі найкоротшого Гамільтона шляху з кінцевими вершинами s і t. Це можна угледіти з наступного факту. Якщо з кожного елемента c ij матриці ваг C відняти досить велике число L, то вийде нова матриця ваг C '= [c ij '], всі елементи c ij 'якої негативні. Тоді найкоротший шлях від s до t - з виключенням негативних циклів - необхідно буде Гамільтона, тобто проходить через всі інші вершини. Так як вага будь-якого гамильтонова шляху з матрицею ваг C 'дорівнює вазі цього шляху з матрицею ваг C, але зменшеному на постійну величину (n-1) Г— L, то найкоротший шлях (Проста ланцюг) від s до t з матрицею C 'буде найкоротшим Гамільтона шляхом від s до t при первісній матриці C. Задача про знаходження найкоротшого Гамільтона шляху набагато складніше, ніж задача про найкоротшому шляху. Тому ми будемо припускати, що всі цикли в G мають невід'ємні сумарна вага. Звідси також випливає, що неорієнтовані дуги (ребра) графа G не можуть мати негативні ваги.
Наступні завдання є безпосередніми узагальненнями сформульованої вище задачі про найкоротшому шляху.
1) Для заданої початкової вершини s знайти найкоротші шляхи між t і всіма іншими вершинами x i X.
2) Знайти найкоротші шляхи між усіма парами вершин.
Окремі випадки, коли всі c ij ненегативні, зустрічаються на практиці досить часто (наприклад, коли c ij є відстанями), так що розгляд цих спеціальних алгоритмів виправдано. Ми будемо припускати, що матриця не задовольняє, взагалі кажучи, умові трикутника, тобто не обов'язково для всіх. В іншому випадку найкоротший шлях між x j і x j складається з однієї єдиної (x j x j ) дуги, якщо така дуга існує, і задача стає тривіальною. Якщо в графі G дуга (x j x j ) відсутня, то її вага покладається рівним.
На практиці часто потрібно знайти не тільки найкоротший шлях, але також другий, третій і т.д. найкоротші шляхи в графі. Маючи цими результатами, можна вирішити, який шлях вибрати в якості найкращого. Крім того, другий, третій і т.д. найкоротші шляху можна використовувати при аналізі В«чутливостіВ» завдання про найкоротший шляху.
Існують також задачі знаходження в графах шляхів з максимальною надійністю і з максимальною пропускною здатністю. Ці завдання пов'язані із завданням про найкоротший шляху, хоча в них характеристика шляху (скажімо, вага) є не сумою, а деякої іншої функцією характеристик (ваг) дуг, що утворюють шлях. Такі завдання можна переформулювати як завдання про найкоротший шлях. Однак можна вчинити інакше: безпосередньо пристосувати для їх вирішення ті методи, які застосовуються в задачах про найкоротший шлях.
Існує також випадок, коли враховуються і пропускні спроможності, і надійності дуг. Це приводить до задачі про шляхи з найбільшою очікуваною пропускною здатністю. І хоча така приватна завдання не може бути вирішена за допомогою техніки відшукання найкоротшого шляху, але ітераційний алгоритм, що використовує цю техніку в якості основного кроку, є ефективним методом отримання оптимальної відповіді.
Найбільш ефективний алгоритм розв'язання задачі про найкоротший (s - t) - шляху спочатку дав Дейкстра. У загальному випадку цей метод заснований на приписуванні вершин часових позначок, причому позначка вершини дає верхню межу довжини шляху від s до цієї вершини. Ці позначки (їх величини) поступово зменшуються за допомогою деякої ітераційної процедури, і на кожному кроці ітерації точно одна з тимчасових позначок стає постійною. Останнє вказує на те, що позначка вже не є верхньою кордоном, а дає точну довжину найкоротшого шляху від s до розглянутої вершині. Опишемо цей метод докладно.
Алгоритм Дейкстри ()
Нехай l (x i ) - позначка вершини x i .
Присвоєння початкових значень
Крок 1 . Покласти і вважати цю позначку постійною. Покласти для всіх x i s і вважати ці позначки тимчасовими. Покласти p = s.
Оновлення позначок
Крок 2 . Для всіх, позначки яких тимчасові, змінити позначки у відповідності з наступним виразом:.
Перетворення помітки в постійну
Крок 3 . Серед всіх вершин з тимчасовими позначками знайти таку, для якої.
Крок 4 . Вважати позначку вершини x i * постійної і покласти p = x i *.
Крок 5 . (1) ( Якщо треба знайти лише шлях від s до t . )
Якщо p = t, то l (p) є довжиною найкоротшого шляху. Останов.
Якщо pt, перейти до кроку 2.
(2) ( Якщо потрібно знайти шляху від s до всіх інших вершин .)
Якщо всі вершини відзначені як постійні, то ці позначки дають довжини найкоротших шляхів. Останов.
Якщо деякі помітки є тимчасовими, перейти до кроку 2.
Доказ того, що вищенаведений алгоритм дійсно дає найкоротші шляхи, надзвичайно просте, дамо начерк цього докази.
Припустимо, що на деякому етапі постійні позначки дають довжини найкоротших шляхів. Нехай S 1 - безліч вершин з цими позначками, а S 2 - безліч вершин з тимчасовими позначками. В кінці кроку 2 кожною ітерації тимчасова позначка l (x i ) дає найкоротший шлях від s до x i , що проходить повністю по вершин безлічі S 1 . (Так як при кожній ітерації в безліч S 1 включається тільки одна вершина, то оновлення позначки l (x i ) вимагає тільки одного порівняння на кроці 2.)
Нехай найкоротший шлях від s до x i * не проходить повністю по S 1 і містить по крайнього міру одну вершину з S 2 , і нехай x j S 2 - перша така вершина в цьому шляху. Так як за припущенням c ij ненегативні, то частина шляху від x j до x i * повинна мати невід'ємні вага і. Це, однак, суперечить твердженням, що l (x i *) - найменша тимчасова позначка, і, отже, найкоротший шлях до x i * проходить повністю по вершинах безлічі S 1 , і тому l (x i *) є його довжиною.
Так як спочатку безліч S 1 одно (s) при кожній ітерації до S 1...
