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

3 чел.

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

    

   

    

      

     

    

      

        

      

     

    

     

  

         

    

   

     

    

 

  

    

 

  

  


 

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

54421. Money 147.5 KB
  So, we need many things to be happy and one of them is money . Today we are going to talk about money and everything connected with it. You know how important money is in our life. Practically all our life is based on money. The majority of relations in the modern world are based on money.
54422. MONEY MAKES THE WORLD GO ROUND 72 KB
  And now you can read the key -word. Its the topic of our today lesson. Lets begin our discussion with the song. You know, friends, that there are so many different songs about money. Id like you to listen to one of the most famous ones sung by legendary group ABBA. Youve heard it already. But while listening fill in the gaps with the necessary words from the list below.
54423. Мониторинг как технология управления качеством образования учащихся в профильной школе 96 KB
  В связи с этим важное значение приобретает социальнопедагогический мониторинг качества образования учащихся позволяющий своевременно получать полную и объективную информацию о результатах работы в профильной школе и осуществлять прогнозирование ее развития. Объектом мониторинга является многоаспектная интеграция включающая учащихся и педагогов нормативное и процессуальное сопровождение образовательные профессиональные и личностные достижения всех участников образовательного взаимодействия и управления качеством профильного обучения....
54424. Мониторинг окружающей среды в Украине 80.5 KB
  Цель: организовать и провести в школе экологическую работу с группой детей и помочь им спасти жителей Мусорного острова; показать учащимся возможности применения экологических навыков в повседневной жизни; воспитывать уважительное отношение к окружающей среде и осознавать свою роль в ней. Изучение проблемы мусора. Реализация акции Нажми на мусор. Для того чтобы ознакомить детей с проблемой бытовых отходов необходимо начать работу с постановки проблемы мусора.
54425. Посилення великокнязівської влади за Володимира Мономаха 58.5 KB
  Мета: характеризувати процес посилення великокнязівської влади за Володимира Мономаха та довести що за його правління Київська Русь зазнала періоду піднесення; розвивати в учнів уміння давати характеристику історичному діячу визначати його місце в історичному процесі аналізувати матеріал роботи висновки працювати з джерелами інформації; переконати учнів у силі згуртованості та єдності на прикладі діяльності Володимира Мономаха виховання почуття патріотизму. Обладнання: Портрет Володимира Мономаха картини картки з джерелами...
54426. Владимир Мономах его внутренняя и внешняя политика 98.5 KB
  ЦЕЛЬ: охарактеризовать процесс усиления великокняжеской власти при Владимире Мономахе и доказать на примерах его внутренней и внешней политики что в период его правления Киевская Русь переживает период расцвета; развивать умение учащихся давать характеристику историческому деятелю определять его место в историческом процессе работать с картой анализировать материал делать выводы работать с историческими источниками; убедить учащихся в силе единства на примере деятельности Владимира Мономаха. ОБОРУДОВАНИЕ: карта портрет Владимира...
54427. Моральная ответственность 49.5 KB
  Перечислите качества личности шутника предположите каким в будущем он будет: другом сослуживцем сыном отцом Присуща ли шутнику моральная ответственность за свои поступки Чтобы вы посоветовали всем участникам Чему учит эта ситуация Обсуждение. Правильно ли поступают мальчишки по отношению к Юли Какие качества личности присущи обидчикам На каком уровне развита моральная ответственность за свои поступки у мальчишек Чтобы вы посоветовали всем участникам Чему учит эта ситуация Обсуждение.
54428. Учимся дружить 124 KB
  Цели и задачи. Нужно расположить буквы в правильной последовательности Чтобы получилось слово буквам нужно подружиться. Важно уметь находить друг с другом общий язык дружить. Мы обсудим: легко ли найти друга какие качества нужно развивать в себе чтобы научиться дружить.
54429. Морально – екологічне виховання 640 KB
  Спостережливість - це та дорогоцінна властивість людини завдяки якій вона здатна орієнтуватись в навколишньому середовищі розуміти різноманітний світ природи контактувати з людьми. Радість зустрічі із живою істотою надовго залишиться в пам’яті дітей пробудить допитливість добрі почуття до природи. Уперед до гармонії сучасного суспільства і природи до такої взаємодії окремої особи і людства із середовищем за якої спілкування з природою стало б джерелом всебічного збагачення людини яка прагне не знищувати а вдосконалювати життєві...