Разработка программы 'Пассажирские перевозки по городу'

ВВЕДЕНИЕ

Данная программа позволяет находить маршруты между двумя точками города для перевозки пассажиров такси. Найденные маршруты выводятся для просмотра в текстовом поле с возможностью сохранения в отдельный файл. Для нахождения маршрутов используется граф.

Граф - это совокупность непустого множества вершин и множества пар вершин.

Объекты представляются как узлы графа, а связи - как рёбра. В данной программе используется взвешенный, ориентированный граф.

Программа написана на языке программирования Delphi.

1.      ПОСТАНОВКА ЗАДАЧИ

Требуется находить все возможные варианты перевозки пассажиров из одной точки в другую (возможно, через промежуточные точки) и рассчитывать стоимость перевозки.

Заданы пункт отправления, пункт назначения и количество человек. В случае если пропускная способность какого-либо маршрута не позволяет транспортировать такое количество пассажиров, он транспортируется по частям.

Результат следует вывести в текстовое поле, а при нажатии соответствующей кнопки сохранить в отдельный текстовый файл.

2.      МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РЕШАЕМОЙ ЗАДАЧИ

Для решения данной задачи применяется теория графов.

В строгом определении графом называется пара множеств (формула (2.1)).

 (2.1)

где

G - граф;

V - множество вершин графа (каждая вершина соответствует одному пункту);

E - множество рёбер графа (каждое ребро соответствует одному маршруту).

Множество вершин графа представлено в формуле (2.2):

V={V₁:Авангардная 1_:, V₂:Буммашевская 3, V₃:Ворошилова 14, V₄:Гагарина 1, V₅:М.Горького 2, V₆: Орженикидзе 17, V₇:Пушкинская 1, V₈:Удмуртская 255, V₉:Холмогорова 5,…, V_n} (2.2)

где

V- множество вершин графа;

V_i - вершина графа с индексом i.

Множество рёбер графа представлено в формуле (2.3):

E = {E₁₂, E_{1 3}, E₁₅,E_{2 1}, E_{2 3}, E_{2 4}, E_{3 1}, E_{3 6}, E_{3 7}, E_{4 1},..,E_{n k}} (2.3)

где

E - множество рёбер графа;

E_{i j} - ребро графа, соединяющее i-ую и j-ую вершины.

Пусть каждый пункт - это вершина графа, а каждый маршрут - его ребро. У каждого ребра есть вес, который задается количеством пассажиров, которых можно перевезти за раз, стоимостью маршрута и названием пункта, который соединяет дуга с исходной вершиной. Количество вершин графа - n, E_i - количество дуг i-ой вершины.

Для нахождения маршрута между вершинами i и j используется формула (2.4).

(2.4)

i,j изменяются от 1 до n (кол-ва пунктов)

i - индекс исходной вершины;

j - индекс конечной вершины;

k - индекс вершины графа, отличной от Vi и Vj и смежной с Vi;

n - индекс произвольной вершины графа;

Path[i, j] - путь от вершины Vi до вершины Vj;

E[i, j] - ребро графа, соединяющее вершины Vi и Vj.

E[i, k] - ребро графа, соединяющее вершины Vi и Vk;

Path[k, j] - путь от вершины Vk до вершины Vj;

E[n, k] - ребро графа, соединяющее произвольную вершину Vn и вершину Vk.

Таким образом, формула для нахождения пути является итерационной. Если нет прямого пути от вершины Vi до вершины Vj, то происходит переход на вершину Vk, смежную с вершиной Vi и ещё не содержащуюся в пути, и ищется путь от вершины Vk до вершины Vj. Если на каком-либо шаге поиска для вершины Vi нет смежных и непосещённых вершин Vk, то поиск возвращается на предыдущий шаг и выбирает новую вершину Vk.

Общий вид пути представлен в формуле (2.5).

 (2.5)

где

Path[i, j] - путь от вершины Vi да вершины Vj;

E[i, k₁] - ребро графа, соединяющее вершины Vi и Vk₁;

E[k₁, k₂] - ребро графа, соединяющее вершины Vk₁ и Vk₂;

E[k_n, j] - ребро графа, соединяющее вершины Vk_n и j.

Пример:

V₇ (Пушкинская 1) - пункт отправления, V₆ (Орженикидзе 17) - пункт назначения

Найденные маршруты: v₇ - v₈ - v_6, v₇ - v₆

По найденным маршрутам подсчитывается их стоимость.

