38011

ИССЛЕДОВАНИЕ АЛГОРИТМОВ НА ГРАФАХ

Лабораторная работа

Информатика, кибернетика и программирование

Краткая теория Представление графов Для представления графов чаще всего применяется матрица смежности – это матрица [n n] где n число элементов а элементы [i j] могут быть равны значению 0 или x – flse или 1 – true в зависимости от того присутствует ли дуга из вершины i в вершину j рис.n] of integer то можно составить оператор L_SMEG_V который определяет множество смежных вершин для заданной вершины v и записывает их в вектор типа ms. function L_SMEG_Vv2 n1:integer; vr k1:integer:ms; {v2 – это вершина для которой ищут все...

Русский

2013-09-25

1.78 MB

2 чел.

11

Лабораторная работа № 7

«ИССЛЕДОВАНИЕ АЛГОРИТМОВ НА ГРАФАХ»

Цель работы: изучить различные алгоритмы работы на графах.

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

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
  3.  написать программу на любом языке;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Краткая теория

Представление графов

Для представления графов чаще всего применяется матрица смежности – это матрица A[n, n], где n - число элементов, а элементы A[i, j] могут быть равны значению 0 (или x)false или 1true, в зависимости от того, присутствует ли дуга из вершины i в вершину j (рис. 7.1). Если орграф помеченный, то в матрицу смежности помещают вместо 1 значение метки (рис. 7.2). Так же различают неориентированные (рис. 7.1 и 7.2) и ориентированные графы (рис. 7.3). Последние так же называются орграфами, у которых рёбра ориентированы.

Тогда тип для матрицы смежности – это

array [1..n, 1..n] of integer.

На рисунках 7.1 -7.3 отсутствие связи напрямую между вершинами обозначается знаком x – это обычно бесконечность, а для удобства расчётов на вычислительной машине используют очень большое число.

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

function SMEG_V(v1, i1 :integer):boolean;

{v1 – это вершина, для которой ищут смежную, а i1 – это вершина которую проверяют на смежность с заданной v1}

Begin

If A[v1, i1]>0 then SMEG_V:=true

Else SMEG_V:=false;

End; {Оператор определяет смежная ли вершина или нет, если да, то SMEG_V принимает значение true.}

Если ввести тип mas= array[1..n] of integer, то можно составить оператор, AL_SMEG_V, который определяет множество смежных вершин для заданной вершины v и записывает их в вектор типа mas.

function AL_SMEG_V(v2, n1:integer; var k1:integer):mas;

{v2 – это вершина, для которой ищут все смежные вершины; n1 – это число вершин в графе; k1 – это количество найденных смежных вершин для v2, которое передаётся в общую программу}

var i2:integer;

Begin

k1:=0;

for i2:=1 to n1 do

begin

if SMEG_V(v2, i2) then

Begin

k1:=k1+1;

AL_SMEG_V[k1]:=i2;

End;

End;

End; {Результатом выполнения данного оператора является заполненный массив AL_SMEG_V, который включает в себя список смежных вершин для заданной вершины v.}

Рассмотрим пример использования данных операторов. С клавиатуры вводится вершина v, для которой будут искаться смежные вершины. Так же известно число вершин в графе – это n. Количество смежных вершин для заданной v будет записано в k. Тогда кусочек программы, реализующий данный пример, будет иметь вид:

Writeln('enter v ----> ');

Readln(v);

AL_SMEG_V(v,n,k);

for i:=1 to k do

write(AL_SMEG_V(v,n,k)[i],'  ');

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

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

Известны два алгоритма по определению кратчайшего пути - это алгоритм Дейкстры и алгоритм Флойда.

Алгоритм Дейкстры используется для нахождения кратчайших по стоимости путей от одной заданной вершины до каждой вершины графа. При изменении заданной вершины расчёт проводят повторно, так как кратчайшие по стоимости пути будут другими. Таким образом, необходимо будет повторять расчёт столько раз, сколько вершин в графе. Чтобы избежать многократных расчётов, используют алгоритм Флойда, который сразу же вычисляет матрицу A[i, j] длин кратчайших путей между всеми возможными концевыми вершинами пути i и j.

Рассмотрим работу данных алгоритмов на примере «графов» (рис. 7.2 и 7.3).

Алгоритм Дейкстры. Необходимо найти кратчайшие пути от вершины 1 до вершин 2, 3, 4, 5 и 6 в ориентированном графе (рис. 7.3). Составим таблицу решения (табл. 7.1) для нахождения кратчайших путей.

В первую строку таблицы 7.1 записывают расстояния от искомой вершины до смежных с ней вершин, а в остальные ячейки строки записывают значок x, если напрямую связи нет. Так, например, от вершины 1 к вершине 2 идёт ветвь, стоимость которой равна 6, её мы и заносим в столбик D[2] первой стоки. А вот между 1 и 6 ветви нет, поэтому ставим в D[6] значок x. Далее среди значений стоимостей данной строчки выбирают наименьшую, и весь столбец, в котором она находится, заполняется вниз до конца данным значением. Больше данный столбец в дальнейших расчётах не используется (смотри столбец D[3] таблице 7.1). В нашем примере минимальной стоимостью оказалась 1, которой соответствует вершина 3. Номер этой вершины заносится во вторую строку таблицы столбца w, а так же во множество вершин уже выведенных из расчёта. Так если перед началом расчёта это множество было равно {1}, то теперь будет таким – {1,3}.

Таблица 7.1

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

Итерация

S

w

D[2]

D[3]

D[4]

D[5]

D[6]

Начало

{1}

-

6

1

x

x

x

1

{1,3}

3

6

1

x

7

5

2

{1,3,6}

6

6

1

8

7

5

3

{1,3,6,2}

2

6

1

8

7

5

4

{1,3,6,2,5}

5

6

1

8

7

5

5

{1,3,6,2,5,4}

4

6

1

8

7

5

Далее для вершины 3 ищутся смежные вершины – это 2, 5 и 6. После чего производится следующая проверка для заполнения второй строки:

D[n]=Min([vk,wn], D[m]+[vm,wn]),

где k – индекс начальной вершины (в нашем примере – это 1);

n – конечная вершина, до которой ищут кратчайшее расстояние;

m – последняя исключённая вершина.

В нашем случае для смежных вершин 2, 5 и 6:

k=1, m=3, а n будут равны соответственно 2, 5 и 6;

D[2]=min([v1,w2], D[3]+[v3,w2])=min(6, 1+x)=6;

D[5]=min([v1,w5], D[3]+[v3,w5])=min(x, 1+6)=7;

D[6]=min([v1,w6], D[3]+[v3,w6])=min(x, 1+4)=5.

Заполним полученными значениями вторую строку таблицы 7.1. и среди этих значений выберем наименьшую величину стоимости пути – это D[6]=5, которая соответствует вершине 6. Запишем данную вершину в множество {1,3} и получим {1,3,6}. Теперь производится проверка для заполнения третьей строки относительно вершины 6. Для неё определим смежные вершины – это вершина 4. Тогда можно записать:

k=1, m=3, а n=4

D[4]=min([v1,w4], D[6]+[v6,w4])=min(x, 5+3)=8.

Следовательно, в строке третей значения D[2]=6, D[5]=7 останутся прежними, а вот D[4], будет уже другим, т.е. 8. Далее алгоритм повторяется, пока множество вершин не станет равно {1,3,6,2,5,4}, т.е. будет включать все вершины графа.

Таким образом, последняя строка в таблице 7.1 включает минимальные расстояния от вершины 1 до вершин 2, 3, 4, 5, 6. Чтобы найти промежуточные вершины, через которые проходит кратчайший путь необходимо сделать следующее. Теперь начинать надо с конечной вершины и двигаться вверх по столбцу до того момента, когда изменится минимальное значение на большее. Выбирается то множество вершин, где минимальное значение появилось впервые. Если необходимо найти кратчайшее расстояние от вершины 1 до 4, то будем двигаться по столбику D[4] снизу вверх до третьей строки, где происходит переход от 8 к x. Этой строке соответствует множество пройденных вершин {1,3,6}, следовательно, кратчайший путь от 1 до 4 будет проходить через вершины 3 и 6.

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

Таблица 7.2

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

Итерация

S

w

D[2]

D[3]

D[4]

D[5]

D[6]

Начало

{1}

-

6

1

5

x

x

1

{1,3}

3

5

1

4

7

5

2

{1,3,4}

4

5

1

4

7

5

3

{1,3,4,2}

2

5

1

4

7

5

4

{1,3,4,2,6}

6

5

1

4

7

5

5

{1,3,4,2,6,5}

5

5

1

4

7

5

Алгоритм Флойда. Необходимо найти кратчайшие пути между всеми вершинами орграфа (рис. 7.3), т.е. рассмотреть все возможные варианты и направления.

Во время решения составляются матрицы (рис. 7.4 – 7.10), число которых равно числу итераций. Оно может быть различно, но не превышает числа вершин исследуемого графа. Каждая новая ячейка новой матрицы заполняется в соответствии с формулой (7.2), в которой k – это номер итерации или матрицы. Матрица нулевой итерации соответствует матрице смежности данного графа. Для нахождения элементов матрицы первой итерации пользуются матрицей нулевой итерации и т.д.

Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j])                   (7.2)

