Проектирование АИС

СОДЕРЖАНИЕ

Введение             3

1. Основные сведения о матрицах смежности.       5

2. Математические зависимости для определения заданных свойств графа  6

2.1. Основные определения.          6

2.2. Алгоритм Дейкстры «Нахождение минимального пути»    7

3. Структура программы  14

3.1 Хранение информации о графе  15

3.2 Входные и выходные данные  16

3.3 Анализ программы  16

4. Руководство пользователя  23

Заключение  25

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

 

 

Введение

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

Курсовой  проект выполняется с целью закрепления  знаний и развития навыков самостоятельного проектирования алгоритмов и программ.

Задачами  курсового проекта являются:

• Исследование графов
• изучение основных свойств графов 
• изучить один алгоритм на грае
• написание программы, которая выполняет один из алгоритмов на графе

Графом  называется алгоритмическая модель, состоящая из множества вершин (узлов) v и соединяющих их ребер e. Ребро - неупорядоченная пара вершин графа. Ребра называются смежными, если они имеют общую вершину. Вершины называются смежными, если есть ребро их соединяющее. Ребро, которое соединяет вершины, называется инцидентным этим вершинам, а вершины – инцидентные этому ребру.

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

 

В своей работе я конкретно рассмотрю  метод  алгоритма Дейкстры «Нахождение минимального пути» .

Исходные  данные к курсовому проекту:

Способ представления  графа в ЭВМ:

• Матрица смежности.

Перечень  свойств графа, которые необходимо определить:

• Определить минимальный путь между заданными вершинами.

 

1. Основные  сведения о матрицах смежности.

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

Если  в клетке i,j установлено значение ПУСТО, то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Чаще всего за значение ПУСТО берут 0, а в клетки, которые обозначают наличие дуги, вписывают вес этой дуги. Если граф не взвешенный, то вес дуги считается равным единице.  

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

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

Разрежённым называется граф, в котором  множество рёбер значительно  больше квадрата множества вершин.

 Если граф разрежён, то большая  часть памяти напрасно будет  тратиться на хранение нулей,  зато в случае неразрежённых графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно (n^2)/8 байт памяти, что может быть на порядок лучше списков смежности.

2. Математические  зависимости для определения  заданных свойств графа

1. Основные  определения.

Неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:

• V это непустое множество вершин или узлов,
• E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

 

 

Путь в графе G =(V,E) последовательность вершин   при  , таких, что две любые последовательные вершины соединены хотя бы одной дугой из E.

Число k рёбер в пути называется его длиной. Каждая из пар двух последовательных вершин называется его звеном. 

 

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

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

 

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

• Для построения минимального остовного дерева во взвешенном графе – алгоритм Прима
• Для нахождения минимального пути между двумя заданными вершинами во взвешенном графе – алгоритм Дейкстры.

2.  Алгоритм Дейкстры «Нахождение минимального пути»

Пусть задан простой неориентированный  граф G = (V, E), как конечное множество  вершин V и множество E неупорядоченных  пар {vi, vj} – ребер. Каждому ребру предписано действительное число a[i][j] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q, то есть такую последовательность вершин u1,u2,…,un, что u1=s, un=q, {ui, ui+1}IE для всех 1 ? i ? n-1, и сумма длин ребер {ui, ui+1} минимальна. Задача решается с помощью алгоритма Дейкстры:

• Каждой вершине припишем временный вес t (vi) = ?. Положим t (s) = 0 и далее t (s) изменяться не будет, т.е. t (s) – постоянный вес вершины s. Положим v = s.
• Для всех вершин u = v_i, смежных с v, имеющих временный вес, изменяем вес по формуле .
• Устанавливаем постоянный вес той вершины u, которая имеет наименьший временный вес. Положим v = u. Если v = q, то t (v) – длина кратчайшего пути из s в q. Если v ? q, то переходим к шагу 2.

В результате работы алгоритма получим  длину кратчайшего пути из s в q. Чтобы  найти вершину и ребра, составляющие этот путь, нужно определить массив h[|V|], где h[v] – вершина, предшествующая вершине v на кратчайшем пути, а в  шаге 2 добавить операцию h[u] = v, в случае, когда t (u) > t (v)+a[v][u].

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

В тексте программы веса вершин записываются в массив t [ ]. Для обозначения того, что для вершины v вес t [v] постоянный, вводится массив x[ ]. Равенство x[v]=1 будет означать, что t [v] – постоянный вес. 

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

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин с этими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью по вершинам множества S1. (Так как при каждой итерации во множество S1 включается только одна вершина, то обновление пометки l(xi) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к xi* не проходит целиком по S1 и содержит по крайней мере одну вершину из S2, и пусть xj S2 – первая такая вершина в этом пути. Так как по предположению cij неотрицательны, то часть пути от xj к xi* должна иметь неотрицательный вес   и . Это, однако, противоречит утверждению, что l(xi*) – наименьшая временная пометка, и, следовательно, кратчайший путь к xi* проходит полностью по вершинам множества S1, и поэтому l(xi*) является его длиной.

Так как вначале множество S1 равно (s) при каждой итерации к S1 добавляется xi*, то предположение, что l(xi*) равно длине кратчайшего пути  xi S1, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Если  требуется найти кратчайшие пути между s и всеми другими вершинами  полного связного графа с n вершинами, то в процессе работы алгоритма выполняются  операций сложения и сравнения на шаге 2 и еще   операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще   операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.

Как только длины кратчайших путей от s будут найдены (они будут заключительными  значениями пометок вершин), сами пути можно получить при помощи рекурсивной  процедуры с использованием соотношения (*). Так как вершина xi' непосредственно предшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну из оставшихся вершин, для которой

' ' . (*)

Если  кратчайший путь от s до любой вершины  xi является единственным, то дуги (xi', xi) этого кратчайшего пути образуют ориентированное дерево с корнем s. Если существует несколько «кратчайших» путей от s к какой-либо другой вершине, то при некоторой фиксированной вершине xi' соотношение (*) будет выполняться для более чем одной вершины xi. В этом случае выбор может быть либо произвольным (если нужен какой-то один кратчайший путь между s и xi), либо таким, что рассматриваются все дуги (xi', xi), входящие в какой-либо из кратчайших путей и при этом совокупность всех таких дуг образует не ориентированное дерево, а общий граф, называемый базой относительно s или кратко – s-базой. 

3. Структура программы

 

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

 

3.1 Общая схема работы  программы

 

 

3.2 Визуальный редактор

Delphi обладает широким набором  возможностей. Среда устраняет необходимость  программировать такие компоненты Windows общего назначения, как метки,  пиктограммы и даже диалоговые  панели. Диалоговые панели (например, Choose File и Save File) являются примерами  многократно используемых компонентов,  встроенных непосредственно в  Delphi, который позволяет приспособить эти компоненты к имеющийся задаче, чтобы они работали именно так, как требуется создаваемому приложению. Также здесь имеются предварительно определенные визуальные и невизуальные объекты, включая кнопки, объекты с данными, меню и уже построенные диалоговые панели. С помощью этих объектов можно, например, обеспечить ввод данных просто несколькими нажатиями кнопок мыши, не прибегая к программированию. Это наглядная реализация применений интерактивных технологий в современном программировании приложений. Та часть, которая непосредственно связана с программированием интерфейса пользователя системой получила название визуальное программирование.

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

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