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

5 чел.

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

    

   

    

      

     

    

      

        

      

     

    

     

  

         

    

   

     

    

 

  

    

 

  

  


 

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

35129. БЕЛАРУСКАЯ МОВА. ПРАФЕСІЙНАЯ ЛЕКСІКА 1.48 MB
  Лічылася што мова закладзена ў самой біялагічнай сутнасці чалавека і перадаецца ў спадчыну. На самой справе мова зява біялагічная і псіхічная але ў тым сэнсе што ў чалавеку генетычна закладзена здольнасць авалодаць мовай г. Кожны чалавек валодае не мовай увогуле а канкрэтнай мовай ці мовамі што належыць пэўнаму народу. Сацыяльная прырода мовы заключаецца найперш у тым што яна аснова і форма грамадскай свядомасці і разам з тым унікальны і універсальны сродак зносін людзей феномен духоўнай культуры чалавецтва [7].
35130. Расчёт пространственного одноэтажного промышленного здания, оборудованного мостовым краном 414.33 KB
  Список литературы Исходные данные Количество пролетов 3; Длина пролета l1 = 18 м; Длина здания l = 168 м; Несущая конструкция покрытия балка; Шаг колонн 6 м; Высота до верха рельса 84 м; Грузоподъемность крана 15 т; Расчетное сопротивление грунта Rгр =019 МПа; Место строительства г. Расчет крайней колонны Данные для расчета сечений: бетон тяжелый класса B15 подвергнутый тепловой обработке при атмосферном давлении Rb = 85 МПа; Rbt = 075 МПа; Eb = 20500 МПа. Арматура класса АIII d 10 мм RS = RSC =...
35131. Форматирование результатов запроса 82 KB
  Например можно применить следующую команду чтобы увидеть определенные поля таблицы Slespeople упорядоченные по убыванию поля commission comm: SELECT snme comm FROM Slespeople ORDER BY 2 DESC; Мы рассматриваем это свойство ORDER BY для того чтобы продемонстрировать возможность его использования со столбцами выходных данных; эта процедура аналогична применению ORDER BY со столбцами таблицы. Например чтобы подсчитать заявки orders для каждого продавца slespeople и вывести результаты в убывающем порядке: SELECT snum COUNT DISTINCT...
35132. Создание таблиц 90 KB
  Команда CRETE TBLE Таблицы определяются с помощью команды CRETE TBLE создающей пустую таблицу таблицу не имеющую строк. Команда CRETE TBLE определяет имя таблицы и множество поименованных столбцов в указанном порядке. Синтаксис команды CRETE TBLE: CRETE TBLE имя таблицы имя столбца тип данных [ размер ] имя столбца тип данных [ размер ]. Поскольку пробелы используются для разделения отдельных частей команд в SQL их нельзя использовать как часть имени таблицы.
35133. Основные понятия SQL 152.5 KB
  Он используется для связи с такими системами управления базами данных как Orcle INGRES Informix Sybse SQLbse Microsoft SQL Server DB2 СУБД самой IBM продуктами SQL DC Prdox ccess pproch и многими другими. Обычно продукт базы данных включает не только СУБД. Собственно СУБД иногда ее называют исполнительной системой или исполнительным механизмом базы данных является рабочей лошадкой продукта. Она хранит данные осуществляет поиск и выборку данных а также записывает данные посредством исполнения операторов SQL В вычислительной...
35134. Альтернативная программная реализация выборки и модификации данных в базе данных Interbase 34.5 KB
  Конфигурируется ODBCисточник реализующий доступ к БД Interbse. В DBE dministrtor настраивается псевдоним БД доступной через BDE и представляющей собой в данном случае ODBCисточник. В отличие от 3го способа являющегося усовершенствованным подходом BDE 1й способ является более универсальным и более ресурсоемким в первую очередь по критерию времени поскольку представляет собой использование промежуточного уровня BDE и промежуточного уровня ODBC а 2й менее универсальным и менее ресурсоемким поскольку предполагает использование...
35135. Пример реализации трехзвенной архитектуры 39.5 KB
  Два разрабатываемых при этом программных компонента это сервер приложений и клиент взаимодействующие по протоколу DCOM. Разработка сервера приложений Основные шаги создания сервера приложений: Создание удаленного модуля данных Remote Dt Module. Однократный запуск программы с целью регистрации сервера приложений в реестре Windows. Для распределенного использования разработанных клиентского и серверного приложений требуется установка некоторых дополнительных программных компонент.
35136. Пример реализации обмена данными с Microsoft Excel 45.5 KB
  Создание новой книги Vrint MSBooks; MSBooks = MSExcel. Создание нового листа книги. Сохранение книги. Создание нового листа книги.
35137. Изучение формата баз данных Visual FoxPro 549.5 KB
  После заголовка таблицы следует цепочка 32байтовых описаний полей таблица 4.fmp Fp 01 1 YY Год последнего обновления таблицы Все 02 1 MM Месяц последнего обновления таблицы Все 03 1 DD День последнего обновления таблицы Все 04 4 RecordsCount Количество записей в таблице Все 08 2 HederSize Размер заголовка в байтах Все 10 2 RecordSize Размер записи в байтах Все 12 2 0x000x00 Зарезервировано Все 14 1 0x01 Начало транзакции D4 D5 0x00 Конец транзакции D4 D5 0x00 Игнорируется FS D3 Fb Fp CL 15 1 0x01 Закодировано D4 D5 0x00 Нормальная...