Кратчайший путь через сеть

Кратчайший путь через сеть

1. Предметная область моделирования

1.1 Понятие модели и их разновидности

Модель (фр. module, от лат. modulus - «мера, аналог, образец») - некоторый материальный или мысленно представляемый объект или явление, являющийся упрощённой версией моделируемого объекта или явления (прототипа) и в достаточной степени повторяющий свойства, существенные для целей конкретного моделирования (опуская несущественные свойства, в которых он может отличаться от прототипа).

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

Моделью может быть серийный повторяемый проект, имеющий набор определённых, свойственных только данной модели параметров и характеристик. Это делается даже в одном ряду изделий (проектов). Модель решений может иметь несколько версий или вариантов, что является моделированием деятельности, проектирования, управления большими проектами и т.п.

Процесс создания модели называется моделированием. Любая мыслительная деятельность представляет собой оперирование моделями (образами). Модели бывают натурные, макеты, информационные, логические, образные, и т.п.

Смоделировать можно любой процесс производственный, экономический (от процесса сборки до процесса прогнозирования цены акций на финансовом рынке).

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

Под моделированием понимается процесс построения, изучения и применения моделей. Понятие моделирование тесно связано с такими категориями как абстракция, гипотеза и аналогия. Формируются некоторые гипотезы развития объекта исследования, изучаются выделенные зависимости и соотношения.

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

• Постановка задачи, ее теоретическая и логическая формулировка.
• Анализ структуры исследуемой экономической системы.
• Построение модели отвечающей экономическим условиям задачи и математическим принципам.
• Заполнение системы уравнений необходимыми статистическими данными.
• Разработка математического алгоритма, решение задачи и получение численных результатов.
• Экономическая интерпретация, и анализ полученных результатов.

Среди множества моделей, которые используются для формализации экономических процессов можно выделить несколько:

- Наглядное моделирование - осуществляется на макетах или объемных моделях они передают внешний вид объекта помогают правильно установить технологические связи и дают наглядное представление об объекте до его реализации.

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

Информационное моделирование - основано на использовании различных графических и математических методов для выражения определенной информации и процессов ее преобразования. Графические модели реализуются средствами логического аппарата (схемы, чертежи таблицы, графики т. п.). Экономико-математические модели реализуются средствами математического аппарата и используют различные формулы, уравнения, неравенства, которые решаются математическими методами и выражаются в виде неравенства, уравнений, систем уравнений.

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

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

1.2 Построение модели

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

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

Задача принятия решения на базе экономико-математической модели сводится к нахождению экстремальных значений (max, min) целевой функции, а главное нахождение конкретного значения, при котором достигается min значение. Такое значение называется оптимальным.

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

Процесс оптимизации в таких моделях сводится к нахождению таких положительных значений неизвестных х1*…*хn, которые удовлетворяются условию ограничений и доставляют экстремум с целевой функции.

Задача, в которой целевая функция и условия ограничений заданы линейными функциями, называется задачей линейного программирования (ЗЛП).

Общая задача линейного программирования имеет несколько форм записи:

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А1х1 + А2x2 +… + АNxN = Ао, X 0, где С = (с1, с2,…, сN); Х = (х1, х2,…, хN); СХ - скалярное произведение; векторы A1, A2,…, AN, A0 состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А0, Х 0, где С = (с1, с2,…, сN) - матрица-cтрока; А = (аij) - матрица системы; Х - матрица-столбец, А0 - матрица-столбец.

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = Сjхj при ограничениях:

Определение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х1, х2,…, хN).