G = <V,E>, где V = { v₁, v₂, v₃, v₄, v₅, v₆, v₇, v₈, v₉} и

E = {e_{1 2}, e_{1 3}, e_{5 3}, e_{7 5}, e_{7 4}, e_{1 9}, e_{1 6}, e_{9 8}, e_{6 8}, e_{6 2}, e_{2 5}}

Граф G является ориентированным, взвешенным графом (рис. 2.1)

Граф G

Рис. 2.1

3.      ИНФОРМАЦИОННЫЕ СТРУКТУРЫ ДАННЫХ

Используемые в программе данные делятся на: входные, внутренние и выходные. Схема данных представлена на рис. 3.1.

Схема данных

Рис. 3.1

3.1 Структура входных данных

Текстовый файл punkt.dat - список пунктов.

Пример:

Пушкинская 1.

Гагарина 1.

М. Горького 2.

Буммашевская 3.

Холмогорова 5.

Ворошилова 14.

Орженикидзе 17.

Авангардная 1.

Типизированный файл puti.dat - список маршрутов, по каждому из маршрутов указывается наименования пунктов, которые соединяет этот маршрут, стоимость перевозки и максимальный пассажиропоток маршрута.

Формат данных, вводимых пользователем, описан в приложении 1.

Пользовательские данные содержат наименование пункта отправления и пункта прибытия, а так же максимальное количество пассажиров. Эти данные вводятся пользователем вручную во время работы программы. Пример ввода данных представлен на рис. 3.2.

Ввод данных пользователем

Рис. 3.2

Подробнее ввод данных пользователем описан в разделе приложении 1.3 «Выполнение программы».

3.2 Представление данных в программе

Типы:

TPath - маршрут (record).

t1,t2 - название пунктов, которые соединяют маршрут.

p1, p2 - порядковые номера пунктов, которые соединяет этот маршрут (byte).

cost - стоимость маршрута (word).

traf - количество пассажиров (word).

Переменные:

f1 - входной текстовый файл со списком пунктов (textfile).

f2 - входной типизированный файл со списком маршрутов (file of tpath).

colp - количество маршрутов (byte).

colt - количество пунктов (byte).

colw - количество найденных маршрутов (word).

towns - массив пунктов (array of string). - массив доступных маршрутов (array of tpath).

rel - динамический двумерный массив сопоставлений пунктов соседним пунктам (array of array of byte).

3.3 Структура выходных данных

Выходные данные

Содержат последовательность строк, содержащих сам маршрут, включая промежуточные пункты, и общую стоимость перевозки. Пример выходных данных представлен на рис. 3.3.

Рис. 3.3

4.      СХЕМА ПРОГРАММЫ

.1 Иерархическая схема программы

Иерархическая схема программы представлена на рис. 4.1.

Иерархическая схема программы

Рис. 4.1

Спецификация:

1)      Search - Проверяются все соседние пункты (рекурсивно), игнорируются пункты, которые уже встречались,при нахождении конечного пункта вызывается процедура Found.

2)      Found - добавляется маршрут в таблицу,рассчитывается стоимость маршрута,увеличивается счетчик найденных маршрутов на единицу.

3)      RassUpdate - Комбобоксы заполняются доступными городами. Заносятся в массивы доступные маршруты.

4)      Button1Click - Открывается редактор пунктов,в котором можно добавить или удалить пункт.

5)      Button2Click - Открывается редактор маршрутов, в котором можно добавить или удалить маршрут.

6)      Button3Click - производится расчет и открывается новая форма с результатами.

7)      ComboBox1Change - проверяет выбранные пункт отправления и пункт прибытия, если они совпадают то делает кнопку «Рассчитать» не доступной, иначе делает активной

8)      FormClose - записывает пункты и маршруты в исходные файлы, при закрытие программы.

ЗАКЛЮЧЕНИЕ

В ходе курсовой работы был создан программный продукт, удовлетворяющий всем поставленным задачам. В результате использования языка Delphi, данный программный продукт легко расширяем и модифицируем.

В дальнейшем полученная программа может быть модифицирована с добавлением функции поиска самого быстрого или дешевого маршрута.

При выполнении работы частично была изучена теория графов, алгоритм поиска в глубину и язык программирования Delphi.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.   Силкин К.Ю. «Геоинформационная система Golden Software Surfer 8: Учебно-методическое пособие для вузов» - Воронеж, 2008. - 66 с.

