Алгоритм для нахождение кратчайшего расстояния

Для добавления и удаления ребер на форме предусмотрены  кнопки «Добавить ребро» и «Удалить ребро». Кнопка «Удалить ребро» удаляет  выделенное в списке ребро сети. Кнопка «Добавить ребро» создает  новую строку, куда следует ввести данные о новом ребре.

Кнопка «Очистка» удаляет  ранее введенные данные из областей «Количество вершин», «Вершина-источник»  и «Вершина-назначение», а так  же из обрасти «Решение», где программа  отображает ход поиска минимального маршрута по методу Минти (выводится  вес найденных ребер, найденный  минимальный путь и стоимость  минимального маршрута).

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

 

 

4. Тестирование программного продукта

программирование delphi минти решение

Тестирование разработанной  программы производилось на 3 тестовых задачах.

 

4.1 Тестовая задача 1

 

Задача:

В предложенной транспортной сети (рисунок 9) имеется несколько  маршрутов по проезду из начального пункта (1) в конечный пункт (11). Стоимость  проездного билета между отдельными пунктами транспортной сети представлены в таблице 1.

Необходимо определить оптимальный маршрут проезда  из пункта 1 в пункт 11 с минимальными транспортными расходами на билеты.

 

Рисунок 9 - Транспортная сеть

 

Таблица 1- Стоимость проезда  между отдельными пунктами

	1	2	3	4	5	6	7	8	9	10	11
1	-	6	4	9	2
2	6	-				8	5
3	4		-			7	6
4	9			-		4	9
5	2				-	3	8
6		8	7	4	3	-		4	6	6
7		5	6	9	8		-	6	5	9
8						4	6	-			4
9						6	5		-		3
10						6	9			-	8
11								4	3	8	-

 

Решение: Исходные данные поставленной задачи были введены в программный  модуль. Результаты вычислений представлены на рисунке 10.

 

Рисунок 10 – Результаты выполнения тестовой задачи 1

 

Найденный минимальный  путь 1 – 5 – 6 – 8 – 11 со стоимостью всего  маршрута 13 является правильным.

 

4.2 Тестовая задача 2

 

Задача: курьеру требуется доехать из офиса 1 до пункта назначения 5 с наименьшим количеством остановок на светофорах, представленных на рисунке 11. Вес ребра – количество светофоров на каждой ветке пути.

 

Рисунок 11 – Транспортная сеть (карта маршрута)

 

Решение: Параметры были введены в программу. Результаты вычислений представлены на рисунке 12.

 

Рисунок 12 – Результаты выполнения тестовой задачи 2

 

Все расчеты выполнены  верно.

 

 

4.3 Тестовая задача 3

 

В качестве третей тестовой задачи был использован пример, приведенный  в описании метода Минти (раздел 1.2. курсовой работы).

Результаты выполнения данного примера представлены на рисунке 13.

 

Рисунок 13 – Результаты выполнения тестовой задачи 3

 

Результаты, полученные в  ходе выполнения программы, совпадают  с ранее полученными.

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

 

Заключение

 

В данной работе был исследован один из современных методов оптимизации, а именно нахождение кратчайшего  пути в неориентированной транспортной сети по методу Минти (метод меток).

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

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

 

Список использованных источников

 

1. Конюховский П.В. Математические методы исследования операций в экономике. – СПб: Питер, 2000. – 208с.
2. http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
3. http://coolreferat.com/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B8%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9_%D0%B2_%D1%8D%D0%BA%D0%BE%D0%BD%D0%BE%D0%BC%D0%B8%D0%BA%D0%B5_%D1%87%D0%B0%D1%81%D1%82%D1%8C=17
4. http://www.studfiles.ru/dir/cat14/subj93/file10844/view103599/page7.html
5. http://www.ecosyn.ru/page0140.html

 

Приложение А

 

Листинг основного модуля программы

unit Unit1;

interface

uses

Windows, SysUtils, Classes, Graphics, Controls, Forms, StdCtrls, Grids, Types,

ExtCtrls, XPMan;

type

TForm1 = class(TForm)

cmdAdd: TButton;

cmdComp: TButton;

cmdDel: TButton;