Так, например, выполняя третью итерацию при заполнении ячейки A[4,5] имеем следующее:

A3[4,5]=min(A2[4,5], A2[4,3]+A2[3,5])=min(14, 3+6)=9.

А сейчас для примера заполним ячейку A[6,1] четвёртой итерации: A4[6,1]=min(A3[6,1], A3[6,4]+A3[4,1])=min(x, 3+5)=8.

Для сравнения приведём нахождение кратчайших путей методом Флойда (рис. 7.11 – 7.14) для простого графа (рис. 7.2)

Как видно для неориентированных графов алгоритм Флойда более эффективен.

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

procedure Deykstra;

begin

S:={1};

for i:=2 to n do

D[i]:=A[1, i]; {инициализация D}

for i:=1 to n-1 do begin

выбор из множества V\S кой вершины w,

что значение D[w] минимально;

добавить w к множеству S;

for каждая вершина v из множества V\S do

D[v]:=min(D[v], D[w]+C[w, v] )

end;

end; {Результат выполнения данной процедуры – это заполненная табличка (см. табл. 7.1, 7.2)}

Для сравнения приведём кратчайшие расстояния (рис. 7.15 и рис. 7.16) от вершины 1 до всех вершин орграфа (рис. 7.3) и простого графа (рис. 7.2).

 

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

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