2.      Капралов Е.Г., Кошкарев А.В., Тикунов В.С. и др. «Геоинформатика: Учеб. для студ. Вузов» / Под ред. Тикунова В.С. - М: Издательский центр «Академия», 2005. - 480 с.

3.   С.И. Бобровский. Delphi 7. Учебный курс. Издательcкий дом "Питер", 2004.

4.   #"656633.files/image009.gif">

Рис. 1

В главном меню программы пользователь должен выбрать пункт отправления и пункт прибытия из предложенного списка, а также ввести количество человек, перевозимых за раз (рис. 2).

Выбор городов

Рис. 2

После выбора количества человек и корректных пунктов отправления и прибытия пользователь должен нажать на кнопку «Рассчитать». Откроется новая форма с текстовым полем в которой будут записаны найденные маршруты (рис. 3). Есть возможность сохранить полученный результат в отдельный файл, нажав кнопку «Сохранить»

Маршруты, удовлетворяющие заданному времени

Рис. 3

Если не найден ни один маршрут, удовлетворяющий заданным значениям, то выводится сообщение «Маршрута между этими точками не существует» (рис. 4).

Маршруты, не удовлетворяющие заданным параметрам

Рис. 4

Пользователь может самостоятельно добавить новый пункт или задать новый маршрут. Для этого нужно нажать кнопку «Редактор пунктов» (рис. 5) или соответственно «Редактор маршрутов» (рис. 6)

Редактор городов

Рис. 5

Рис. 6

В каждом из редакторов можно добавить или удалить пункты или маршруты, нажав соответствующие клавиши.

Приложение 2

Схема программы

Граф-схема проц-ры FormCreate

Граф-схема проц-ры Found

Граф-схема процедуры RassUpdate

Граф-схема процедуры ComboBox1Change

Граф-схема проц-ры Search

Граф-схема проц-ры Button4Click Граф-схема проц-ры Button2Click

Граф-схема проц-ры Button3Click

Граф-схема проц-ры Button1Click

Граф-схема проц-ры TForm6.Button2Click

ПРИЛОЖЕНИЕ 3

Исходный код программы

Программа Project1:

program Taxi;

{Выполнил: студент гр. Б2-191-2 Нуруллин Р.М.

},in 'Unit1.pas' {Form1},in 'Unit2.pas' {Form2},in 'Unit3.pas' {Form3},in 'Unit4.pas' {Form4},in 'Unit5.pas' {Form5};

{$R *.res}.Initialize;.Title := 'Перевозки пассажиров по городу';

Application.CreateForm(TForm1, Form1);.CreateForm(TForm2, Form2);.CreateForm(TForm3, Form3);.CreateForm(TForm4, Form4);.CreateForm(TForm5, Form5);.Run;.

Модуль Unit1:Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Buttons, XPMan, ComCtrls, jpeg, ExtCtrls;=record,t2:string[30];,p2:byte;:word;:word;;= class(TForm): TButton;: TButton;: TImage;: TBevel;: TLabel;: TLabel;: TComboBox;: TComboBox;: TEdit;: TUpDown;: TButton;: TLabel;: TButton;FormCreate(Sender: TObject);FormClose(Sender: TObject; var Action: TCloseAction);ComboBox1Change(Sender: TObject);Button1Click(Sender: TObject);Button2Click(Sender: TObject);Button3Click(Sender: TObject);Button4Click(Sender: TObject);

{ Private declarations }:textfile;:file of tpath;,colt:byte;:word;:array [1..60] of string;:array [1..30] of tpath;:array of array of byte;RassUpdate;Search(fin:byte;way:string);Found(way:string);;: TForm1;Unit2, Unit3, Unit4, Unit5;

