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

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

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

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

2 Высокопроизводительный компилятор в машинный код

3 Объектно-ориентированная модель компонент

4 Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов

5 Масштабируемые средства для построения баз данных

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

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

 

Анализ результатов данной задачи приводит к тому, что оптимальный путь найден и удовлетворяет условию задачи. Эта задача была решена с помощью языка программирования 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 с.