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

    

   

    

      

     

    

      

        

      

     

    

     

  

         

    

   

     

    

 

  

    

 

  

  


 

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

81379. Познавательные возможности и особенности количественной методологии в социологии при анализе социальной работы 37.93 KB
  Организация наблюдения включает в себя определение характеристик объекта целей и задач наблюдения выбор вида наблюдения разработку программы и процедуры наблюдения установление параметров наблюдения разработку техники выполнения результатов анализ результатов и выводов. добивается максимального взаимодействия с объектом наблюдения не обнаруживая как правило своих исследовательских намерений на практике.
81380. Понятие и виды социологических исследований 34.64 KB
  Качественные методы социологии позволяют социологу понять суть какоголибо социального явления а количественные понять насколько массово часто встречаемо это социальное явление и насколько оно важно для общества. Количественные методы: социологический опрос анкетирование и интервьюирование контентанализ документов наблюдение эксперимент Качественные методы: фокус группа исследование случая кейс стади этнографические исследования неструктурированные интервью.
81381. Измерение эффективности социальной работы и типы шкал. Приведите примеры использования 36.91 KB
  Показатели эффективности социальной работы. В связи с тем что социальная работа направлена на удовлетворение социальных потребностей человека правомерно признать главным критерием эффективности социальной работы как и определяющим критерием гуманности общества полноту удовлетворения интересов отдельного человека или различных сообществ людей во всех сферах жизни. Исходя из этих особенностей следует подходить к определению критериев социальной работы.
81382. Понятие и построение выборки в социологическом исследовании социальной работы 41 KB
  Задача построения выборки возникает всякий раз когда необходимо собрать информацию о некоторой группе или большой совокупности людей. Выборка это подмножество заданной совокупности популяции позволяющее делать более или менее точные выводы относительно совокупности в целом. Первым шагом в построении любой модели отбора включая вероятностную является определение генеральной совокупности. Любую генеральную совокупность характеризует какойлибо значимый признак или набор признаков по которым мы можем отнести конкретный объект к данной...
81383. Обработка и обобщение социологической информации в социологическом исследовании 36.58 KB
  Обработка данных включает в себя следующие компоненты: Редактирование и кодирование информации. Основное назначение этого шага состоит в приведении к единой форме унификации и формализации отображение объектов некоторой предметной области с помощью символов той информации которая была получена в ходе исследования. В зависимости от методов получения первичной информации возможно применение различных приемов обработки и анализа данных.
81384. Разработка программы социологического исследования социальной работы 35.51 KB
  Программу социологического исследования это один из важнейших социологических документов в котором содержатся методологические методические и процедурные основы исследования социального объекта. Ее можно рассматривать как теорию и методологию конкретного исследования отдельного эмпирического объекта или явления которое представляет собой теоретикометодологическую основу процедур всех этапов исследования сбора обработки и анализа информации. Функции программы социологического исследования: Методологическая Методологическая функция...
81386. Качественные методы сбора первичной информации. Основное назначение и случаи применения 38.95 KB
  Качественные методы социологии : Фокусгруппа Проведение интервью в группе из 812 человек с определенными параметрами в зависимости от целей исследования. В групповой дискуссии интервьюируемый оказывается в ситуации общения с себе подобными что помогает снимать защитные психологические барьеры и облегчает выражение эмоциональных реакций. Источниками информации в таком исследовании могут быть письма личные документы фотографии образцы фольклора а также групповые интервью. Неструктурированные интервью диалог в начале которого не...
81387. Технология проведения качественных исследований. На примерах глубинного интервью и фокус-группового исследования 40.77 KB
  На примерах глубинного интервью и фокусгруппового исследования. Проведение интервью в группе из 812 человек с определенными параметрами в зависимости от целей исследования. В групповой дискуссии интервьюируемый оказывается в ситуации общения с себе подобными что помогает снимать защитные психологические барьеры и облегчает выражение эмоциональных реакций. Подготовка Фокусированное интервью как и любое другое социологическое исследование предполагает: написание программы где формулируется и обосновывается проблема определяются цель...