{$R *.dfm}TForm1.FormCreate(Sender: TObject);st:string;:tpath;not FileExists('punkt.dat') then begin(f1,'punkt.dat');(f1);(f1);(f1,'punkt.dat');(f1);:=0;not eof(f1) do begin(f1,st);(colt);[colt]:=st;(f1);not FileExists('puti.dat') then begin(f2,'puti.dat');(f2);(f2);(f2,'puti.dat');(f2);:=0;not eof(f2) do begin(f2,t);(colp);[colp]:=t;(f2);;TForm1.FormClose(Sender: TObject; var Action: TCloseAction);i:byte;(f1,'punkt.dat');(f1);i:=1 to colt do(f1,towns[i]);(f1);(f2,'puti.dat');(f2);i:=1 to colp do(f2,paths[i]);(f2);;TForm1.RassUpdate;i,k,cpn:byte;:array [1..30] of tpath;,f2:boolean;:=0;i:=1 to colp do begin:=false;:=false;k:=1 to colt do beginpaths[i].t1=towns[k] then f1:=true;paths[i].t2=towns[k] then f2:=true;f1 and f2 then begin(cpn);[cpn]:=paths[i];i:=1 to cpn do begin[i]:=t[i];:=1;(towns[k]<>paths[i].t1) do inc(k);[i].p1:=k;:=1;(towns[k]<>paths[i].t2) do inc(k);[i].p2:=k;:=cpn;.Clear;.Clear;i:=1 to colt do begin.Items.Add(towns[i]);.Items.Add(towns[i]);.ItemIndex:=0;.ItemIndex:=0;Change(Self);;TForm1.ComboBox1Change(Sender: TObject);ComboBox1.ItemIndex=ComboBox2.ItemIndex then Button3.Enabled:=false else Button3.Enabled:=true;TForm1.Search(fin:byte;way:string);i,k:shortint;:byte;:boolean;:=Ord(way[length(way)]);i:=0 to length(rel[t])-1 do begin:=true;k:=1 to length(way) doOrd(way[k])=rel[t,i] then f:=false;f thenrel[t,i]=fin then(way+Chr(rel[t,i]))(fin,way+Chr(rel[t,i]));TForm1.Found(way:string);i,k:byte;:integer;:string;(colw);:=towns[Ord(way[1])+1];i:=2 to length(way) do st:=st+' - '+towns[Ord(way[i])+1];:=0;i:=1 to length(way)-1 dok:=1 to colp do((paths[k].p1=Ord(way[i])+1) and (paths[k].p2=Ord(way[i+1])+1)) or ((paths[k].p2=Ord(way[i])+1) and (paths[k].p1=Ord(way[i+1])+1)) then:=sum+paths[k].cost*(((UpDown1.Position-1) div paths[k].traf)+1);.Memo1.Lines.Add(IntToStr(colw)+')'+st+': '+IntToStr(sum));;TForm1.Button1Click(Sender: TObject);.ShowModal;TForm1.Button2Click(Sender: TObject);.ShowModal;;TForm1.Button3Click(Sender: TObject);i,k:shortint;.Memo1.Clear;(rel,colt);i:=1 to colt do begin(rel[i-1],0);k:=1 to colp dopaths[k].p1=i then begin(rel[i-1],length(rel[i-1])+1);[i-1,length(rel[i-1])-1]:=paths[k].p2-1paths[k].p2=i then begin(rel[i-1],length(rel[i-1])+1);[i-1,length(rel[i-1])-1]:=paths[k].p1-1;:=0;(ComboBox2.ItemIndex,Chr(ComboBox1.ItemIndex));colw=0 then MessageBox(Handle,'Маршрута между этими точками не существует','Ошибка',MB_OK+MB_DEFBUTTON1+MB_ICONERROR+MB_APPLMODAL) else Form4.ShowModal;TForm1.Button4Click(Sender: TObject);;;.

Модуль Unit2:Unit2;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Buttons;= class(TForm): TLabel;: TListBox;: TButton;: TButton;: TButton;: TButton;AddButtonClick(Sender: TObject);DelButtonClick(Sender: TObject);SaveButtonClick(Sender: TObject);CancelButtonClick(Sender: TObject);FormShow(Sender: TObject);FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);

{ Private declarations }

{ Public declarations };: TForm2;:text;Unit1;

{$R *.dfm}TForm2.AddButtonClick(Sender: TObject);t:string;.Enabled:=true;:=InputBox('Добавление пункта','Название пункта','');

if t<>'' then.ListBox1.Items.Add(t);;TForm2.DelButtonClick(Sender: TObject);i:integer;.Enabled:=true;i:=ListBox1.Count-1 downto 0 doListBox1.Selected[i] then ListBox1.Items.Delete(i);;TForm2.SaveButtonClick(Sender: TObject);i:integer;:string;(f,'punkt.dat');(f);i:=0 to ListBox1.Count-1 do:=ListBox1.Items[i];(f,t);.towns[i+1]:=t;;(f);.colt:=ListBox1.Count;.RassUpdate;;;TForm2.CancelButtonClick(Sender: TObject);;;TForm2.FormShow(Sender: TObject);t:string;:integer;.Clear;