Определение 2. План Х = (х1, х2,…, хN) называется опорным, если векторы А (i = 1, 2,…, N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

Определение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

Определение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

Для решений уравнений линейного программирования применяют симплексный метод. Решение оформляется в виде таблицы. Переход к другой таблице называется итерацией.

Существует несколько модификаций симплексного метода. Метод последовательного улучшения опорного плана - применяется к тем задачам линейного программирования, когда выполнены следующие условия:

Правая часть системы ограничений состоит из неотрицательных чисел, т.е. P0 > 0

Канонический вид системы содержит полный набор базисных векторов.

Рассмотрим задачу линейного программирования, система ограничений которой задана в виде неравенств.

Найти минимальное значение линейной функции:

(1.2.1) Z = С1х1+С2х2+… +СNxN

при ограничениях:

a11x1 + a22x2 +… + a1NХN b1

a21x1 + a22x2 +… + a2NХN b2

(1.2.2)……………M1x1 + aM2x2 +… + aMNХN bM

(1.2.3)xj 0 (j = 1, 2,…, n)

Совокупность чисел х1, х2,…, хN, удовлетворяющих ограничениям (1.2.2) и (1.2.3), называется решением. Если система неравенств (1.2.2) при условии (1.2.3) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х1Ох2 совместную систему линейных неравенств

a11x1 + a22x2 b1

a21x1 + a22x2 b2

…….M1x1 + aM2x2 bM

x1 0, x2 0

Это все равно, что в системе (1.2.2) - (1.2.3) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

ai1x1 + ai2x2 = bi,(i = 1, 2,…, m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

Совокупность этих точек (решений) назовем многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Если в системе ограничений (1.2.2) - (1.2.3) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2,…, n), а условия неотрицательности - полупространства с граничными плоскостями соответственно хj = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.2.2) - (1.2.3) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью ai1x1 + ai2x2 + aiNxN = bi (i = 1, 2,…, m), а условия неотрицательности - полупространства с граничными гиперплоскостями хj 0 (j = 1, 2,…, n).

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

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

1.3 Выбор метода реализации модели

Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

Описание различных задач на графах.

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

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Далее перечислим некоторые типовые задачи теории графов и их приложения:

Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

Связность графов и сетей

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

Изоморфное вхождение и пересечение графов

локализация неисправности с помощью алгоритмов поиска МИПГ

покрытие схемы заданным набором типовых подсхем

Автоморфизм графов

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

2. Расчет модели

2.1 Постановка задачи

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

Программа должна работать на IBM совместных персональных компьютерах. Если говорить о типе процессоров им должен быть Pentium 1 и выше, а объем запоминающего устройства 16 Мб. Тип видеоадаптера - SVGA.

В качестве контрольного примера рассмотрены следующие задачи:

Пусть установлены возможные варианты транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10. Все 10 пунктов можно отнести к пяти зонам (этапам). На линиях, соединяющих пункты, поставлено время проезда между соседними пунктами (рис. 1).

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

Рисунок 1

2.1.1 Экономическая интерпретация задачи

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

Для её выполнения был выбран язык программирования Delphi 7.0, Данная программа легка в пользовании, и подойдет для выполнения похожих задач на движение.

Для пользования программой подойдет любой компьютер с ОС.

2.1.2 Построение математической модели и методы ее реализации

Нахождение кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G = <V, E> дугам которых приписаны веса. Это означает, что каждой дуге? E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