Самая простая реализация алгоритма Флойда выглядит так

procedure FLOYD;

{В данном алгоритме переменной x соответствует индекс i массива смежности, переменной y соответствует индекс j, а z – это номер итерации k в алгоритме Флойда.}

var x,y,z:integer;

Begin

for x:=1 to n do A[x,x]:=0;

for z:=1 to n do

for x:=1 to n do

for y:=1 to n do

if A[x,z]+A[z,y]<A[x,y] then A[x,y]:=A[x,z]+A[z,y]

End;{Результатом выполнения данного алгоритма является матрица кратчайших расстояний между всеми узлами графа, которая перезаписывается в массив A вместо матрицы смежности.}

Чтобы вывести матрицу кратчайших расстояний на экран необходимо выполнить следующие действия:

Readln;

FLOYD;

for i:=1 to n do

Begin

for j:=1 to n do write(A[i,j]:4,', ' );

writeln;

End;

Readln;

Так, например, для графа рис. 7.3 результат выполнения –матрица A (рис. 7.10), а для графа рис. 7.2 – матрица (рис. 7.14).

Вышеприведённый алгоритм не позволяет получить информацию о промежуточных узлах, через которые проходит этот минимальный путь. Для того чтобы получить данную информацию, необходимо изменить алгоритм выше приведённой процедуры FLOYD и использовать дополнительную процедуру PRINT_POINTS, которая будет выводить промежуточные узлы. Необходимо ввести новую матрицу P[i, j], в которой будут храниться самые первые промежуточные вершины в кратчайшем пути между вершинами i и j.

