Метод Минти нахождения кратчайшего пути

 

СОДЕРЖАНИЕ


Введение

. Математическое обеспечение

.1 Постановка задачи о кратчайшем пути на сети

.2 Описание метода Минти

. Алгоритмическое обеспечение

. Программное обеспечение

.1 Обоснование выбора среды разработки

.2 Описание интерфейса и параметров программного продукта

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

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

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

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

Заключение

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

ПРИЛОЖЕНИЕ А Листинг основного модуля программы


Введение


Исследование операций - применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Исследование операций начинается тогда, когда для обоснования решений применяется тот или другой математический аппарат. Операция - всякое мероприятие (система действий), объединённое единым замыслом и направленное к достижению какой-то цели (напр., мероприятия задач 1-8, указанных ниже, будут операциями). Операция всегда является управляемым мероприятием, то есть зависит от человека, каким способом выбрать параметры, характеризующие её организацию (в широком смысле, включая набор технических средств, применяемых в операции). Решение (удачное, неудачное, разумное, неразумное) - всякий определённый набор зависящих от человека параметров. Оптимальное - решение, которое по тем или другим признакам предпочтительнее других.

Цель исследования операций - предварительное количественное обоснование оптимальных решений. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения - параметры, совокупность которых образует решение: числа, векторы, функции, физические признаки и т. д. Если элементами решения можно распоряжаться в определённых пределах, то заданные («дисциплинирующие») условия (ограничения) фиксированы сразу и нарушены быть не могут (грузоподъёмность, размеры, вес). К таким условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение. Их совокупность формирует множество возможных решений.

Характерная особенность исследования операций - системный подход <#"justify">1Изучить математическое описание данного метода оптимизации;

2Сформулировать алгоритм реализации данного метода;

Разработать пользовательский интерфейс программного продукта, реализующего метод Минти;

Разработать рабочую версию программы для реализации метода Минти;

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

1. Математическое обеспечение


.1 Постановка задачи о кратчайшем пути на сети


На сети, что задается графом (I,U), где I множество вершин, U множество дуг, с определенной на ней функцией стоимости сіj ((і,j) дуга с U), для фиксированных i1 и is найти путь

= ((i1,i2),(i2,i3)...,(is-1,is))


из вершины i1 в вершину is, длина которого



наименьшая.


1.2 Описание метода Минти


Метод Минти решения задачи о кратчайшем пути в сети представляет собой итеративный процесс, в ходе которого строится путь L=(s=i0, i1, ..., ip-1, ip=t).

На предварительном (нулевом) этапе алгоритма:

·формируется массив значений так называемых модифицированных длин i,j, которые перед началом первой итерации полагаются равными сi,j ?0;

·осуществляется отметка вершины i0 = s числом mi0 = 0.

Стандартная итерация включает этапы:

. Отметка вершин сети. Обозначим множество вершин cети, отмеченных на предыдущих итерациях, как (на первой итерации ={i0}). Для каждой вершины i? ищутся дуги, соединяющие ее с еще не помеченными вершинами-потомками j, модифицированная длина которых i,j = 0. Найденные таким способом вершины j помечаются числом mj = i, указывающим на «родителя». В том случае, когда сразу несколько дуг, имеющих i,j = 0, заканчиваются в одной и той же вершине j, значение для ее пометки выбирается произвольно.

Если среди вновь помеченных вершин окажется вершина t, то, значит, найден искомый путь (i0, i1,..., i(p-1), ip), гдена чем алгоритм завершается.

В случае, если вершины t нет среди отмеченных, и одновременно нельзя отметить ни одной новой вершины, то переходим к этапу 2.

. Преобразование значений модифицированных длин дуг. Для каждой вершины i? ищутся дуги, соединяющие ее с еще не помеченными вершинами j, и находятсяДалее модифицированные длины всех дуг, которые соединяют отмеченные вершины с неотмеченными (i?, j?), уменьшаются на величинув результате чего кратчайшие неиспользованные дуги получают нулевую модифицированную длину.

Затем происходит переход к следующей итерации.

