Розробка програмної системи для обчислення найкоротших маршрутів з використанням алгоритму Дейкстри або Флойда та мови програмування С# - Курсовая работа

Алгоритм широко застосовується в програмуванні й технологіях, наприклад, його використовує протокол OSPF для усунення кільцевих маршрутів. Алгоритм був відкритий англійцем Елвіном Берлекемпом. Дейкстра не тільки привів метод побудови Shortest Path First, а й реалізував його на базі матриці суміжності (час виконання N2), а також показав, що тим же методом можна обчислити і MST (MST - Mininal Spanning Tree). Джонсон запропонував реалізацію алгоритму Прима (алгоритм Прима - алгоритм побудови мінімального кістякового дерева, це жадібний алгоритм) за допомогою d-парних частково впорядкованих повних дерев, а не за допомогою стандартних повних бінарних дерев. Реалізації черг з пріоритетами на базі повних дерев Фібоначчі, дозволяє зменшити час виконання алгоритмів до (E N*log(N)).В програмі повинна бути змодельована та реалізована ситуація, коли доречно застосовувати алгоритми пошуку найкоротших шляхів, такі як алгоритм Дейкстри або Флойда. В даній курсовій роботі передбачається ситуація з переливанням рідини з однієї місткості в іншу, при цьому час переливання між окремими посудинами може бути різним, тобто може виникнути така ситуація у якій існуватиме порядок переливання, який вигідніший, ніж переливання з першої посудини в останню. Користувачу повинно бути доступне ручне налаштування роботи програми, а саме: розміщення обєктів, кількість взаємодіючих елементів та їх положення відносно один одного - користувач повинен сам вирішувати ці питання на власний розсуд, але бажано так, щоб можна було знайти розвязання завдання, а не зайти у найгірший випадок, коли переливання з початкової посудини в останню відбувається без економії часу. Дані про час переливання повинні міститися у таблиці, яка відображатиме інформацію про взаємодію елементів один між одним, тобто і буде таблицею суміжності, на основі якої буде будуватись хід виконання програми.Найпростіша реалізація алгоритму Дейкстри потребує O(V2) дій. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.Розмір таблиці буде рівним (N 1)*(N 1), де N - кількість обєктів на формі, а ще одне поле та ще один стовпчик відводяться під найменування (тобто сервісні області з підказками по напрямкам відношень, що допоможуть користувачеві зорієнтуватись під час введення даних в таблицю). Відповідно рисунку 1.2 з елемента під іменем «1» (виділений зеленим кольором) здійснюється переливання в елемент під іменем «3» (виділено червоним кольором). Потім, якщо даний елемент задовольняє умову, тобто переливання в нього займає найменший час серед усіх можливих, від рядка з номером кінцевого елемента переходимо до стовпчика з відповідним номером. Аналогічно й переливання в ту ж посудину, переливання з будь-якої іншої посудину в початкову (адже якщо з початкової в кінцеву невигідно - тонема сенсу переливати в початкову) та переливання з кінцевої посудини в будь-яку іншу теж хибне. Знайшовши - перевіряємо, чи знайдене нове MIN в сумі із S менше R, якщо менше - переходимо у стовпчик під номером стрічки, в якій знаходилось мінімальне значення і виконуємо знову такі ж операції по пошуку мінімального значення в стовпчику та перевірки, чи менше воно в сумі із S за орієнтоване значення R до поки не знайдеться така місткість, з якої час переливання в останню посудину в сумі із S (затраченим часом на пошук) буде меншим ніж час переливання із першої посудини в останню (тобто за R).IMG_1507915d-390b-4b10-816c-2036e3076b27

IMG_b8af1bf1-1d45-4af3-b0b7-8dad0dc26444

IMG_8b13ac8e-a8cc-4c6c-8feb-e5cc23cb0656

IMG_a4e10ac3-8bcd-4cfe-bc20-54b5d8262d8e

IMG_b8d8b4a5-6107-4f8f-ab41-2aee31d37387

IMG_accaf620-7353-4730-90b7-34f0118df851Як уже було зазначено, програма буде реалізована мовою програмування C# версії 4.0. Інтерфейс у програмі буде нейтральної кольорової гамми, що підійде для більшості користувачів. Після запуску програми зявлятиметься вікно привітання, де буде вказано тему та призначення програми, а також її розробника. На цьому ж віні планується розмістити таймер приблизно на 10 секунд, після спрацьовування якого автоматично зявлятиметься головне вікно а вікно привітання ховатиметься. Планується, що головне вікно відразу після запуску розгортатиметься на весь екран і програма функціонуватиме в повноекранному режимі.Рисунок 2.1 - Блок-схема основного алгоритмуМеню (англ. menu) - список варіантів (режимів, команд, відповідей тощо), що виводяться на екран дисплею і пропонуються користувачу для вибору. Меню являє собою набір таких елементів: - рядок меню (англ. menu bar) - основна частина меню, яка постійно знаходиться у вікні програми (рідше, ховається і зявляється при певних діях користувача). Вибір елемента головного меню зазвичай призводить до виклику зявляється під головним підменю, яке в свою чергу може містити підменю; Пункти спливаючих меню можуть бути відзначені (англ. checked), пр

ЗМІСТ

ВСТУП

1. ТЕХНІКО-ЕКОНОМІЧНЕ ОБҐРУНТУВАННЯ ТЕХНІЧНОГО ЗАВДАННЯ НА КУРСОВУ РОБОТУ

1.1 Вимоги користувача

1.2 Аналіз предметної області

1.3 Вибір методу вирішення основної задачі

2. РОЗРОБКА АЛГОРИТМІВ РОЗВЯЗКУ ЗАДАЧІ

2.1 Алгоритм побудови робочого поля

2.2 Покроковий алгоритм

2.3 Розробка меню

3. ПРОГРАМНА РЕАЛІЗАЦІЯ

3.1 Вибір мови програмування

3.2 Програмування інтерфейсу

3.3 Розробка програми

4. ТЕСТУВАННЯ, ПЕРЕВІРКА ПРАВИЛЬНОСТІ РОБОТИ

4.1 Готування тестування

4.2 Аналіз результатів роботи

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ

ЛІТЕРАТУРА

ДОДАТОК А