Автор работы: Пользователь скрыл имя, 18 Августа 2012 в 17:42, курсовая работа
В первом разделе «Разработка модели» описывается сущность задачи, применяемая математическая модель. Также описываются способы организации исходных данных. Рассматриваются инструменты реализации алгоритма.
Во втором разделе «Проектирование программы» рассматриваются разрабатываемые функции их структура и реализация.
В третьем разделе «Тестирование» описываются требования к техническим средствам для проведения испытаний, рассматриваются возможные ошибки, представляются результаты тестирования.
В четвертом разделе «Применение» описывается назначение программы, рассматривается практический пример использования программы.
В заключении будет проанализировано созданное программное приложение, определена степень соответствия поставленной задачи и выполненной работы.
Введение 4
1. Разработка модели
1.1 Сущность задачи 6
1.2 Организация данных 8
1.3 Инструменты разработки 10
2. Проектирование программы
2.1 Описание основных алгоритмов 11
2.2 Описание структуры 12
3. Тестирование
3.1 Технические требования 14
3.2 Полное тестирование 14
4. Применение
4.1 Назначение программы 20
Заключение 21
Литература 22
Dialogs, Unit2, Unit3, StdCtrls, XPMan, Buttons, Menus, jpeg, ExtCtrls;
type
TForm1 = class(TForm)
GroupBox1: TGroupBox;
Button1: TButton;
Button2: TButton;
XPManifest1: TXPManifest;
BitBtn1: TBitBtn;
MainMenu1: TMainMenu;
File1: TMenuItem;
Support1: TMenuItem;
Exit1: TMenuItem;
Showgraphic1: TMenuItem;
Exit2: TMenuItem;
Aboutmyself1: TMenuItem;
Image1: TImage;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure BitBtn1Click(Sender: TObject);
procedure Exit1Click(Sender: TObject);
procedure Showgraphic1Click(Sender: TObject);
procedure Exit2Click(Sender: TObject);
procedure Aboutmyself1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
uses Unit4;
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
Form2.Show;
Form2.Refresh;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Form3.Show;
end;
procedure TForm1.BitBtn1Click(Sender: TObject);
begin
Close;
end;
procedure TForm1.Exit1Click(Sender: TObject);
begin
Form2.Show;
Form2.Refresh;
end;
procedure TForm1.Showgraphic1Click(
begin
Form3.Show;
end;
procedure TForm1.Exit2Click(Sender: TObject);
begin
close;
end;
procedure TForm1.Aboutmyself1Click(
begin
Form4.ShowModal;
end;
end.
unit Unit2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, Menus, XPMan, Unit3;
const
MAXPATH = 1000; // максимальная длина пути между 2-мя вершинами
MAXTOWNCOUNT = 100; // максимальное количество вершин
type
TForm2 = class(TForm)
StringGrid1: TStringGrid;
Memo1: TMemo;
Button1: TButton;
ListBox1: TListBox;
Button3: TButton;
Button5: TButton;
Button6: TButton;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label6: TLabel;
XPManifest1: TXPManifest;
MainMenu1: TMainMenu;
N1: TMenuItem;
N2: TMenuItem;
// procedure Button1Click(Sender: TObject);
// procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
// procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure FormShow(Sender: TObject);
procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure N2Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure StringGrid1Click(Sender: TObject);
private
// матрица весов (расстояний между городами)
Weights: array [0..MAXTOWNCOUNT-1, 0..MAXTOWNCOUNT-1] of integer;
// кол-во городов
towncount: integer;
// массивы для расчета
// город (вершина графа) уже обсчитан
Ready: array [0..MAXTOWNCOUNT-1] of boolean;
// текущий кратчайший путь до этого города из первого
Paths: array [0..MAXTOWNCOUNT-1] of word;
// предпоследний узел пути из первого города до этого
Nodes: array [0..MAXTOWNCOUNT-1] of byte;
// индекс первого города
first: integer;
// очистка интерфейсной таблицы весов
procedure ClearGrid;
// перенести данные из TStringGrid в матрицу весов
procedure GetWeightsMatrix;
// инициализируем расчет
procedure FirstCountStep;
// запускаем расчет
procedure GoCount;
// результаты в мемо
procedure ShowResults;
// все ли вершины обсчитаны?
function AllAreReady: boolean;
// получить необсчитанную вершину с наименьшим путем
function GetMinPath: word;
public
{ Public declarations }
end;
var
Form2: TForm2;
implementation
{$R *.dfm}
(*----------------------------
Заполняем матрицу весов из интерфейсной
таблицы
------------------------------
procedure TForm2.GetWeightsMatrix;
var
i, j: integer;
begin
for i:=0 to towncount-1 do
Weights[i,i] := 0; // из города в сам себя
for i:=0 to towncount-1 do
for j:=i+1 to towncount-1 do
if StringGrid1.Cells[i+1,j+1]='' then
begin
Weights[i,j]:=MAXPATH+1; // считаем, что это бесконечность
Weights[j,i]:=MAXPATH+1; // симметрия
end
else
begin
try // получаем значение
Weights[i,j]:=StrToInt(
except
MessageDlg(‘Ошибка: значение в таблице не является целым числом !’, mtError, [mbOK], 0);
exit;
end;
// неотрицательное?
if Weights[i,j]<0 then
begin
MessageDlg(‘Ошибка: значение в таблице не является неотрицательным !’, mtError, [mbOK], 0);
exit;
end;
// симметричная матрица
Weights[j,i] := Weights[i,j];
end; // else
end;
(*----------------------------
Инициализация расчета
------------------------------
procedure TForm2.FirstCountStep;
var
i: integer;
begin
first := -1;
for i:=0 to towncount-1 do
if ListBox1.Selected[i] then
first := i;
if (first=-1) then
begin
MessageDlg(‘Ошибка: вы не выбрали начальный город в списке!’,
mtError, [mbOK], 0);
exit;
end;
Label1.Caption := ListBox1.Items[first];
for i:=0 to towncount-1 do
begin
Ready[i] := false; // еще ничего не посчитано
Nodes[i] := first; // все как-будто на прямую
Paths[i] := Weights[first,i]; // прямые пути
end;
end;
(*----------------------------
Итерационная часть расчета
(Собственно, сам алгоритм)
------------------------------
procedure TForm2.GoCount;
var
k, cur: integer;
begin
while not AllAreReady() do
begin
cur := GetMinPath;
Ready[cur] := true;
for k:=0 to towncount-1 do
if ((Ready[k]=false)and(Paths[k]>
begin
Paths[k] := Paths[cur]+Weights[cur,k];
Nodes[k] := cur;
end;
end;
end;
(*----------------------------
Показать результаты: последовательности
перемещения и величины кратчайших путей
------------------------------
procedure TForm2.ShowResults;
var
k, last: integer;
str: string;
//i, j: integer;
begin
Memo1.Lines.Clear;
Form3.Memo1.Clear;
for k:=0 to towncount-1 do
begin
str := ListBox1.Items[k]+' ('+IntToStr(Paths[k])+')';
last := Nodes[k];
while last<>first do
begin
str := ListBox1.Items[last]+' => '+str;
last := Nodes[last];
end;
str := ListBox1.Items[first]+' => '+str;
Memo1.Lines.Add(str);
Form3.Memo1.Lines.Add(str);
end;
end;
function TForm2.AllAreReady: boolean;
var
i: integer;
begin
Result := true;
for i:=0 to towncount-1 do
if Ready[i]=false then
Result := false;
end;
function TForm2.GetMinPath: word;
var
i, min, imin: integer;
begin
min := MAXPATH+1;
imin := 0;
for i:=0 to towncount-1 do
if ((Ready[i]=false)and(Paths[i]<
begin
min := Paths[i];
imin := i;
end;
Result := imin;
end;
procedure TForm2.ClearGrid;
var
i, j: integer;
begin
for i:=1 to StringGrid1.RowCount-1 do
for j:=1 to StringGrid1.ColCount-1 do
StringGrid1.Cells[i,j] := '';
end;
procedure TForm2.FormShow(Sender: TObject);
begin
Label2.Caption := IntToStr(MAXPATH);
end;
procedure TForm2.StringGrid1SetEditText(
ARow: Integer; const Value: String);
begin
// делаем матрицу симметричной принудительно
StringGrid1.Cells[ARow,ACol] := Value;
end;
procedure TForm2.Button6Click(Sender: TObject);
var
i: integer;
begin
StringGrid1.ColCount := ListBox1.Items.Count+1;
StringGrid1.RowCount := ListBox1.Items.Count+1;
for i:=0 to ListBox1.Items.Count-1 do
begin
StringGrid1.Cells[i+1,0] := ListBox1.Items[i];
StringGrid1.Cells[0,i+1] := ListBox1.Items[i];
end;
end;
procedure TForm2.Button5Click(Sender: TObject);
var
i, j: integer;
flag: real; // существует ли путь
begin
ClearGrid;
for i:=1 to StringGrid1.ColCount-1 do
begin
StringGrid1.Cells[i,i] := '0';
for j:=i+1 to StringGrid1.RowCount-1 do
begin
flag := random;
if (flag>0.5) then
begin
StringGrid1.Cells[i,j] := IntToStr(random(MAXPATH));
StringGrid1.Cells[j,i] := StringGrid1.Cells[i,j];
end;
end;
end;
end;
//procedure TForm2.Button4Click(Sender: TObject);
//begin
//ListBox1.Items.Clear;
//end;
procedure TForm2.Button3Click(Sender: TObject);
begin
towncount := ListBox1.Items.Count;
GetWeightsMatrix; // перебрасываем пути в матрицу
FirstCountStep; // инициализируем расчет
GoCount; // запускаем расчет
ShowResults; // результаты – в мемо
end;
procedure TForm2.N2Click(Sender: TObject);
begin
Form2.Close;
end;
procedure TForm2.FormCreate(Sender: TObject);
begin
Form2.Refresh;
end;
procedure TForm2.Button1Click(Sender: TObject);
var
i, j: integer;
//flag: real; // существует ли путь
begin
ClearGrid;
for i:=1 to StringGrid1.ColCount-1 do
begin
StringGrid1.Cells[i,i] := '0';
for j:=i+1 to StringGrid1.RowCount-1 do // ñäåëàòü îçåðêàëèâàíèå ìàòðèöû
begin
StringGrid1.Cells[1,6] := IntToStr(160);
StringGrid1.Cells[1,7] := IntToStr(75);
StringGrid1.Cells[1,5] := IntToStr(120);
StringGrid1.Cells[1,9] := IntToStr(270);
StringGrid1.Cells[1,11] := IntToStr(200);
StringGrid1.Cells[1,13] := IntToStr(150);
StringGrid1.Cells[1,15] := IntToStr(105);
StringGrid1.Cells[1,16] := IntToStr(145);
StringGrid1.Cells[2,3] := IntToStr(175);
StringGrid1.Cells[2,6] := IntToStr(65);
StringGrid1.Cells[2,8] := IntToStr(165);
StringGrid1.Cells[3,4] := IntToStr(120);
StringGrid1.Cells[3,7] := IntToStr(90);
StringGrid1.Cells[4,5] := IntToStr(50);
StringGrid1.Cells[5,20] := IntToStr(60);
StringGrid1.Cells[6,8] := IntToStr(110);
StringGrid1.Cells[8,9] := IntToStr(80);
StringGrid1.Cells[9,10] := IntToStr(80);
StringGrid1.Cells[10,13] := IntToStr(120);
StringGrid1.Cells[10,11] := IntToStr(170);
StringGrid1.Cells[11,13] := IntToStr(150);
StringGrid1.Cells[11,12] := IntToStr(115);
StringGrid1.Cells[12,13] := IntToStr(115);
StringGrid1.Cells[12,14] := IntToStr(155);
StringGrid1.Cells[13,15] := IntToStr(115);
StringGrid1.Cells[14,15] := IntToStr(105);
StringGrid1.Cells[14,17] := IntToStr(250);
StringGrid1.Cells[15,16] := IntToStr(115);
StringGrid1.Cells[16,17] := IntToStr(155);
StringGrid1.Cells[16,19] := IntToStr(55);
StringGrid1.Cells[17,18] := IntToStr(50);
StringGrid1.Cells[18,19] := IntToStr(200);
StringGrid1.Cells[19,20] := IntToStr(105);
StringGrid1.Cells[19,21] := IntToStr(145);
StringGrid1.Cells[20,21] := IntToStr(110);
end;
end;
end;
procedure TForm2.StringGrid1Click(
begin
end;
end.
unit Unit3;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls, jpeg, XPMan, Menus;
type
TForm3 = class(TForm)
Memo1: TMemo;
XPManifest1: TXPManifest;
Image1: TImage;
Image2: TImage;
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form3: TForm3;
implementation
{$R *.dfm}
end.
unit Unit4;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls, Menus, jpeg;
type
TForm4 = class(TForm)
MainMenu1: TMainMenu;
File1: TMenuItem;
Exit1: TMenuItem;
Image1: TImage;
Image2: TImage;
procedure Exit1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form4: TForm4;
implementation
uses Unit1;
{$R *.dfm}
procedure TForm4.Exit1Click(Sender: TObject);
begin
close();
end;
end.
Информация о работе Графы. Поиск оптимального маршрута по городам Беларуси