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

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

 

Введение

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

 

 

Введение

 

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

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

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

Объект исследования: исследование операций в экономике.

Предмет исследования: метод  Минти для нахождения кратчайшего  пути.

Цели исследования: изучить  метод нахождения кратчайшего пути (метод Минти).

Для достижения поставленной цели необходимо выполнить следующие  задачи:

1. Изучить математическое описание данного метода оптимизации;
2. Сформулировать алгоритм реализации данного метода;
3. Разработать пользовательский интерфейс программного продукта, реализующего метод Минти;
4. Разработать рабочую версию программы для реализации метода Минти;
5. Разработать демонстрационные примеры для тестирования программы.

 

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

 

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

 

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

 

L = ((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.

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

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

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

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

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. Программное обеспечение

 

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

 

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

Для реализации метода Минти была выбрана система программирования Delphi версии 7 фирмы Borland, так как она предоставляет наиболее широкие возможности для программирования приложений ОС Windows.

Delphi – это продукт  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 – Интерфейс  программы расчета минимального пути

 

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

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