Grid: TStringGrid;

Label1: TLabel;

Memo1: TMemo;

txtDest: TLabeledEdit;

txtSrc: TLabeledEdit;

txtVertex: TLabeledEdit;

Button1: TButton;

procedure Button1Click(Sender: TObject);

procedure cmdAddClick(Sender: TObject);

procedure cmdCompClick(Sender: TObject);

procedure cmdDelClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure txtDestChange(Sender: TObject);

procedure txtHandlerKeyPress(Sender: TObject; var Key: Char);

procedure txtSrcChange(Sender: TObject);

procedure txtVertexChange(Sender: TObject);

end;

THackGrid = class(TStringGrid);

var

Form1: TForm1;

type TElement = record

_start, _end, _weight, _initial:Integer;

_checked:boolean;

end;

TVertex = record

_vertex:integer;

_data:integer;

end;

TVertexArray = array of TVertex;

implementation

uses Math;

{$R *.dfm}

var VertexCount:Integer = 6;

VertexSrc:Integer = 1;

VertexDest:Integer = 6;

const EdgesCount = 10;

Edges:array[1..EdgesCount, 1..3] of Integer =

((1, 2, 2), (1, 3, 3), (2, 3, 1),

(2, 4, 2), (2, 5, 10), (3, 4, 6),

(3, 5, 4), (4, 5, 3), (4, 6, 8),

(5, 6, 2));

function InArr(const Arr:TVertexArray; const Num:Integer):Boolean;

var I:Integer;

begin

Result:=False;

for I:=0 to High(Arr) do

if Arr[I]._vertex = Num then

begin

Result:=True;

Exit;

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

txtVertex.Clear;

txtSrc.Clear;

txtDest.Clear;

Memo1.Clear;

end;

procedure TForm1.cmdAddClick(Sender: TObject);

var I:Integer;

begin

Grid.RowCount:=Grid.RowCount + 1;

for I:=0 to 2 do Grid.Cells[I, Grid.RowCount - 1]:='0';

end;

procedure TForm1.FormCreate(Sender: TObject);

var I, J:Integer;

begin

txtVertex.OnKeyPress:=txtHandlerKeyPress;

txtSrc.OnKeyPress:=txtHandlerKeyPress;

txtDest.OnKeyPress:=txtHandlerKeyPress;

Grid.RowCount:=EdgesCount + 1;

txtVertex.Text:=IntToStr(VertexCount);

txtSrc.Text:=IntToStr(VertexSrc);

txtDest.Text:=IntToStr(VertexDest);

Grid.Cells[0, 0]:='Начало';

Grid.Cells[1, 0]:='Конец';

Grid.Cells[2, 0]:='Вес';

for I:=1 to EdgesCount do

for J:=1 to 3 do Grid.Cells[J-1, I]:=IntToStr(Edges[I, J]);

end;

procedure TForm1.cmdCompClick(Sender: TObject);

var I, _from, _to:Integer;

Vertex, VertArr:TVertexArray;

Bool:Boolean;

Massiv:array of TElement;

procedure Process;

var I, Min, MinPos:Integer;

begin

if InArr(VertArr, VertexDest) then Exit;

Min:=MaxInt;

// ищем ребро с минимальным  весом в оба направления

for I:=0 to High(Massiv) do

if (Massiv[I]._weight < Min) and not (Massiv[I]._checked) then

begin

if InArr(VertArr, Massiv[I]._start) and (Vertex[Massiv[I]._end - 1]._vertex = -1) then

begin

Min:=Massiv[I]._weight;

MinPos:=I;

Bool:=False;

end

else if InArr(VertArr, Massiv[I]._end) and (Vertex[Massiv[I]._start - 1]._vertex = -1) then

begin

Min:=Massiv[I]._weight;

MinPos:=I;

Bool:=True;

end;

end;

// -------------------------

if not Bool then

begin

_from:=Massiv[MinPos]._start;

_to:=Massiv[MinPos]._end;

end

else

begin

_to:=Massiv[MinPos]._start;

_from:=Massiv[MinPos]._end;

end;

Memo1.Lines.Add('Нашли минимальный вес ребра - ' + IntToStr(Min) + ' из ' + IntToStr(_from) + ' в ' + IntToStr(_to));