procedure FLOYD;

var x,y,z:integer;

Begin

for x:=1 to n do

for y:=1 to n do 

P[x, y]:=0; {обнуляем матрицу для предотвращения ошибок в дальнейших вычислениях}

for x:=1 to n do A[x,x]:=0;

for z:=1 to n do

for x:=1 to n do

for y:=1 to n do

if A[x,z]+A[z,y]<A[x,y] then

begin

A[x,y]:=A[x,z]+A[z,y];

P[x,y]:=z;

end;

end;{Результатом выполнения данного алгоритма является матрица кратчайших расстояний между всеми узлами графа, которая перезаписывается в массив A вместо матрицы смежности, а так же матрица промежуточных узлов P в кратчайшем пути.}

Для графа (рис. 7.3) матрица P будет иметь вид – рис. 7.17.

procedure PRINT_POINTS (var i4,j4: integer);

var k4:integer;

Begin

{k4 – это промежуточная вершина между i4 и j4 из кратчайшего пути}

k4:=P[i4,j4];

{если кратчайший путь содержит промежуточные вершины, то искать их в матрице P[i,j] и выводить на экран}

if k4<>0 then Begin

write(k4, ‘, ‘);

path(k4,j4);

End;

End;

Если заданы две точки: b – это начальная вершина, а c – это конечная вершина, и необходимо определить кратчайший путь между b и c, то нужно будет выполнить определённые действия в программе.

readln;

FLOYD;

write(‘Введите начальную вершину: ‘);

readln(b);

write(‘Введите конечную вершину: ‘);

readln(c);

readln;

writeln(‘Вершины кратчайшего пути: ’);

PRINT_POINTS(b,c);

readln;

Так, например, чтобы найти промежуточные вершины кратчайшего пути между вершинами 2 и 1 графа (рис. 7.3), нужно в матрице P (рис. 7.17) найти значение ячейки [2,1] – это вершина 3. Потом найти в матрице P значение ячейки [3,1] – это 6, т.е. от первой промежуточной вершины до искомой. Далее ищется ячейка [6,1] – это значение 4, а потом определяется [6,1] – это 0, после чего поиск прекращается. Таким образом, кратчайший путь от 2 до 1 проходит через вершины 3, 6 и 4.

Задания по вариантам

Найти кратчайшие расстояния между заданными точками в графе в соответствии с вариантом (табл. 7.3). Для всех вариантов использовать алгоритм Дейкстры и Флойда. Необходимо произвести решение как вручную, так и с использованием программы. Результаты сравнить. Граф для выполнения задания выбирать в соответствии с номером варианта.

Таблица 7.3

Выбор начальной вершины для реализации алгоритма Дейкстры

Номер начальной вершины

Вариант

1

1, 7, 13, 19, 25, 31, 37, 43, 49

2

2, 8, 14, 20, 26, 32, 38, 44, 50

3

3, 9, 15, 21, 27, 33, 39, 45

4

4, 10, 16, 22, 28, 34, 40, 46

5

5, 11, 17, 23, 29, 35, 41, 47

6

6, 12, 18, 24, 30, 36, 42, 48

    

   

    

      

     

    

      

        

      

     

    

     

  

         

    

   

     

    

 

  

    

 

  

  


 

А также другие работы, которые могут Вас заинтересовать

