Міністерство освіти і науки України

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

Кафедра автоматизованих систем управління

Курсова робота

з дисципліни «Проблемно-орієнтовані мови програмування»

на тему

Пошук найкоротшого шляху на орієнтованому графі

Виконав:

Студент групи КН-22з

Василашко Володимир

Керівник:

Кустра Н.О.

Львів 2011


Міністерство освіти та науки України

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

Кафедра автоматизованих систем управління

Завдання на курсову роботу

з дисципліни «Проблемно-орієнтовні мови програмування»

Прізвище,ім’я студента Василашко Володимир

Група КН-22з

Тема курсової роботи Пошук найкоротшого шляху на орієнтованому графі


Зміст

Вступ

1.Постановка завдання та сфера її застосування

2. Теоретична частина

2.1 Загальні відомості про графи

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

3. Особливості роботи в середовищі

4. Програмна реалізація

4.1 Опис алгоритму та структури програми

4.2 Опис програмних засобів

5. Інструкція користувача

Висновок

Перелік посилань

Додаток А Текст програми

Додаток Б Результат

Додаток В Схема програмної реалізації алгоритму Дейкстри


ВСТУП

Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається. Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від перебування оптимального маршруту між двома об'єктами на місцевості (наприклад, найкоротший шлях від будинку до університету), в системах автопілота, для знаходження оптимального маршруту при перевезеннях, комутації інформаційного пакету в Internet і т. д. Найкоротший шлях розглядається за допомогою певного математичного об'єкту, званого графом. Існують три найбільш ефективних алгоритму знаходження найкоротшого шляху:

• алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);

• алгоритм Флойда (для знаходження оптимального маршруту між усіма парами вершин);

• алгоритм Йена (перебування k-оптимальних маршрутів між двома вершинами).

Зазначені алгоритми легко виконуються при малій кількості вершин у графі. При збільшенні їх кількості завдання пошуку найкоротшого шляху ускладнюється. Тут на допомогу приходить сучасна техніка. Комп'ютерні засоби та інформаційні технології підвищили можливості такого всеосяжного методу вивчення і створення, як моделювання об'єктів, явищ і процесів - як тих, що існують у природі, так і тих, що створюються людиною штучно. Кількість об'єктів ускладнювалися, збільшувалися, і натурне моделювання (макети споруд) стало невигідним, не економним. Тому для вивчення почали застосовувати математику. Використання математичних моделей - рівняння, нерівності, формули і тому подібне називається математичним моделюванням, для розвитку і пристосування якого потрібні були ефективні чисельні методи. Реалізувати великий потенціал математичного моделювання неможливо без потужних засобів автоматизації обчислень, якими є комп'ютери. Завдяки появі комп'ютерів і розвитку інформаційних технологій створюються методи та засоби комп'ютерного моделювання, здатні вирішувати складні практичні завдання, такі як управління великими енергетичними системами, створення достовірних прогнозів погоди або врожаю, моделювання регіональних і загальнодержавних систем, проектування літаків, кораблів тощо. Комп'ютерна модель - це розміщена в комп'ютері сукупність засобів, що реалізують концепцію обчислення. Для реалізації комп'ютерної моделі, велике значення має такий науковий напрямок, як програмування. Без нього комп'ютер це просто набір різних пристроїв, мікросхем, який не може бути корисним. Великі програми із-за своєї складності нерідко містять помилки, які можуть стати причиною матеріальних збитків, а іноді й загрожувати життю людей (наприклад, при управлінні авіапольотом). У результаті боротьби з проблемою складності програмного коду були вироблені три нові концепції програмування: а) об'єктно-орієнтоване програмування (ООП); б) уніфікована мова моделювання (UML); в) спеціалізовані засоби розробки програмного забезпечення; З усіх об'єктно-орієнтованих мов С + + є найбільш широко використовуваним. І саме з його допомогою в даному курсовому проекті реалізується алгоритм Дейкстри.


1. ПОСТАНОВКА ЗАВДАННЯ І СФЕРА ЇЇ ЗАСТОСУВАННЯ

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



Информация о работе «Пошук найкоротшого шляху на орієнтованому графі»
Раздел: Информатика, программирование
Количество знаков с пробелами: 15687
Количество таблиц: 1
Количество изображений: 7

Похожие работы

Скачать
108557
5
34

... зноманітними типами транспортних засобів з урахуванням обмеження на обсяг робот, що можуть виконати транспортні засоби. РОЗДІЛ 3 МАТЕМАТИЧНА МОДЕЛЬ ТРАНСПОРТНОЇ СИСТЕМИ ПІДПРИЄМСТВА   3.1 Структура моделі У якості структурної моделі транспортної системи підприємства можна запропонувати схему, що складається з трьох рівнів. Необхідно відзначити, що з метою деякого спрощення задачі розгляда ...

Скачать
20329
3
4

... і певну кількість нових машин). Більшість дискретних і комбінаторних задач можна вирішити шляхом перебору. Проте перебірні методи мають експоненційну складність. Проблема: знайти метод вирішення експоненційних задач за поліноміальний час. 3.1 Планування в просторі станів. Основні поняття теорії графів Граф – сукупність вершин і дуг. Для комп’ютерного опису графу використовуються: матриця і ...

Скачать
39159
0
35

... графа рівно один раз. Означення.3.2 . Зв’язний граф називається напівгамільтоновим , якщо існує ланцюг , який проходить через кожну його вершину рівно один раз. Не дивлячись на подібність в означеннях ойлерових та гамільтонових графів, відповідно теорії для цих класів графів сильно відрізняються. До теорії гамільтонових графів відноситься і задача про бродячого тор-говця, або задача про комі ...

Скачать
39276
23
35

... оцінка складності алгоритму - О(n*log(n)). Даний алгоритм має сенс застосування лише на великих обсягах даних від 500-1000 елементів. Тільки в цьому випадку можна побачити виграш алгоритму в ефективності. Для менших обсягів даних він малопридатний. 3 Синтез машини Тьюрінга 3.1 Загальні відомості Машина Тьюрінга - це кінцевий автомат, забезпечений безкінченою стрічкою і читаючою/записуючою голівкою ...

0 комментариев


Наверх