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

СОДЕРЖАНИЕ

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

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

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

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

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

 

 

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

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

 

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

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

 

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

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

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

Пусть задан простой неориентированный  граф 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 = vi, смежных с 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-базой. 

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

 

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

 

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

 

 

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

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

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

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

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

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

Для  изображения  контекстного меню потребовалось обработать нажатие правой кнопки мышки.

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton; // по нажатию на кнопку и даже

Shift: TShiftState; X, Y: Integer);

begin

if button <>mbLeft then // если  нажали левой кнопкой

PopupMenu1.Popup(Mouse.CursorPos.X, Mouse.CursorPos.y); // показать  контекстное меню

end;


 

Для размещения ребра или вершины используется следующая схема.

 

3.3 Интерфейс программы 

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

 

 

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

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

На вкладке палитры компонентов Dialogs находятся компонент Delphi OpenDialog и компонент Delphi SaveDialog. Все Delphi диалоги, находящиеся на этой вкладке, в том  числе и Delphi диалоги выбора файла, невизуальные, т.е. при переносе их на Форму в работающей программе  их не видно, они видны только на этапе конструирования. Компонент Delphi OpenDialog позволяет открыть в нашей  программе стандартное Windows-окно диалога  открытия файла, компонент Delphi SaveDialog - окно диалога сохранения. Данные полученные из диалогов передаются в программу  для работы с конкретным файлом графа.

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

Для ориентированного графа матрица  может быть не симметрична относительно главной диагонали. Для неориентированного графа она всегда симметрична.

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

Компонент StringGrid предназначен в первую очередь для отображения таблиц текстовой информации.

Основные свойства компонента, определяющие отображаемый текст:

  • Cells[ACol, ARow: Integer]: string - Строка, содержащаяся в ячейке с индексами столбца и строки ACol и ARow.
  • Cols[Index: Integer]: TStrings - Список строк, содержащихся в столбце с индексом Index.
  • Rows[Index: Integer]: TStrings - Список строк, содержащихся в строке с индексом Index.

 

 

 

Заключение

 

 

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

 

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

 

 

1. Абдеев Р.Ф. Философия информационной  цивилизации. - М.: Владос, 1994.

2. Адамар Ж. Исследование психологии  процесса изобретения в области  математики. - М.: Сов. радио, 1970.

3. Болтянский В.Г. Информатика  и преподавание математики// Математика  в школе. 1989. № 4.-С.86-90

4. Вейценбаум Дж. Возможности вычислительных  машин и человеческий разум. - М.: Радио и связь, 1982.

5. Вирт Н. Алгоритмы+Структуры  данных=Программа. - М.:Мир, 1989

6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.

7. Громов Г.Р. Очерки информационной  технологии. - М.: ИнфоАрт, 1993.

8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.

9. Ильенков Э. В. Философия  и культура. - М.: Полит. лит., 1991.

10. Йодан Э. Структурное проектирование  и конструирование программ. - М.: Мир, 1979.

11. Майерс Г. Надежность программного  обеспечения. - М.: Мир, 1980.

12. Махмутов М.И. Организация  проблемного обучения в школе. - М., 1986.  

 

 

ПРИЛОЖЕНИЕ  А

Модуль реализации алгоритма  Дейкстры

Для упрощения понимания программы  и возможности использовать в  дальнейшем написанного кода было принято  решение разработать модуль для  реализации алгоритма Дейкстры. Работа данного модуля полностью соответсвует описанному алгоритму:

 

unit deikstra; // модуль  реализации алгоритма дейкстры

interface

const max = 100; //  максимальное  количество вершин

 inf =100*100*100; // замена  бесконечности

Type TJarak = Array [1..max,1..max] of Integer; //  матрица смежности (тип)

 

  TPath  = record // запись для хранения дерева решений

    nodeke : byte;

    Arraypath : Array [1..max] of byte;

    Jarak     : Integer;

  end;

Procedure RuteTerpendek(var Data : TJarak; var Closed : TPath;var awal,tujuan : integer;count : byte);

Implementation

Procedure RuteTerpendek(var Data : TJarak; var Closed : TPath;var awal,tujuan : integer;count : byte);

 

Var// локальные  переменные 

  Path : Array [ 1..max] of  TPath;

  Open,Jauh : Array[1..max] of Real ;

 

procedure Initdata(count : byte); //  иницаилизация переменных и выделение памяти

var i,j : byte;

begin

fillchar(Open,sizeof(Open),inf);

fillchar(jauh,sizeof(jauh),inf);

fillchar(Path ,sizeof(Path ),inf);

 

 

  for i := 1 to count do // вносим переданные данные в начало дерева решений

  begin

    open[i] := 0 ;

    path[i].Jarak  := 0;

    jauh[i] := data[awal,i] ;

    path[i].arraypath[1] := awal;


ПРИЛОЖЕНИЕ  А

 

    path[i].nodeke := 1;

    path[i].arraypath[2] := i;

    path[i].nodeke := path[i].nodeke + 1;

    path[i].Jarak  := Data[path[i].arraypath[1],path[i].arraypath[2]]

  end;

  open[awal] := awal ;

end;

procedure update_close(var Closed: TPath); // обновление  последней вершины решшения

begin

  closed := path[Tujuan] ;  // возвращаем  путь

end ;

 

function successor(count : byte) : byte ; // проверка  на достижисомть

var i,j : byte ;

  minimum : Real ;

begin

  minimum := inf;

  for i := 1 to count do

    if (jauh[i] < minimum) and (open[i] = 0) then // если путь лежащий через И меньше минимума и до этой вершины можно добраться то этот путь лучше

  begin

    minimum := jauh[i] ;

    j := i ;

  end ;

  successor := j ;

end ;

 

procedure lessthen(count,x : byte) ; //

var i : byte ;

  a,b : Real ;

begin

  for i := 1 to count do

  begin

    a := jauh[x] + data[x,i] ;

    b := jauh[i] ;

    if a < b then

    begin

      jauh[i] := a ;

      path[i] := path[x];

      path[i].nodeke := path[i].nodeke + 1;

      path[i].arraypath[path[i].nodeke] := i;

      path[i].Jarak  := path[i].Jarak + Data[path[i].arraypath[path[i].nodeke-1],path[i].arraypath[path[i].nodeke]]

    end;

  end ;

end ;


ПРИЛОЖЕНИЕ  А

 

 

procedure disktra(count : byte) ; // вызов процедуры поиска  пути 

var i,j : byte ;

begin

  for i := 1 to count do //  для всех вершин  графа

  begin

    lessthen(count,successor(count)) ; // начали  строить дерево решений  

    update_close(closed); // заменили последний достигнутый пунтк

    open[successor(count)] := successor(count) ; // теперь кратчайший путь лежит через него

  end ;end ;

begin

  initdata(count);

  disktra(count);

end;

 

end.


 


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