84258. Способы питания микроорганизмов 33.22 KB
  Пищей обычно называют вещества которые попав в живой организм служат либо источником энергии необходимой для процессов жизнедеятельности либо материалом для построения составных частей клетки. Голофитный способ – живые существа используют питательные вещества всасывая их в виде относительно небольших молекул из водного раствора. Чтобы проникнуть в клетку питательные вещества должны находиться в растворенном состоянии и иметь соответствующий размер молекул. Однако это не означает что микроорганизмы не используют высокомолекулярные...
84259. Химический состав микробной клетки 33.69 KB
  Связанная вода входит в состав коллоидов клетки и с трудом высвобождается из них. С потерей связанной воды нарушаются клеточные структуры и наступает гибель клетки. При удалении свободной воды гибели клетки не происходит.
84260. Механизмы поступления питательных веществ в клетку 32.25 KB
  ЦПМ регулирует не только поступление веществ в клетку но и выход из нее воды разнообразных продуктов обмена и ионов что обеспечивает нормальную жизнедеятельность клетки. Существует несколько механизмов транспорта питательных веществ в клетку: простая диффузия облегченная диффузия и активный транспорт. Транспорт веществ через цитоплазматическую мембрану схематично изображен на рис.
84261. Пищевые потребности и типы питания микроорганизмов 42 KB
  В зависимости от источника углерода микроорганизмы делятся на: автотрофы сами себя питающие которые используют углерод из неорганических соединений углекислого газа и карбонатов; гетеротрофы питаются за счет других – используют углерод из органических соединений. В зависимости от источника энергии различают: фототрофы – микроорганизмы которые в качестве источника энергии используют энергию солнечного света; хемотрофы – энергетическим материалом для этих микроорганизмов являются разнообразные органические и неорганические вещества....
84262. Понятие о конструктивном и энергетическом обмене 38.76 KB
  Из веществ среды перенесенных в клетку собираются строительные блоки из которых формируются биополимеры клетки и синтезируются белки жиры углеводы нуклеиновые кислоты и другие клеточные компоненты. Обмен веществ можно рассматривать как сумму двух явлений: катаболизма энергетического обмена представляющего собой ферментативное расщепление крупных органических молекул с выделением свободной энергии которая запасается в виде макроэргических связей в молекулах АТФ; анаболизма конструктивного обмена представляющего собой синтез...
84263. Энергетический метаболизм, его сущность. Макроэргические соединения. Типы фосфорилирования 35.11 KB
  Энергия образуемая при энергетическом обмене трансформируется в энергию макроэргических связей молекул АТФ. Процесс образования АТФ называется фосфорилированием. Механизм образования АТФ у разных групп микроорганизмов неодинаков. Фотофосфорилирование – образование АТФ при поглощении квантов света молекулами хлорофилла.
84264. Энергетический метаболизм хемоорганогетеротрофов, использующих процессы брожения 35.13 KB
  Образование молекул АТФ при брожении происходит путем субстратного фосфорилирования. Основными стадиями гликолиза являются присоединение фосфатных групп от молекулы АТФ и превращение во фруктозо16дифосфат. При этом образуется свободная энергия достаточная для образования 4 молекул АТФ.
84265. Энергетический метаболизм хемоорганогетеротрофов, использующих процесс дыхания 33.75 KB
  При этом на каждые 2 атома водорода поступающих в дыхательную цепь синтезируются 3 молекулы АТФ. Таким образом суммарный энергетический эффект процесса окисления одной молекулы глюкозы теоретически составляет 38 молекулы АТФ причем 2 молекулы АТФ образуются в результате субстратного фосфорилирования а 36 АТФ – при окислительном фосфорилировании.
84266. Понятие о чистых и накопительных культурах микроорганизмов 34.34 KB
  При культивировании происходит рост культуры – физиологический процесс в результате которого увеличивается биомасса – масса клеточного вещества данного микроорганизма. Для выделения чистой культуры используют плотные питательные среды на которых каждая клетка вырастает в виде изолированной колонии – популяции микроорганизмов одного вида. Перед выделением чистой культуры из какоголибо пищевого продукта или природного субстрата например: почвы воды в котором данный микроорганизм находится в небольших количествах вначале получают...