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

Автор работы: Пользователь скрыл имя, 28 Октября 2013 в 20:13, реферат

Краткое описание

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

Содержание

Введение
1. Математическое обеспечение
1.1 Постановка задачи о кратчайшем пути на сети
1.2 Описание метода Минти
2. Алгоритмическое обеспечение
3. Программное обеспечение
3.1 Обоснование выбора среды разработки
3.2 Описание интерфейса и параметров программного продукта
4. Тестирование программного продукта
4.1 Тестовая задача 1
4.2 Тестовая задача 2
4.3 Тестовая задача 3
Заключение
Список использованных источников

Вложенные файлы: 1 файл

Алгоритм Минти.docx

— 210.09 Кб (Скачать файл)

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

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

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

 

 

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


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