Нас будет интересовать нахождение кратчайшего пути между фиксированными вершинами s, t? V. Длину такого кратчайшего пути мы будем обозначать d (s, t) и называть расстоянием от s до t (расстояние, определенное таким образом, может быть отрицательным). Если не существует ни одного пути из s в t, то полагаем d (s, t) = +. Если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем, т.е. в последовательности v1,…, vp не будет повторов.

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

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам, а каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну ситуацию получаем, когда вес дуги равен вероятности p (u, v) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляющих его дуг. Задачу нахождения наиболее надежного пути легко можно свести к задаче о кратчайшем пути, заменяя веса p (u, v) на a (u, v) = - lg p (u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а не самих путей. Однако, зная расстояние, мы можем при условии положительной длины всех контуров легко определить кратчайшие пути. Для этого достаточно отметить, что для произвольных s, t,? V (s, t) существует вершина v, такая что d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина произвольного кратчайшего пути из s в t. Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u,… не содержит повторений и оканчивается вершиной s. Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a (u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная таким образом последовательность t, v, u,… не содержит повторений и оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший путь из s в t.

Таким образом, мы получаем следующий алгоритм:

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

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v? V, фиксированная вершина t, матрица весов ребер, A [u, v], u, v? v.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

begin:=?; CTEK? t; v:= t;v? s do:= вершина, для которой D[v] = D[u] + A [u, v];? u;:= u.

Пусть - ориентированный граф, | V| = n, | E| = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v} двумя дугами? u, v? и? v, u?, каждая с таким же весом, что и {u, v}.

Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E> является ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A [u], u, v? V (A [u, v] содержит вес a (u, v)).

Кратчайшие пути от фиксированной вершины

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A [u, v], u, v? V, вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин v ОV. Каждый раз, когда мы устанавливаем, что D[u] + A [u, v] < D[v], оценку D[v] улучшаем: D[v] = D[u] + A [u, v].

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко можно показать, что значение каждой из переменных D[v] равно тогда d (s, v) - расстоянию от s до v. Заметим, что для того чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных.

Описанная общая схема является неполной, так как она не определяет очередности, в которой выбираются вершины u и v для проверки условия минимальности расстояния. Эта очередности, как будет показано ниже, очень сильно влияет на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа.

Сначала представим алгоритм для общего случая, в котором предполагается только отсутствие контуров с отрицательной длиной. С эти алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.

2.2 Математический метод решения задачи

Алгоритм Дейкстры (Dijkstras algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

Алгоритм Дейкстры (Dijkstra) предназначен для решения задачи Поиск кратчайших путей в графе.

Важным фактом, позволяющим исключить перебор, является то, что если у нас есть кратчайший путь от v до w, проходящий через вершину y, назовем его, то его первая часть от v до y, тоже будет кратчайшим путем. Действительно, если бы это было не так, т.е. существовал бы путь длины меньшей, чем, то можно было бы улучшить оптимальный путь, заменив в нем на (См. #Рисунок 1).

В алгоритме Дейкстры, мы, итерационно поддерживаем два множества вершин:

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

множество вершин, которые достижимы одним ребром из множества вершин Visited, ассоциированных с верхними оценками стоимости пути до них.

В иллюстрации выполнения алгоритма, мы показываем изменение на каждой итерации хэш-таблиц Visited и ToVisit, а в конце изображен входной граф, где сплошными линиями нарисованы имеющиеся ребра с ассоциированными длинами, а пунктиром - найденные кратчайшие пути.

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

Код алгоритма, представлен в виде функции на языке Python.

def dijkstra (G, start_node):

# хэш (узел -> стоимость) посещенных вершин={}

# хэш (узел -> стоимость) ближайших к посещенным={start_node:0}

# хэш (узел -> кратчайший путь)

Paths = {start_node: [start_node]}

# пока есть вершины, до которых не построен кратчайший путь

while ToVisit:

# выбираем ближайшую=argmin(ToVisit)

# до $v$ кратчайший путь найден[v]=ToVisit[v]; del ToVisit[v];

# для всех соседей вершины $v$

for w in G.neighbors(v):

# к которым еще не нашли кратчайший путь

if (w not in Visited):

# обновляем кратчайшие пути= Visited[v] + G.get_edge (v, w)(w not in ToVisit) or (vwLength < ToVisit[w]):[w] = vwLength[w] = Paths[v]+[w]_frame (G, start_node, Visited, ToVisit, Paths)

return (Visited, Paths).

2.3 Программная реализация модели

кратчайший путь программирование вершина

Задача данного курсового проекта реализована в языке программирования Borland Delphi 7.

В первую очередь Delphi предназначен для профессионалов-разработчиков корпоративных информационных систем. Может быть, здесь следует пояснить, что конкретно имеется в виду. Не секрет, что некоторые удачные продукты, предназначенные для скоростной разработки приложений (RAD - rapid application development) прекрасно работают при изготовлении достаточно простых приложений, однако, разработчик сталкивается с непредвиденными сложностями, когда пытается сделать что-то действительно сложное. Бывает, что в продукте вскрываются присущие ему ограничения только по прошествии некоторого времени. Delphi такие ограничения не присущи. Хорошее доказательство тому - это тот факт, что сам Delphi разработан на Delphi. Именно отсюда можно сделать вывод. Однако Delphi предназначен не только для программистов-профессионалов. Я читал в электронной конференции совершенно неожиданные для меня письма, где учителя, врачи, преподаватели ВУЗов, бизнесмены, все те, кто используют компьютер с чисто прикладной целью, рассказывали о том, что приобрели Delphi for Windows для того, чтобы быстро решить какие-то свои задачи, не привлекая для этого программистов со стороны. В большинстве случаев им это удается. [9,44]- это комбинация нескольких важнейших технологий:

1. Высокопроизводительный компилятор в машинный код
2. Объектно-ориентированная модель компонент
3. Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов
4. Масштабируемые средства для построения баз данных

В состав Borland Delphi 7 входят:

компилятор.

генератор отчетов.

среда визуального построителя приложений.

библиотека визуальных компонент.

Так же Borland Delphi 7 обладает открытой компонентной архитектурой. Благодаря такой архитектуре приложения, изготовленные при помощи Delphi, работают надежно и устойчиво. Delphi поддерживает использование уже существующих объектов, включая DLL, написанные на С и С++, OLE сервера, VBX, объекты, созданные при помощи Delphi. Из готовых компонент работающие приложения собираются очень быстро. Кроме того, поскольку Delphi имеет полностью объектную ориентацию, разработчики могут создавать свои повторно используемые объекты для того, чтобы уменьшить затраты на разработку.

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

Классы объектов построены в виде иерархии, состоящей из абстрактных, промежуточных, и готовых компонент. Разработчик может пользоваться готовыми компонентами, создавать собственные на основе абстрактных или промежуточных, а также создавать собственные объекты. [7,101]

Структурная и функциональная схемы программы

Описание процедур, функций, модулей, таблица идентификаторов

procedure 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); - процедура создание области вывода.

3. Анализ результатов расчета

Анализ результатов данной задачи приводит к тому, что оптимальный путь найден и удовлетворяет условию задачи. Эта задача была решена с помощью языка программирования Delphi 7.0 это значит. Сравнивая результат, полученный в программе и результат, полученный при решении вручную, оказываются одинаковы. Но для решения данной задачи в программе требуется несколько секунд, а для решения в ручную, намного больше времени.

Заключение

Цель курсового проекта - освоить и реализовать программу для нахождения кратчайшего пути в транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10.

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

Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

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

Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо «да», либо «нет». Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. «Опрос» завершается, когда удается установить то, что требовалось.

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH2n+2 Молекула каждого предельного углеводорода представляет собой дерево.

Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т.е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех. Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

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

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

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

Список литературы

1. Гольштейн, Е.Г. Линейное программирование./ Гольштейн, Е.Г., Юдин, Д.Б. Теория, методы и приложения. - М., Наука, 1969. - с. 424
2. Грешилов, А.А. Прикладные задачи математического программирования: учебное пособие для ВУЗов./ Грешилов, А.А. - М., Логос, 2006. - с. 286
3. Зайченко, Ю.П. Исследование операций./ Зайченко, Ю.П. - 2-е издание, перер. и доп. - Киев, Высшая школа, 1979. - с. 392
4. Таха. Введение в исследование операций./ Таха, Хэмди, А. - 6-е изд. - М., Изд. дом «Вильямс», 2001. - с. 912

5.Абанская А.В. Экономико-математическое моделирование - 2004. - 123 c.

.Гасс С. Линейное программирование - 2000. - 167 c.

.Дрогобыцкий И.Н. Экономико-математическое моделирование - 2006. - 88 c.

.Аверилл М. Лоу Имитационное моделирование - 2005. - 155 c.

.Колесов В.М. Моделирование систем. Объектно-ориентированный подход - 2006. - 199 c.

10. Колемаев В.А. Экономико-математическое моделирование - 2005. - 66 с.