Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка програмної системи алгоритму Дейкстри.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2010
Тип роботи:
Курсова робота
Предмет:
Засоби інженерії програмних систем
Група:
ПЗС-13м
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
|Національний університет "Львівська політехніка"
Кафедра програмного забезпечення
/
Курсова робота
з дисципліни "Засоби інженерії програмних систем"
на тему " Розробка програмної системи алгоритму Дейкстри "
Виконала:
ст. групи ПЗС-13м
Перевірив:
Кутельмах Р.К.
Львів – 2010
Зміст
1. Постановка задачі 3
2. Специфікація вимог 3
2.1 Призначення 3
2.2 Загальний опис 3
2.2.1 Характеристики продукту 3
2.2.2 Середовище функціонування 3
2.2.3 Обмеження проектування та реалізації 3
2.2.4 Документація користувача 3
2.3 Характеристики системи 3
2.3.1 Знаходження найкоротшого шляху між точками 3
2.3.2 Редагування матриці 4
2.3.2.1. Зміна кількості об’єктів 4
2.3.2.2. Зміна ваги відстаней між існуючими 4
2.4 Вимоги зовнішніх інтерфейсів 4
2.5 Користувацькі інтерфейси 4
2.6 Програмні інтерфейси 5
2.7 Інші нефункційні вимоги 5
2.8 Вимоги продуктивності 5
2.9 Вимоги надійності 5
3. Планування розробки 6
3.1 Призначення 6
3.2 Оцінка часу та необхідних ресурсів 6
3.2.1 Людські ресурси, задіяні в проекті 6
3.2.2 Етапи виконання проекту 6
3.2.3 Завантаження 7
3.2.4 Діаграма Ганта 7
4. Написання програми 8
4.1 Призначення 8
4.2 Розробка програми 8
4.2.1 Опис алгоритму Дейкстри 8
4.2.2 Пояснення алгоритму 9
4.3 Вибір засобів розробки програми 12
4.3.1 Мова програмування C++ 12
4.3.2 C++ Builder 13
4.4 Програмний код 14
4.5 Користувацький інтерфейс 17
5. Тестування програми 19
6. Висновки 20
Постановка задачі
Необхідно розробити програму призначену для пошуку найкортшого шляху між точками за допомогою матриці суміжності із застосуванням алгоритму Дейкстри. Програма повинна забезпечувати користувача засобами для керування процесом роботи програми. Результат повинен відображатись у формі списку з отриманими результатими
Специфікація вимог
Призначення
Цей документ описує основні характеристики, функції, середовище роботи та концепцію графічного інтерфейсу програмної системи алгоритму Дейкстри.
Програмна система алгоритму Дейкстри призначена для знаходження найкоротших шляхів між об’єктами де відстані між сусідніми об’єктами задані матрицую суміжності
Загальний опис
Характеристики продукту
1) Знаходження найкоротшого шляху між точками
2) Редагування матриці
1. Зміна кількості об’єктів
2. Зміна ваги відстаней між об’єктами
Середовище функціонування
Операційна система: Windows
Версія ОС: XP, Server 2003, Vista, Server2008, 7
Пристрій: ПК
Обмеження проектування та реалізації
Одним із основних обмежень при розробці програмного продукту алгоритму Дейкстри є розмір оперативної пам’яті. При заданні великої кількості точок можливе зависання програми. Більша детальна залежність між кількістю точок і оперативною пам’яттю буде визначена в процесі тестування.
Документація користувача
Документація користувача програмного продукту алгоритму Дейкстри надається у форматі HTML з детальним описом інтерфейсу програмного продукту.
Характеристики системи
2.3.1 Знаходження найкоротшого шляху між точками
Для отримання найкоротшого шляху необхідно задати кількість точок, ввести матрицю суміжності, задати початкову точку для обчислень та виконати обчислення
2.3.2 Редагування матриці
2.3.2.1. Зміна кількості об’єктів
Передбачена можливість зміни числа точок, для цього в полі необхідно задати кількість точок від 2 до 10
2.3.2.2. Зміна ваги відстаней між існуючими
Зміна ваги відстаней між існуючими точками здійснюється за допомогою редагування таблиці самої матриці суміжності
Вимоги зовнішніх інтерфейсів
Користувацькі інтерфейси
Цей розділ описує графічний інтерфейс користувача програмного продукту алгоритму Дейкстри. Рисунок 1 показує вигляд основного вікна програми перед початком роботи
/
Рис. 2.1 – Основне вікно програми перед початком роботи
Рисунок 2 показує вигляд вікна програми після завершення обчислень
/
Рис. 2.2 – Основне вікно програми після завершення роботи
Програмні інтерфейси
Для розробки інтерфейсу користувача використати мову програмування С++
Середовище розробки – C++ Builder
Інші нефункційні вимоги
Вимоги продуктивності
При обробці вимагається обмеження в часовому інтервалі 5 секунд. Завантажуватись програмний продукт повинен не довше 5 секунд. Користувач не повинен відчувати будь-яких затримок роботи програми.
Вимоги надійності
Пошкоджень та збоїв у роботі іншого програмного забезпечення при роботі програмного продукту алгоритму Дейкстри не передбачається.
Планування розробки
Призначення
Цей розділ описує план розробки програмної системи алгоритму Дейкстри. Програмна система призначена для визначення найкортшої відстані між вершинами
Оцінка часу та необхідних ресурсів
Людські ресурси, задіяні в проекті
Для виконання проекту MapEdit будуть задіяні наступні людські ресурси:
1 менеджер проекту (надалі – Менеджер проекту);
2 програмісти (надалі - Програміст1, Програміст2);
1 тестувальник (надалі – Тестувальник).
Загальна кількість – 4.
Етапи виконання проекту
Таблиця 1 містить основні етапи виконання проекту, кількість годин на кожен етап та людські ресурси, що в ньому задіяні.
Таблиця 1. Етапи виконання проекту.
Етап
К-ть годин
Ресурси
Дослідження існуючих напрацювань
40 годин
Програміст1+Програміст2
Написання та узгодження специфікації
20 годин
Менеджер проекту
Реалізація алгоритму Дейкстри
80 годин
Програміст1
Проектування архітектури
40 годин
МП+Програміст2
Написання тест-плану
40 годин
Менеджер проекту
Реалізація основних класів архітектури
40 годин
Програміст2
Тестування алгоритму Дейкстри
40 годин
Тестувальник
Виправлення помилок
40 годин
Програміст1
Тестування альфа-версії
40 годин
Тестувальник
Виправлення помилок
40 годин
Програміст1+Програміст2
Тестування бета-версії
40 годин
Тестувальник
Виправлення помилок
40 годин
Програміст1+Програміст2
Загальна кількість годин – 660
Завантаження
Таблиця 2 містить дані про завантаження кожного в проекті.
Таблиця 2.
Менеджер проекту
100 годин
Програміст1
240 годин
Програміст2
200 годин
Тестувальник
120 годин
Діаграма Ганта
Наступний рисунок (рис. 1) містить діаграму виконання проекту.
/
Написання програми
Призначення
Даний розділ містить інформацію про засоби та спосіб реалізації програмної системи алгоритму Дейкстри, також у ньому розглянуто опис вищезгаданого алгоритму.
Розробка програми
Опис алгоритму Дейкстри
Процедура знаходить шлях мінімальнї ваги в графі G = (V, E) заданому матрицею W в якій елемент wij рівний вазі ребра що з’єднує i-у и j-у вершини. При цьому, що всі елементи wij невід’ємні. Шлях шукається з вершини u1 до вершини номер u2 . Процедура використовує алгоритм Дейкстри. Для представлення ваги, равної нескінченності,використовується число GM, що передається в алгоритм. Это число можно задавати в залежності от конкретной задачі.
Алгоритм за яким здійснюється пошук полягає в наступному:
всім веpшинам приписується вага - число, d(i) := GM для всіх вершин крім вершини с номером u1 , а d(u1 ) := 0
всем веpшинам пpиписується мітка m(i) := 0
вершина u1 визнається поточною: t := u1
для всіх вершин в яких m(i) рівне 0, пересчитуємо вагу по формулі: d(i) := min{d(i), d(t)+W[t,i]}
серед вершин для яких m(i) = 0 шукаємо ту для якої d(i) мінімальна, але мінімум не знайдений, тобто. Вага всіх непомічених вершин рівна безкінечності (GM), то шляху не існує, покидаємо алгоритм
Інакше найдену вершину c мінімальною вагою приймаємо поточною і помічаємо (m(t) := 1)
якщо t = u2 , то найден путь ваги d(t), покидаемо алгоритм
переходимо на наступний крок.
Пояснення алгоритму
Зберігатимемо поточну мінімальну відстань до всіх вершин V (від даної вершини a) і на кожному кроці алгоритму намагатимемося зменшити цю відстань. Спочатку встановимо відстані до всіх вершин рівними нескінченості, а до вершини а — нулю.
/
Розглянемо виконання алгоритму на прикладі. Хай потрібно знайти відстані від 1-ої вершини до всіх інших. Кружечками позначені вершини, лініями — шляхи між ними («дуги»). Над дугами позначена їх «ціна» — довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини.
Крок 1
Ініціалізація. Відстань до всіх вершин графа V = /. Відстань до а = 0. Жодна вершина графа ще не опрацьована
/
Крок 2
Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуєм цей новий, коротший шлях як поточний найкоротший шлях до сусіда. /
Крок 3
Перший по порядку сусід 1-ї вершини — 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.
/
Кроки 4, 5
Аналогічну операцію проробляєм з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю. //
Крок 6
Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довів Дейкстра). Тому викреслимо її з графа, щоб відмітити цей факт.
/
Крок 7
Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7.
/І
знову намагаємося зменшити відстань до всіх сусідів 2-ої вершини, намагаючись пройти в них через 2-у. Сусідами 2-ої вершини є 1, 3, 4.
Крок 8
Перший (по порядку) сусід вершини № 2 — 1-а вершина. Але вона вже оброблена (або викреслена — див. крок 6). Тому з 1-ою вершиною нічого не робимо.
Крок 8 (з іншими вхідними данними)
Інший сусід вершини 2 — вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ої + відстань між 2-ою і 4-ою вершинамі = 7 + 15 = 22. Раз 22 < ∞, встановлюємо відстань до вершини № 4 рівним 22
. /
Крок 9
Ще один сусід вершини 2 - вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятована раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ої вершини не міняємо.
/
Крок 10
Всі сусіди вершини 2 проглянуті, заморожуємо відстань до неї і викреслюємо її з графа.
/
Кроки 11 — 15
По вже «відпрацьованій» схемі повторюємо кроки 2 — 6. Тепер «найближчою» виявляється вершина № 3. Після її «обробки» отримаємо такі результати:
/
Наступні кроки
Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).
///
Завершення виконання алгоритму
Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої складає 7, до 3-ої — 9, до 4-ої — 20, до 5-ої — 20, до 6-ої — 11 умовних одиниць.
Вибір засобів розробки програми
Для розробки даного програмного продукту обрана мова програмування С++ та середовище розробки C++ Builder
Мовою реалізації програми обрано C++, оскільки вона повністю відповідає вимогам проекту і забезпечить необхідну продуктивність роботи програми
Засобом розробки програми було обрано C++ Builder, оскільки дане середовище є зручним для написання програм на мові С++, дозволяє швидко створювати зручний користувацький інтерфейс, та забезпечує функціональність проекту.
Мова програмування C++
C++ (Сі-плюс-плюс) — універсальна мова програмування високого рівня з підтримкою декількох парадигм програмування: об'єктно-орієнтованої, узагальненої та процедурної. Розроблена Б'ярном Страуструпом (англ. Bjarne Stroustrup) в AT&T Bell Laboratories (Мюррей-Хілл, Нью-Джерсі) у 1979 році та названа «Сі з класами». Страуструп перейменував мову у C++ у 1983 р. Базується на мові Сі. Визначена стандартом ISO/IEC 14882:2003
У 1990-х роках С++ стала однією з найуживаніших мов програмування загального призначення.
Особливості
При створенні С++ прагнули зберегти сумісність з мовою С. Більшість програм на С справно працюватимуть і з компілятором С++. С++ має синтаксис, заснований на синтаксисі С.
Нововведеннями С++ порівняно з С є:
підтримка об'єктно-орієнтованого програмування через класи;
підтримка узагальненого програмування через шаблони;
доповнення до стандартної бібліотеки;
додаткові типи даних;
обробка винятків;
простори імен;
вбудовані функції;
перевантаження операторів;
перевантаження імен функцій;
посилання і оператори управління вільно розподіленою пам'яттю.
Переваги мови C++
Швидкодія. Швидкість роботи програм на С++ практично не поступається програмам на С, хоча програмісти отримали в свої руки нові можливості і нові засоби.
Масштабованість. На мові C++ розробляють програми для самих різних платформ і систем.
Можливість роботи на низькому рівні з пам'яттю, адресами, портами. (Що, при необережному використанні, може легко перетворитися на недолік.)
Можливість створення узагальнених алгоритмів для різних типів даних, їх спеціалізація, і обчислення на етапі компіляції, з використанням шаблонів.
Підтримуються різні стилі та технології програмування, включаючи традиційне директивне програмування, ООП, узагальнене програмування, метапрограмування (шаблони, макроси).
C++ Builder
C++ Builder— програмний продукт, інструмент швидкої розробки (RADінтегроване середовище програмування (IDE), система що використувується програмістамидля програмування на мові C++.
C++ Builder об'єднує в собі комплекс бібліотек (STL, VCL, CLX, MFC и др.), компілятор, відладчик, редактор коду і багато інших компонентів. Цикл розробки аналогічний Delphi. C++ Builder містить інструменти, які за допомогою drag-and-drop дійсно роблять розробку візуальною, що спрощує програмування завдяки WYSIWYG — редактору інтерфейса і тд.
/
Рис. 4.1 Інтерфейс середовища
Програмний код
В даному підрозділі наводиться код програми.
//---------------------------------------------------------------------------
#include <vcl.h>
#include <string.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
//#define n 6
int n;
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
const int z=10;
int q,i,j,m,v,l;
int a[z][z];
bool b[z];
int d[z];
String p[z];
for (l=0;l<n;l++) p[l] = "" ;
q=StrToIntDef(Edit1->Text, 1);
if ((q<1)||(q>n)) q=1;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
a[i][j] = StrToIntDef(StringGrid1->Cells[i][j], -1);
memset(b, 0, sizeof(b));
memset(d, 10000, sizeof(d));
d[q-1]=0;
for(i=0;i<n;i++)
{
m = 1000;
for(j=0;j<n;j++)
if ((d[j]<=m)&&(!b[j]))
{
m = d[j];
v = j;
}
b[v] = True;
for(j=0;j<n;j++)
if ((a[v][j] != -1) && (!b[j]) && (d[v]+a[v][j]<d[j]))
{
d[j] = d[v]+a[v][j];
p[j] = p[v]+" -> " + IntToStr(j+1);
}
}
ListBox1->Clear();
for (i=0;i<n;i++)
if(i!=q-1)
ListBox1->Items->Append(IntToStr(q) + " -> " + IntToStr(i+1) +
" : øëÿõ - " + IntToStr(q) + p[i]
+ "; äîâæèíà - " + IntToStr(d[i]));
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
int i,j;
n=StrToIntDef(Edit2->Text, 10);
for (i=0;i<10;i++)
for (j=0;j<10;j++)
StringGrid1->Cells[i][j] = ' ';
randomize();
for (i=0;i<n;i++) StringGrid1->Cells[i][i]= '0';
for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
{
StringGrid1->Cells[i][j] = IntToStr(random(10));
if (StringGrid1->Cells[i][j]=='0')
StringGrid1->Cells[i][j]=IntToStr(-1);
StringGrid1->Cells[j][i]=StringGrid1->Cells[i][j];
}
/* for (i=0;i<n;i++)
for (j=i+1;j<n;j++)
StringGrid1->Cells[i][j]=StringGrid1->Cells[j][i]; */
}
//---------------------------------------------------------------------------
Користувацький інтерфейс
Інтерфейс програми складається з головного вікна програми.
Головне вікно призначене для виконання усіх функціональних можливостей програми.
/
Рис. 4.2 Головне вікно програми
/
Рис. 4.3 Головне вікно програми
Тестування програми
Після того, як програму було спроектовано і розроблено необхідно виконати її тестування з метою виявлення можливих помилок в програмному коді, а також з метою перевірки відповідності програми вимогам.
В результаті тестування програми було виявлено ряд помилок у функціонуванні перелік яких наведено в таблиці 5.1.
Таблиця 5.1. Виявлені помилки
№
Помилка
Опис
Пріоритет
Статус
1.
Не задана початкова відстань до всіх вершин рівною /
При роботі програми видавася некоректний результат, тому масив з відстаннями між вершинами необхідно ініціювати за допомогою функції memset
Високий
Виправлено
2.
Високі затрати оперативної пам’яті при роботі із великими масивами.
При використанні великої кількості даних доцільно використовувати динамічні масиви. В межах дано ї програми задана обмеженість на кількість елементів до 10
Високий
Виправлено
3.
Некоректний вивід результатів
При тестуванні програми виявлено що результат відображеється некоректно. Для виправлення помилки було відредаговано стрічку виведення результату та приведено елементу результату до відповідних типів
Середній
Виправлено
4.
Неможливість редагування матриці суміжності.
При виконанні програми виявлена неспроможність відредагувати матрицю. Для випарвлення помилки змінено властивості елементу StringGrid.
Низький
Виправлено
5.
Некоректне відображення згенерованої матриці.
При генеруванні матриці елементи з більш ніж одним символом некоректно відображалися. Вправлено задяки перетворенню типів
Середній
Виправлено
Проведене тестування виявило ряд помилок, які успішно усунуто. Повторне тестування не виявило нових помилок, отже програма готова до використання.
Висновки
В межах даної курсової роботи було виконано розробку програмної системи призначеної для пошуку найкоритших шляхів між точками за допомогю алгоритму Дейкстри.
Основними етапами процесу розробки були:
Розробка програмної специфікації – етап в межах якого було чітко визначено усі вимоги, які висуваються до програми, як функціональні ні так і не функціональні;
Планування розробки – в межах цього етапу було визначено кількість і склад колективу розробників, їх обов’язки, побудовано діаграму Ганта проекту та оцінено його тривалість;
Написання програми – етап в межах якого було розроблено структуру програми, опрацьвано алгоритм роботи програми, виконано написання програмного коду та розроблено користувацький інтерфейс;
Тестування – в межах цього етапу було виконано тестування програми, виявлено та усунено усі знайдені дефекти;
Тестування показало, що після виправлення знайдених дефектів програма цілком відповідає вимогам і тому вважається завершеною.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора