Исследование программ для работы с фотографиями

МБОУ «Гимназия №3 г. Горно-Алтайска»

 

 

 

Поиск пути на графе

(программирование)

 

 

 

 

 

 

 

Выполнил:Индикеев Дмитрий

Юрьевич, ученик 10Б класса,

Руководитель: Криворучко Елена Александровна

 

 

 

 

 

 

 

 

г.Горно-Алтайск

2012 г.

 

ОГЛАВЛЕНИЕ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

В различных областях математики и информатики возникает  потребность описания свойств тех  или иных объектов на языке теории графов и использования её результатов, что подчёркивает значимость изучения графов и их свойств. Графы достаточно широко применяются в технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом. Графы встречаются в сотнях разных задач. Например, задач передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем, прокладки Интернет-сетей и т.д. В некоторых случаях графы видны и «невооруженным глазом» - сеть дорог, электрическая цепь, структурная формула химического соединения, блок-схема. При желании графы можно обнаружить практически где угодно. Широкому распространению теории графов в большой мере способствует прогресс в области развития вычислительной техники. Внедрение вычислительной техники ставит и перед всей дискретной математикой, и перед теорией графов проблему нахождения не произвольных алгоритмов, позволяющих решать те или иные классы задач, а таких алгоритмов, которые допускали бы эффективную практическую реализацию с использованием современных компьютерных технологий.

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

Программное обеспечение:  ОС Windows, система программирования PascalABC.NET версии 3.0.1.35.

 Основные понятия теории графов

Граф- это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Графы подразделяются на ориентированные, неориентированные и смешанные (рис.1):

Если ребра ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом или орграфом (рис.1,а). Если ребра не имеют ориентации, то граф называется неориентированным (рис.1,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (рис.1,в). Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе под (в) дуга a7 является петлей.Граф называется полным, если все вершины связаны (т.е. соединены ребрами).

Способы задания графа: графический, матрица смежности, матрица  инцедентности. Квадратная матрица  порядка n (кол-во вершин), в которой элемент , стоящий на пересечении строки с номером и столбца с номером , определяется следующим образом:  называется матрицей смежности. Для обыкновенного графа она обладает особенностью: из-за отсутствия петель на главной диагонали стоят нули, а так как граф неориентированный, то матрица симметрична относительно главной диагонали. Другая матрица, ассоциированная с графом - это матрица инцидентности. Матрица инцидентности  имеет n строк и m столбцов, а ее элемент равен 1, если вершина с номером инцидентна ребру с номером , в противном случае он равен нулю.

Рис.2 Граф с занумерованными вершинами и ребрами и его матрицы смежности и инцидентности

 

Рис.3 Граф с занумерованными вершинами и ребрами и его матрицы инцидентности

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

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

 

 

 

Поиск в ширину и в глубину.

Алгоритм поиска в глубину (рис.4) стал одной из основных методик проектирования графовых алгоритмов. Поиск начинается с некоторой фиксированной вершины x₀, например, с висячей. Затем выбирается вершина x₁, смежная с x₀. После этого выбирается вершина х₂, смежная с х₁, и т.д. Еще не просмотренные вершины будем условно называть новыми. Если на k-м шаге поиска для вершины x_k существует новая вершина x_k+1, то она выбирается (перестаёт быть новой) и поиск продолжается от вершины x_k+1. Если же для вершины x_k новых вершин не существует, осуществляется возврат к вершине, из которой мы попали в x_k, и

поиск осуществляется от неё. Процесс                    рис. 4                                             продолжается до тех нор, пока не будет произведён возврат в вершину х₀. В процессе поиска вершины соединяют рёбрами .

Поиск в ширину (рис.5) отличается от поиска в глубину тем, что выбор очередной вершины происходит путем просмотра не одной, а всех смежных.

    Рис.5

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

В процессе выполнения этого алгоритма при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через u_i кратчайшее расстояние от исходного узла 1 до узла i, через d_ij - длину ребра (i, j). Тогда для узла j определим метку [u_j, i] следующим образом:

    [u_j, i] = [u_i + d_ij, i], d_ij >= 0    

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

 Вычислительная схема  алгоритма состоит из следующих  шагов.    

 Шаг 0. Исходному узлу (узел 1) присваивается метка [0, -]. Полагаем i = 1.    

 Шаг i. а) Вычисляются временные метки [u_i + d_ij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и если u_i + d_ij < u_j, тогда метка [u_j, k] заменяется на [u_i + d_ij, i].    

b) Если все узлы  имеют постоянные метки, процесс  вычислений заканчивается. В противном  случае выбирается метка [u_r, s] с наименьшим значением расстояния u_r среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.

 

Алгоритм Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае. Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.6 Треугольный  оператор

 

Оценка сложности алгоритмов

Таблица 1

 

Алгоритм	Объект	Сложность	Доп. память	Полезность
Поиск в ширину	Невзвешенный граф	О(N2)	О(N)	10
Поиск в глубину	Невзвешенный граф	О(N2)	О(N)	8
Алгоритм Дейкстры	Взвешенный граф без  рёбер отрицательного веса	О(N2)	О(N)	10
Алгоритм Флойда	Взвешенный граф	О(N3)	О(N2)	8

 

 

Описание используемых процедур в  программе

1)Используется модуль Crt, для очистки экрана.

2) Объявляются переменные и метки  и описываются процедуры. Следующие  идентификаторы являют собой:  graf- матрица смежности, visited- массив посещенности вершин, D- массив очереди, inf- бесконечность, z- метка, n- кол-во вершин;

3)Процедуры:

a)Simetria-делает матрицу симетричной;

б)petli- убирает петли из матрицы;

в) CheckGraf- редактирование матрицы смежности для BFS и DFS

г) ShowGraph- Вывод составленной матрицы смежности

д) InputD –процедура ввода для алгоритмов Флойда и Дейкстры

ж) Input- процедура ввода для поисков в ширину и в глубину

з) DFS- процедура поиска в глубину

и) BFS- процедура поиска в ширину

к) Deisktr- процедура алгоритма  Дейкстра

л) floyd- процедура алгоритма  Флойда

4) Функции

а) Min- определяет наименьшее число из 2 предложенных.

 

Диалог с пользователем

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

Рис.7 Выбор  метода обхода графа

В данном случае мы выбрали  пункт 1-Поиск в ширину(BFS). После чего на экране ЭВМ появляется меню в котором программа просит задать количество вершин графа (рис.8).

Рис.8 Выбор  кол-ва вершин в графе

В данном случае было задано 4 вершины. После этого программа  просит заполнить матрицу смежности с клавиатуры . После того, как матрица заполнена она корректируется и выводится на экран(рис.9).

Рис.9- Вывод  матрицы смежности

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

Рис. 10 Начало обхода

В данном случае выбрана вершина 2. Выводится результат.

Программа завершает  свою работу.

 

Анализ результатов работы

Для теста был взят полный граф с 4 вершинами 

Ниже представлена матрица  смежности данного графа 

Таблица 2

 

 

 

 

1)Алгоритм Флойда

В ходе работы программы была получена матрица кротчайших расстояний (табл.3)

 

Таблица 3

0	1	3	5
1	0	2	6
3	2	0	6
5	6	6	0

 

Из данной матрицы  можно сделать вывод: Что бы попасть  из вершины х1 в вершину х2 нужно  пройди расстояние равное 1, из х1 в х3-3(обход  через вершину х2), из х1 в х4- 5, из х2 в х3-2, из вершины х2 в х4-6(обход через вершину х1), из ч3 в ч4-6;

2)Алгоритм Дейкстры

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

Подведем итоги. Из 4-х иследованных методов, 2 применяются  для взвешенных графов (алгоритм Флойда и алгоритм Дейкстры) и  2 для невзвешенных (BFS и DFS). Сравнивая поиск в ширину и в глубину, можно сказать, что по способу легче первое, так как поиск в глубину использует больше машинных ресурсов. 

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

Поставленная  цель и текущие задачи работы выполнены.

 

 

 

 

 

 

 

 

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

1. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений структуры графов. – Н.Новгород: «Нижегородский университет», 2005.- 307 с.
2. Епашников А.М., Епашников В.А. Программирование в среде Turbo Pascal 7.0. –3-е изд., стер. – М.: «ДИАЛОГ-МИФИ», 1998. –288 с.
3. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990.
4. Окулов С.М.Программирование в алгоритмах.-М.:«Бином»,2002.-341 с.
5. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992.
6. Википедия [Электронный ресурс] URL http://ru.wikipedia.org - режим доступа свободный.
7. Интернет университет информационных технологий. Лекции: графы и алгоритмы [Электронный ресурс] URL http://www.intuit.ru/department/algorithms - режим доступа через регистрацию.
8. Форум программистов и сисадминов [Электронный ресурс] URL http://www.cyberforum.ru – режим доступа свободный.

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

uses crt;

const C=100;

inf=999999;

var graf:array[1..C,1..C] of integer;

ww,w,n:integer; 

visited:array[1..C] of boolean;

D:array[1..C] of integer;

// процедуры

procedure simetria;

    var i,j:integer;

begin

for i:=1 to n do

   for j:=1 to n do begin

   if graf[i,j]<>graf[j,i] then

      graf[j,i]:=graf[i,j];

end;

end;

 

procedure petli; {убираем петли из графа}

var

i,j:integer;

begin

for i:=1 to n do

 for j:=1 to n do begin

   if ((i=j) and (graf[i,j]<>0)) then

   graf[i,j]:=0;

end;

end;

 

procedure CheckGraph; {проверка матрицы смежности графа }

var i,j:integer;

begin

for i:=1 to n do

 for j:=1 to n do begin

 if graf[i,j]>1 then

    graf[i,j]:=1;

 if graf[i,j]<0 then

    graf[i,j]:=0; end;

petli;

simetria;

end;

 

procedure ShowGraph;

var i,j:integer;

begin

Clrscr;

Writeln('Матрица составлена(Скорректирована)');

for i:=1 to n do begin

Writeln;

Write(i,' | ');

for j:=1 to n do

Write (graf[i,j]:2,' '); {вывод }

end;

ReadKey;

end;

 

procedure InputD;

var

i,j:integer;

label m; 

begin

Clrscr;    

Writeln('укажите целое кол-во вершин в графе');

Readln(n);

while ((n<0) or (n>C)) do

begin

 if n<0 then

Writeln('Число вершин должно быть положительным');

 if n>C then

Writeln('Выберите меньшее число');

Readln(n);

end;           

writeln('Заполните матрицу смежности');

for i:=1 to n do 

for j:=1 to n do begin             

Writeln(i,'-',j,': ');

Readln(graf[i,j]);

end;              

petli;

simetria;

ShowGraph;          

end;

 

procedure Input;

var

i,j:integer;

begin

Clrscr;    

Writeln('Укажите целое кол-во вершин в графе');

Readln(n);

while ((n<0) or (n>C)) do

begin

 if n<0 then

Writeln('Число вершин должно быть положительным');

 if n>C then

Writeln('Выберите меньшее число');

Readln(n);

end;           

writeln('Заполните матрицу смежности');

for i:=1 to n do

for j:=1 to n do begin

Writeln(i,'-',j,': ');

Readln(graf[i,j]);

end;

CheckGraph;

ShowGraph;     

end;                

 

procedure Pgn(v:integer); {поиск в глубину }

var yk,t,j,k,i:integer;

    stt:array[1..C] of integer;

    pp:boolean;

begin 

yk:=1;

k:=1;

D[yk]:=v;

stt[yk]:=v;

visited[v]:=false;

 while (yk<>0) do begin

t:=stt[yk]; //выбор вершины

j:=1;

pp:=false;

 repeat

if ((graf[t,j]=1) and (visited[j]=false)) then

pp:=true

 else

j:=j+1;

 until ((pp=true) or (j>n));