// вычитаем из стоимости  всех проверенных ребер стоимость  наименьшего

for I:=0 to High(Massiv) do

if (not Massiv[I]._checked) and (InArr(VertArr, Massiv[I]._start) or InArr(VertArr, Massiv[I]._end)) then

begin

Massiv[I]._weight:=Massiv[I]._weight - Min;

if Massiv[I]._weight = 0 then

begin

Vertex[_to - 1]._vertex:=_from;

Vertex[_to - 1]._data:=Massiv[MinPos]._initial;

end;

end;

// ------------------------------------

// заносим в список  вершин очередную, к которой  ведет ребро с минимальным  весои

SetLength(VertArr, Length(VertArr) + 1);

if not Bool then VertArr[High(VertArr)]._vertex:=Massiv[MinPos]._end

else VertArr[High(VertArr)]._vertex:=Massiv[MinPos]._start;

// и отмечаем ребро  с мин. стоимостью

Massiv[MinPos]._checked:=True;

Application.ProcessMessages;

// звем рекурсию для  добавленной в список вершины

Process;

end;

var Res:string;

Sum:Integer;

begin

if VertexSrc = VertexDest then

begin

MessageBox(Handle, 'Исходный и конечный пункты совпадают', '', MB_ICONEXCLAMATION);

Exit;

end;

if (VertexCount < VertexSrc) or (VertexCount < VertexDest) then

begin

MessageBox(Handle, 'Неверное значение  источника или назначения', '', MB_ICONEXCLAMATION);

Exit;

end;

Memo1.Clear;

SetLength(Massiv, Grid.RowCount - 1);

for I:=0 to High(Massiv) do

begin

Massiv[I]._start:=StrToInt(Grid.Cells[0, I+1]);

Massiv[I]._end:=StrToInt(Grid.Cells[1, I+1]);

Massiv[I]._weight:=StrToInt(Grid.Cells[2, I+1]);

Massiv[I]._initial:=Massiv[I]._weight;

Massiv[I]._checked:=False;

end;

SetLength(Vertex, VertexCount);

for I:=0 to High(Vertex) do Vertex[I]._vertex:=-1;

Vertex[VertexSrc-1]._vertex:=0;

SetLength(VertArr, 1);

VertArr[0]._vertex:=VertexSrc; // задаем начальный узел

Memo1.Lines.Add('Процесс рекурсии:');

Process;

I:=VertexDest - 1; // считаем стоимость маршрута

Res:=IntToStr(VertexDest);

Sum:=0;

while Vertex[I]._vertex > 0 do

begin

Res:=IntToStr(Vertex[I]._vertex) + ' - ' + Res;

Sum:=Sum + Vertex[I]._data;

I:=Vertex[I]._vertex - 1;

end; // ---------------

Memo1.Lines.Add(#13#10 + 'Решение:' +

#13#10 + 'Маршрут с минимальной  стоимостью ребер: ' + Res +

#13#10 + 'Полная стоимость  маршрута: ' + IntToStr(Sum));

end;

procedure TForm1.cmdDelClick(Sender: TObject);

var I:Integer;

begin

THackGrid(Grid).DeleteRow(Grid.Selection.Top);

if Grid.RowCount = 1 then

begin

Grid.RowCount:=2;

Grid.FixedRows:=1;

for I:=0 to 2 do Grid.Cells[I, Grid.RowCount - 1]:='0';

end;

end;

procedure TForm1.txtVertexChange(Sender: TObject);

begin

TryStrToInt(txtVertex.Text, VertexCount);

end;

procedure TForm1.txtSrcChange(Sender: TObject);

begin

TryStrToInt(txtSrc.Text, VertexSrc);

end;

procedure TForm1.txtDestChange(Sender: TObject);

begin

TryStrToInt(txtDest.Text, VertexDest);

end;

procedure TForm1.txtHandlerKeyPress(Sender: TObject; var Key: Char);

begin

if not ((Key in ['0'..'9']) or (Key = #8)) then

begin

Key:=#0;

Beep;

end;

end;

end.

Размещено на Allbest.ru