{AssignFile(f,'punkt.dat');not FileExists('goroda.dat') then Rewrite(f);(f);not eof(f) do(f,t);.Items.Add(t);;(f);;; }i:=1 to Form1.colt do.Items.Add(Form1.towns[i]);;TForm2.FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);key=vk_escape then Close;;.

Модуль Unit3:Unit3;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, Buttons, StdCtrls, ComCtrls;= class(TForm): TLabel;: TComboBox;: TLabel;: TComboBox;: TEdit;: TUpDown;: TLabel;: TLabel;: TEdit;: TUpDown;: TButton;: TButton;SpeedButton2Click(Sender: TObject);FormShow(Sender: TObject);ComboBox1Change(Sender: TObject);Button2Click(Sender: TObject);Button1Click(Sender: TObject);FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);

{ Private declarations }

{ Public declarations };: TForm3;Unit1, Unit5;

{$R *.dfm}TForm3.SpeedButton2Click(Sender: TObject);;TForm3.FormShow(Sender: TObject);i:byte;.Clear;.Clear;i:=1 to Form1.colt do begin.Items.Add(Form1.towns[i]);.Items.Add(Form1.towns[i]);.ItemIndex:=0;.ItemIndex:=0;.Text:='100';.Text:='100';.RassUpdate;;TForm3.ComboBox1Change(Sender: TObject);ComboBox1.ItemIndex=ComboBox2.ItemIndex then Button1.Enabled:=false else Button1.Enabled:=true;TForm3.Button2Click(Sender: TObject);;;TForm3.Button1Click(Sender: TObject);(Form1.colp);.paths[Form1.colp].p1:=ComboBox1.ItemIndex+1;.paths[Form1.colp].p2:=ComboBox2.ItemIndex+1;.paths[Form1.colp].t1:=Form1.towns[ComboBox1.ItemIndex+1];.paths[Form1.colp].t2:=Form1.towns[ComboBox2.ItemIndex+1];.paths[Form1.colp].cost:=UpDown1.Position;.paths[Form1.colp].traf:=UpDown2.Position;.ListBox2.Items.Add(Form1.towns[ComboBox1.ItemIndex+1]+' - '+Form1.towns[ComboBox2.ItemIndex+1]);;TForm3.FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);key=vk_escape then Close;;.

Модуль Unit4:Unit4;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Grids;= class(TForm): TLabel;: TMemo;: TButton;: TButton;: TSaveDialog;Button1Click(Sender: TObject);Button2Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm4;

{$R *.dfm}TForm4.Button1Click(Sender: TObject);.InitialDir:=GetCurrentDir;SaveDialog1.Execute then.Lines.SaveToFile(SaveDialog1.FileName);;TForm4.Button2Click(Sender: TObject);;;.

Модуль Unit5:Unit5;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TListBox;: TGroupBox;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TButton;: TButton;: TButton;ListBox2Click(Sender: TObject);NewButtonClick(Sender: TObject);FormShow(Sender: TObject);CancelButtonClick(Sender: TObject);DelButtonClick(Sender: TObject);FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);

{ Private declarations }

{ Public declarations };: TForm5;Unit3,Unit1;

{$R *.dfm}TForm5.ListBox2Click(Sender: TObject);ListBox2.ItemIndex>=0 then begin.Caption:=Form1.towns[Form1.paths[ListBox2.ItemIndex+1].p1];.Caption:=Form1.towns[Form1.paths[ListBox2.ItemIndex+1].p2];.Caption:=IntToStr(Form1.paths[ListBox2.ItemIndex+1].cost);.Caption:=IntToStr(Form1.paths[ListBox2.ItemIndex+1].traf);TForm5.NewButtonClick(Sender: TObject);.ComboBox1Change(Self);.ShowModal;TForm5.FormShow(Sender: TObject);i:integer;.Clear;i:=1 to Form1.colp do.Items.Add(Form1.towns[form1.paths[i].p1]+' - '+Form1.towns[Form1.paths[i].p2]);ListBox2.Items.Count>0 then begin.ItemIndex:=0;Click(Self);TForm5.CancelButtonClick(Sender: TObject);;;TForm5.DelButtonClick(Sender: TObject);i,k:byte;: array [1..30] of tpath;:=0;i:=1 to Form1.colp donot ListBox2.Selected[i-1] then:=k+1;[k]:=Form1.paths[i];;.colp:=k;i:=1 to Form1.colp do Form1.paths[i]:=t[i];.DeleteSelected;;TForm5.FormKeyDown(Sender: TObject; var Key: Word;: TShiftState);key=vk_escape then Close;;.