if (pp=true) then begin

yk:=yk+1;

visited[t]:=true; {добавляем номер вершины }

k:=k+1;

D[k]:=j;

stt[yk]:=j;

end

else

begin

visited[t]:=true;

yk:=yk-1; //убираем номер вершины

end;

end; 

for i:=1 to n do begin

write(D[i]);

write('->');

end;

end;

 

procedure DFS; //подготовка к поиску в глубину

var v:integer;

begin

Writeln;

Writeln('Введите номер вершины откуда начать поиск в глубину');

Readln(v);

while((v<0) or (v>n)) do begin

Writeln('Нет такой вершины в графе, попробуй еще раз');

readln(v);

end;

Pgn(v);{начало поиска }

end;

 

procedure BFS;

var v,i, ps, pe : integer;//v-корневая вершина

begin

writeln;

writeln('введите номер вершины с которой следует начать обход в ширину');

readln(v);

while (v<1) or (v>n) do begin

writeln('Ошибка ввода! Такой вершины не существует');

readln(v);

end;  

ps := 1; //начало 

pe := 1; //конец

D[pe] := v;

visited[v] := TRUE;

while ps <= pe do begin

for i := 1 to n do if (graf[v, i] <> 0) and (not visited[i]) then begin

inc(pe);

D[pe] := i;

visited[i] := true;

end;

inc(ps);

v := D[ps];

end;

for i:=1 to n do begin

write(d[i]);

write('->');

end;

end;

 

procedure Deisktr;

var s,i, j, v, min : longint;{s – искомая вершина}

begin

writeln;

writeln('Введите искомую вершину');

readln(s);

while (s<1) or (s>n) do begin

writeln('Такой вершины не существует');

readln(s);

end;  

visited[s] := TRUE;

for i := 1 to N do D[i] := graf[s, i];

 for i := 1 to n-1 do  begin

min := inf;

for j := 1 to N do if (not visited[j]) and (D[j] < min) then begin

min := D[j];

v := j;

end;

for j := 1 to N do if (D[j] > D[v] + graf[v, j]) and (D[v] < inf) and (graf[v, j] < inf) then D[j] := D[v] + graf[v, j];

visited[v] := TRUE;

end;

writeln;

writeln('Поиск завершон');

for i:=1 to n do begin

writeln('Расстояние из вершины ',i,' в вершину: ',d[i]);

end;

end;

 

function Min(a,b:integer):integer;{алгоритм флойда }

begin

    if a < b then min := a else min := b;

end;

 

procedure floyd;

var i, j, k : integer;

W:array[1..C, 1..C] of integer;

begin

for i := 1 to N do for j := 1 to N do W[i, j] := graf[i, j];{копирование матрицы}

for k := 1 to N do

for i := 1 to N do

  for j := 1 to N do W[i,j] := min(W[i, j], W[i, k] + W[k, j]);

//âûâîä

writeln;

writeln('Поиск завершон');

writeln('Массив кратчайших расстояний');

for i:=1 to N do begin

writeln;

Write(i,' | ');

for j:=1 to N do begin

write(w[i,j]:2,' ');

end;

end;

end;

 

procedure obedinenieDFS;

begin

Input;

DFS;

Readln;

end;

 

procedure obedinenieBFS;

begin

Input;

BFS;

readln;

end;

 

procedure obedinenieDeisktr;

begin

InputD;

Deisktr;

readln;

end;

 

procedure obedineniefloyd;

begin

InputD;

floyd;

Readln;

end;

{тело  программы }

begin

z:Writeln('Выберите метод поиска в глубину:');

writeln('1-Поиск в ширину ');

Writeln('2-Поиск в глубину ');

writeln('3-Алгоритм Дейкстры ');

writeln('4-Алгоритм флойда ');

readln(w);

if w=1 then begin

obedinenieBFS;

end

else

if w=2 then begin

obedinenieDFS;

end

else

if w=3 then begin

obedinenieDeisktr;

end

else

if w=4 then begin

obedineniefloyd;

end;

readln;

end.