Метод Минти нахождения кратчайшего пути
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
сании метода Минти (раздел 1.2. курсовой работы).
Результаты выполнения данного примера представлены на рисунке 13.
Рисунок 13 - Результаты выполнения тестовой задачи 3
Результаты, полученные в ходе выполнения программы, совпадают с ранее полученными.
В ходе тестирования программы на контрольных задачах программа ни разу не давала сбои и работала корректно.
Заключение
В данной работе был исследован один из современных методов оптимизации, а именно нахождение кратчайшего пути в неориентированной транспортной сети по методу Минти (метод меток).
Для достижения поставленной цели изучения метода было изучено математическое описание данного метода оптимизации, сформулирован алгоритм решения задач нахождения минимального пути.
В ходе выполнения работы был разработан программный модуль, реализующий поиск минимального пути по методу Минти. Так же были разработаны контрольные задачи для тестирования и исследования возможности и работоспособности программы.
Список использованных источников
.Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2000. - 208с.
2.">
.">
.">
.">
Приложение А
Листинг основного модуля программы
unit Unit1;, SysUtils, Classes, Graphics, Controls, Forms, StdCtrls, Grids, Types,, XPMan;= class(TForm): TButton;: TButton;: TButton;: TStringGrid;: TLabel;: TMemo;: TLabeledEdit;: TLabeledEdit;: TLabeledEdit;: TButton;Button1Click(Sender: TObject);cmdAddClick(Sender: TObject);cmdCompClick(Sender: TObject);cmdDelClick(Sender: TObject);FormCreate(Sender: TObject);txtDestChange(Sender: TObject);txtHandlerKeyPress(Sender: TObject; var Key: Char);txtSrcChange(Sender: TObject);txtVertexChange(Sender: TObject);;= class(TStringGrid);: TForm1;TElement = record
_start, _end, _weight, _initial:Integer;
_checked:boolean;;= record
_vertex:integer;
_data:integer;;= array of TVertex;Math;
{$R *.dfm}VertexCount:Integer = 6;:Integer = 1;:Integer = 6;EdgesCount = 10;: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));InArr(const Arr:TVertexArray; const Num:Integer):Boolean;I:Integer;:=False;I:=0 to High(Arr) doArr[I]._vertex = Num then:=True;;;;TForm1.Button1Click(Sender: TObject);.Clear;.Clear;.Clear;.Clear;;TForm1.cmdAddClick(Sender: TObject);I:Integer;.RowCount:=Grid.RowCount + 1;I:=0 to 2 do Grid.Cells[I, Grid.RowCount - 1]:=0;;TForm1.FormCreate(Sender: TObject);I, J:Integer;.OnKeyPress:=txtHandlerKeyPress;.OnKeyPress:=txtHandlerKeyPress;.OnKeyPress:=txtHandlerKeyPress;.RowCount:=EdgesCount + 1;.Text:=IntToStr(VertexCount);.Text:=IntToStr(VertexSrc);.Text:=IntToStr(VertexDest);.Cells[0, 0]:=Начало;.Cells[1, 0]:=Конец;.Cells[2, 0]:=Вес;I:=1 to EdgesCount doJ:=1 to 3 do Grid.Cells[J-1, I]:=IntToStr(Edges[I, J]);;TForm1.cmdCompClick(Sender: TObject);I, _from, _to:Integer;, VertArr:TVertexArray;:Boolean;:array of TElement;Process;I, Min, MinPos:Integer;InArr(VertArr, VertexDest) then Exit;
Min:=MaxInt;
// ищем ребро с минимальным весом в оба направления
for I:=0 to High(Massiv) do(Massiv[I]._weight < Min) and not (Massiv[I]._checked) thenInArr(VertArr, Massiv[I]._start) and (Vertex[Massiv[I]._end - 1]._vertex = -1) then:=Massiv[I]._weight;:=I;:=False;if InArr(VertArr, Massiv[I]._end) and (Vertex[Massiv[I]._start - 1]._vertex = -1) then:=Massiv[I]._weight;:=I;:=True;;;
// -------------------------not Bool then
_from:=Massiv[MinPos]._start;
_to:=Massiv[MinPos]._end;
_to:=Massiv[MinPos]._start;
_from:=Massiv[MinPos]._end;;.Lines.Add(Нашли минимальный вес ребра - + IntToStr(Min) + из + IntToStr(_from) + в + IntToStr(_to));
// вычитаем из стоимости всех проверенных ребер стоимость наименьшего
for I:=0 to High(Massiv) do(not Massiv[I]._checked) and (InArr(VertArr, Massiv[I]._start) or InArr(VertArr, Massiv[I]._end)) then[I]._weight:=Massiv[I]._weight - Min;Massiv[I]._weight = 0 then[_to - 1]._vertex:=_from;[_to - 1]._data:=Massiv[MinPos]._initial;
end;;
// ------------------------------------
// заносим в список вершин очередную, к которой ведет ребро с минимальным весои
SetLength(VertArr, Length(VertArr) + 1);not Bool then VertArr[High(VertArr)]._vertex:=Massiv[MinPos]._endVertArr[High(VertArr)]._vertex:=Massiv[MinPos]._start;
// и отмечаем ребро с мин. стоимостью
Massiv[MinPos]._checked:=True;.ProcessMessages;
// звем рекурсию для добавленной в список вершины
Process;;Res:string;:Integer;VertexSrc = VertexDest then(Handle, Исходный и конечный пункты совпадают, , MB_ICONEXCLAMATION);;;(VertexCount < VertexSrc) or (VertexCount < VertexDest) then
begin(Handle, Неверное значение источника или назначения, , MB_ICONEXCLAMATION);
Exit;;.Clear;(Massiv, Grid.RowCount - 1);I:=0 to High(Massiv) do[I]._start:=StrToInt(Grid.Cells[0, I+1]);[I]._end:=StrToInt(Grid.Cells[1, I+1]);[I]._weight:=StrToInt(Grid.Cells[2, I+1]);[I]._initial:=Massiv[I]._weight;[I]._checked:=False;;(Vertex, VertexCount);I:=0 to High(Vertex) do Vertex[I]._vertex:=-1;[VertexSrc-1]._vertex:=0;(VertArr, 1);[0]._vertex:=VertexSrc; // задаем начальный узел
Memo1.Lines.Add(Процесс рекурсии:);;:=VertexDest - 1; // считаем стоимость маршрута
0do:=IntToStr(Vertex[I]._vertex)+-+Res;:=Sum+Vertex[I]._data;:=Vertex[I]._vertex-1;;//---------------.Lines.Add(#13#10+:+">Res:=IntToStr(VertexDest);:=0;Vertex[I]._vertex > 0 do:=IntToStr(Vertex[I]._vertex) + - + Res;:=Sum + Vertex[I]._data;:=Vertex[I]._vertex - 1;; // ---------------.Lines.Add(#13#10 + Решение: +
#13#10 + Маршрут с минимальной стоимостью ребер: + Res +
#13#10 + Полная стоимость маршрута: + IntToStr(Sum));
end;TForm1.cmdDelClick(Sender: TObject);I:Integer;(Grid).DeleteRow(Grid.Selection.Top);Grid.RowCount = 1 then.RowCount:=2;.FixedRows:=1;I:=0 to 2 do Grid.Cells[I, Grid.RowCount - 1]:=0;;;TForm1.txtVertexChange(Sender: TObject);(txtVertex.Text, VertexCount);;TForm1.txtSrcChange(Sender: TObject);(txtSrc.Text, VertexSrc);;TForm1.txtDestChange(Sender: TObject);(txtDest.Text, VertexDest);;TForm1.txtHandlerKeyPress(Sender: TObject; var Key: Char);not ((Key in [0..9]) or (Key = #8)) then:=#0;;;;
end.