Путь, построенный по методу Минти, будет кратчайшим. Это можно доказать с помощью индукции по номеру итерации, на которой была помечена вершина t, или, что то же самое, по количеству дуг, составляющих кратчайший путь. Если это произошло на первом шаге (что возможно только в случае, если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение очевидно. Предположим, что оно верно для всех пунктов, помеченных за первые r итераций, т. е. тех, которые достигаются переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный путь также будет кратчайшим, так как данная вершина помечается в результате минимально возможного продолжения одного из путей, полученного за предыдущие r итераций и являющегося по предположению кратчайшим.

Описанный алгоритм пригоден для построения кратчайших путей на неориентированных графах.

2. Алгоритмическое обеспечение


Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рисунке 1.


Рисунок 1 - Неориентированная сеть с заданными длинами дуг для нахождения кратчайшего пути


На предварительном этапе вершина 1 отмечается числом m1 = 0, а модифицированные длины совпадают с заданными длинами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ? = min{1,2, 1,3}=2 и вычитаем ее из 1,2, 1,3. После преобразования имеем 1,2 = 0, 1,3 = 1. Результаты можно увидеть на рисунке 2.

Рисунок 2 - Измененная сеть после выполнения первой итерации


Итерация 2. Помечаем вершину 2 m2 = 1 (см. рисунок 3). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего определяем ? = min{1,3, 2,3, 2,4, 2,5}=1 и после соответствующего преобразования имеем


Рисунок 3 - Измененная сеть после выполнения второй итерации


Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m3 = 1 (рисунок 4). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ? = min{2,4, 2,5, 3,4, 3,5}=1 и после преобразования имеем 2,5 = 8, 2,4 = 0, 3,5 = 3, 3,4 = 5.


Рисунок 4 - Измененная сеть после выполнения третей итерации


Итерация 4. Помечаем вершину 4 m4 =2 (рисунок 5). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Из чего определяем ? = min{2,5, 3,5, 4,5, 4,6}=3 и после преобразования имеем 2,5 = 5, 3,5 = 0, 4,5 = 0, 4,6 =5.


Рисунок 5 - Измененная сеть после выполнения четвертой итерации

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же соображениями, что и на итерации 3, пометим вершину 5 числом m5 =3 (рисунок 6). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Из чего определяем ? = min{4,6, 5,6}=2 и после преобразования имеем 4,6 = 3, 5,6 = 0.


Рисунок 6 - Измененная сеть после выполнения пятой итерации


Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m6=5 (рисунок 7). Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).

Рисунок 7 - Измененная сеть после выполнения шестой итерации


Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет несколько решений.


3. Программное обеспечение


.1 Обоснование выбора среды разработки


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

Для реализации метода Минти была выбрана система программирования Delphi версии 7 фирмы Borland, так как она предоставляет наиболее широкие возможности для программирования приложений ОС Windows.- это продукт Borland International для быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В основе Delphi лежит язык Object Pascal, который является расширением объектно-ориентированного языка Pascal. В Delphi также входят локальный SQL-сервер, генераторы отчетов, библиотеки визуальных компонентов, и прочее хозяйство, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто программ для Windows-среды.

Прежде всего Delphi предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать приложения в архитектуре клиент-сервер. Delphi производит небольшие по размерам (до 15-30 Кбайт) высокоэффективные исполняемые модули (.exe и .dll), поэтому в Delphi должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются - это имеет немаловажное значение и для конечных пользователей.

Преимущества Delphi по сравнению с аналогичными программными продуктами.

быстрота разработки приложения;

высокая производительность разработанного приложения;

низкие требования разработанного приложения к ресурсам компьютера;

наращиваемость за счет встраивания новых компонент и инструментов в среду Delphi;

возможность разработки новых компонент и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходных кодах);

удачная проработка иерархии объектов.

Система программирования Delphi рассчитана на программирование различных приложений и предоставляет большое количество компонентов для этого.

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


3.2 Описание интерфейса и параметров программного продукта


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

Рисунок 8 - Интерфейс программы расчета минимального пути


Пользователь должен ввести в соответствующие области:

·количество вершин в исходной исследуемой сети;

·вершину-источник, от которой начнется поиск кратчайшего пути;

·вершину-назначение, до достижения которой будет продолжаться поиск;

·начало, конец и вес ребер исходной исследуемой сети.

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

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

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


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

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

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


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


Задача:

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

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


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


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

12345678910111-649226-8534-7649-4952-3868743-46675698-659846-4965-31069-811438-

Решение: Исходные данные поставленной задачи были введены в программный модуль. Результаты вычислений представлены на рисунке 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


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

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

Заключение


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

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

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

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


.Конюховский П.В. Математические методы исследования операций в экономике. - СПб: Питер, 2000. - 208с.

2.<#"justify">Приложение А


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

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; // считаем стоимость маршрута

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.


СОДЕРЖАНИЕ Введение . Математическое обеспечение .1 Постановка задачи о кратчайшем пути на сети .2 Описание метода Минти . Алгоритмическое об

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