Автор работы: Пользователь скрыл имя, 04 Мая 2013 в 10:02, курсовая работа
Цель работы: написание программы, которая создает сеть и находит кратчайший путь от одной заданной вершины в другую.
Задачи курсовой работы:
1.Изучить основные алгоритмы поиска кратчайшего пути;
2.Выбрать один алгоритм из изученных и написать приложение для автоматизации поиска этого пути и расчета его стоимости.
Актуальность курсовой работы в том, что на практике, часто возникает необходимость поиска кратчайшего пути в таких задачах, как составление расписания движения транспортных средств, планирование производства, замене оборудования на производстве и многих других. Умение решать эти задачи позволяет оптимизировать деятельность в разных сферах жизни.
Введение…………………………………………………………………………4
1. Сетевые модели.............................................................................................5
1.1. Основные определения.........................................................................5
1.2. Задача поиска кратчайшего пути.........................................................6
1.3. Алгоритмы определения кратчайшего пути......................................6
1.4. Примеры................................................................................................12
2. Программа и руководство пользователя...................................................15
2.1. Модульная организация программы..................................................15
2.2. Текст программы..................................................................................16
2.3. Руководство пользователя...................................................................18
Приложение. Тестовый пример...........................................................................19
Заключение............................................................................................................21
Список литературы...............................................................................................22
1) Unit1 — модуль реализации класса TForm1 проведения всех вычислений нахождения кратчайшего пути.
Методы класса TForm.
procedure Button1Click - реализация алгоритма поиска кратчайшего пути;
procedure StringGrid1DrawCell - процедура закрашивания нулевых элементов.
2) Unit3 — модуль реализации класса TForm3 - О программе.
2.2. Текст программы
В данном пункте приводятся тексты отдельных наиболее значимых разработанных классов приложения и их ключевых методов.
procedure TForm1.Button1Click(Sender: TObject); // поиск кратчайшего пути
var
Put:array [1..NVertex] of Integer;
i,j,x,m:integer;
weight:Longint;
begin
If StrToInt(Edit2.Text)>
MessageDlg('Такой вершины нет!', mtWarning,[mbOK],0);
exit;
end;
x0:=StrToInt(Edit1.Text)-1;
z:=StrToInt(Edit2.Text)-1;
Nx:=CountPerSpinEdit.Value;
Nx:=nX-1;
for i:=0 to Nx do begin
for j:=0 to Nx do begin
We[i,j]:=StrToInt( StringGrid1.Cells[i+1,j+1]);
if We[i,j]=0 then We [i,j]:=$7fff;
end;
end;
for x:=0 to NX do begin
Mark[x]:=False;
Dist[x]:=$7ffffff;
end;
y:=x0; // просматриваемая вершина
Mark[y]:=True;
Dist[y]:=0;
Prev[x0]:=x0;
while not Mark [z] do begin
for x:=0 to Nx do
if not Mark[x] and (Dist[x]>Dist[y]+We[y,x]) then begin
Dist[x]:=Dist[y]+We[x,y];
Prev[x]:=y;
end;
// Поиск новой вершины y принадлежащей Х с минимальной временной меткой
weight:=$7fffff;
for x:=0 to Nx do if not Mark[x] then
if weight>Dist[x] then begin
weight:=Dist[x];
y:=x;
end;
Mark[y]:=True;
end;
x:=z;
RichEdit1.Text:='Вершины пути= ';
while x<>x0 do begin
RichEdit1.Lines.Strings[0]:=
x:=Prev[x];
end;
RichEdit1.Lines.Strings[0]:=
Edit3.Text:='Длина кратчайшего пути='+IntToStr(Dist[z]);
end;
2.3. Руководство пользователя
При разработке программы применялся принятый в среде Delphi объектно-ориентированный подход для разработки интерфейса. При реализации алгоритмов обработки данных использовался структурный подход. В рабочем окне программы поле для ввода данных и вывода результатов решения, а именно, матрица весов , поле для ввода начальных и конечных вершин пути и поле результатов - вершины пути и стоимость кратчайшего маршрута. Управление программой выполняется посредством кнопок управления, расположенное в главном окне.
Назначение кнопок.
Если путь найден, то он выводится в поле Ответ, а если такого пути нет, то выводятся нулевые результаты.
Приложение. Тестовый пример
Дана транспортная сеть (рис. 7), состоящая из пяти городов (расстояния между городами (в милях) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города 1 (узел 1) до города 5 (узел 5).
100 20 10 50
30
Рисунок 7 - Тестовый пример.
На рисунке 8 показан тестовый пример решения в программе.
Вводим количество переменных (вершин) - 5. В матрицу весов вводим значения расстояний между вершинами, их 7. Задаем начальную и конечную вершину. Нажимаем кнопку Решение. В поле результат выводятся вершины найденного кратчайшего пути и длина этого пути.
Рисунок 8 - Тестовый пример.
Заключение
Результатом работы над курсовой работой создана программа в среде Delphi, которая находит кратчайший путь в сети. Приложение является полупрофессиональным. Выполненные многочисленные тестовые примеры позволяют утверждать, что надежность программного обеспечения проекта довольно высока.
Список использованных источников
3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ, 2000. – 288с.
4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
5. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.
6. Hечепуpенко М.И. Алгоритмы и программы решения задач на гpафах и сетях.- Hовосибиpск: Hаука, 1990
7. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992
8. Таха Хемди А. Введение в исследование операций. - М.: Изд-во "Вильямс", 2005. - 903с.
9. http://works.tarefer.ru
10. http://www.bibliofond.ru
11. http://www.coolreferat.com