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

    

   

    

      

     

    

      

        

      

     

    

     

  

         

    

   

     

    

 

  

    

 

  

  


 

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

22730. Основи програмної інженерії, курс лекцій 7.17 MB
  Даже простые системы ПО обладают высокой степенью сложности, поэтому при их разработке приходится использовать весь арсенал технических и инженерных методов. Таким образом, инженерия программного обеспечения – это инженерная дисциплина
22731. Політика адміністрації Дж. Буша (ст.) щодо СРСР на етапі його розпаду 29 KB
  Припинення холодної війни біполярної конфронтації зняло головну суперечність котра продукувала юнку ядерних озброєнь. Переведення міждержавних і міжнародних проблем у річище політичного діалогу поширення відносин партнерства створили клімат довіри який у свою черіу дав змоіу і СРСР і СШЛ піти па істотне скорочення ядерних озброєнь. І тій і іншій стороні необхідно було позбавитися від накопичень застарілих ядерних озброєнь експлуатація яких потребує великих витрат. закінчувалися гарантійні терміни експлуатації близько 60 ...
22732. Доктрина стримування 31 KB
  Тож керівництво США зробило спробу ізолювати СРСР у систесмі повоєнних міжнародних відносин проголосивши радянський режим аномальним збоченням природного шляху суспільного розвитку. яку направив до держдепартаменту радник посольства США в Москві маловідомий тоді дипломат Джордж Кеннан. Зміст її зводився до того що мирне співіснування США і Радянського Союзу є неможливим так само як і будьяке співробітництво між ними у вирішенні міжнародних питань. Кеннан уже як начальник відділу політичного планування держдепартаменту США...
22733. Основні напрямки зовнішньої політики адміністрації Дж. Буша (мол.) 34.5 KB
  Такая политика известна почти всем так как каждое государство исключая США при администрации Клинтона ее практикует. В строгом смысле эта поддержка не была необходимой но она оказала важную дипломатическую и экономическую помощь в борьбе США против терроризма. Вместе с тем администрация США решительно отвергла более широкую коалицию которая могла помешать борьбе с терроризмом в целом и ведению войны против талибов в частности. Администрация США поняла это несмотря на четкое осознание всей слабости многосторонних мер и коалиций и решила...
22734. Створення НАТО 32.5 KB
  Створення НАТО. після тривалих переговорів у Великій залі Державного департаменту США у Вашингтоні відбулася церемонія підписання Статуту Організації Північноатлантичного Договору НАТО. згідно з цим законом СПІА уклали вісім двосторонніх угод із західноєвропейськими членами НАТО про фінансову допомогу у військовій сфері. керуючись законом конгрес затвердив суму асигнувань 95 млрд доларів для кредитування закупок військової техніки та обладнання членами НАТО.
22735. Зовнішньоекономічна програма США після ІІ світової війни 26.5 KB
  Зовнішньоекономічна програма США після ІІ світової війни. Проте США не зазнали на відміну від європейських держав проблем пов'язаних з війною руйнації міст та сіл. Зате на США припала третина воєнних витрат в антигітлерівській коаліції. Найголовніший результат американської участі у другій світовій війні полягав у тому що США перетворилися в наймогутнішу країну капіталістичного світу стали його економічним та фінансовим центром і незаперечним військовополітичним лідером.
22736. Ескалація інтервенції США у В'єтнамі 1965 - 1968 рр. 30.5 KB
  Ескалація інтервенції США у Вєтнамі 1965 1968 рр. Воспользовавшись спровоцированными инцидентами США подвергли 5 августа 1964 г. 10 августа президент США утвердил закон принятый 7 августа на совместном заседании палаты представителей в сената США. Эта так называемая тонкинская резолюция санкционировала принятие президентом США необходимых мер два отражения любого вооруженного нападения против военных сил США и предотвращения дальнейшей агрессии.
22737. Початок ’’холодної війни’’ США проти СРСР у 1946 – 1949 рр 37 KB
  Початок холодної війни США проти СРСР у 1946 1949 рр. Але наступного ж дня 3 лютого у США розпочалася пропагандистська кампанія з приводу радянського атомного шпіонажу до речі про інтерес спецслужб СРСР до Манхеттенського проекту американському керівництву стало відомо щонайменше за півроку до появи відповідної інформації у ЗМІ. Черчилль не висловив і побоювань щодо можливості воєнного нападу СРСР на країни Заходу. СРСР який переміг у війні та вперше розірвав буферний пояс що ізолював його від світу відчув за думкою...
22738. Зовнішня політика адміністрації Трумена. «Доктрина Трумена» 33 KB
  Американский империализм стремился использовать финансовоэкономические трудности Англии усугубленные кабальным займом полученным ею от США в июле 1946 г. Американские дипломаты убеждали своих английских коллег что для их правительства самым благоприятным выходом была бы передача этой доли наследства в руки США как для облегчения финансового бремени Англии так и для ухода от той критики которой повсеместно подвергался британский империализм за его интервенцию в Греции. правительство США получило две британские ноты в которых...