При работе с графами часто приходится выполнять некоторые действия по одному разу с каждой вершиной графа. Например, некоторую информацию следует передать каждому из компьютеров в сети. При этом мы не хотим посещать каждый компьютер дважды. Аналогичная ситуация возникает, если мы хотим собрать информацию, а не распределить ее.
Подобный обход можно совершить двумя различными способами. При обходе в глубину проход по выбранному пути осуществляется настолько глубоко, насколько это возможно, а при обходе в ширину мы равномерно двигаемся вдоль всех возможных направлений.
В обоих случаях мы выбираем одну из вершин графа в качестве отправной точки.
4.3.1. Обход в глубину
При обходе в глубину мы посещаем первый узел, а затем идем вдоль ребер графа, пока не упремся в тупик. Узел неориентированного графа является тупиком, если мы уже посетили все примыкающие к нему узлы. В орграфе тупиком также оказывается узел, из которого нет выходящих ребер.
После попадания в тупик мы возвращаемся назад вдоль пройденного пути, пока не обнаружим вершину, у которой есть еще не посещенный сосед, а затем движемся в этом направлении. Процесс оказывается завершенным, когда мы вернулись в исходную точку, а все примыкающие к ней вершины уже оказались посещенными.
При выборе одной из двух вершин будем выбирать вершину с меньшей меткой.
Например, для графа на рис.4.4 обход в глубину будет соответствовать следующему порядку посещения вершин: 1, 2, 3, 5, 4, 8, 7 тупик; вернемся к 8 –тупик, возврат к 4 и посетим 9, 6.
Приведем пример алгоритма обхода в глубину:
DepthWay (А, N)
// А – матрица смежностей
// в стеке St хранятся номера просмотренных вершин графа
// уk - указатель стека
// Массив Nnew – Boolean признак того, что вершина просмотрена
V1; yk0; ykyk+1; St[yk]V;
Nnew (V) false;
while yk <> 0 do // пока стек не пустой
t St [yk] // выбор вершины из верхней точки стека
j 1; pp False
Repeat
if A [t, J] <> 0 and Nnew[j] then pp true
else jj+1
// найдена новая вершина рр или все вершины, связанные с данной просмотрены
until pp OR (j³N);
if pp then // новая вершина
ykyk+1; S[yk]j; Nnew[j]false
else ykyk-1 // убираем номер вершины из стека
endif
endwhile
end
4.3.2. Обход в ширину
При обходе графа по уровням мы, после посещения первого узла, посещаем все соседние с ним вершины. При втором проходе посещаются все вершины «на расстоянии двух ребер» от начальной. При каждом новом проходе обходятся вершины, расстояние до которых от начальной точки на 1 больше предыдущего.
В графе могут быть циклы, поэтому не исключено, что одну и ту же вершину можно соединить с начальной двумя путями. Мы обойдем эту вершину впервые, дойдя до нее по самому короткому пути. Чтобы предупредить повторные посещения, необходимо вести список посещений вершин.
Порядок обхода вершин графа, представленного на рис.4.4, соответственно 1, 2, 5, 3, 4, 8, 9, 6, 7
В основе обхода в глубину лежала стековая структура данных (LIFO), а при обходе по уровням мы воспользуемся очередью (FIFO)
WidthWay (G, v)
// G - граф, заданный некоторым способом
// v – начальная вершина обхода
Visit (v); Mark (v); Queue (v);
While очередь не пуста do
DeQueue (x) // исключаем пройденную вершину из очереди
for (каждого ребра Xw в графе G) do
if (вершина w не помечена)
then visit (w)
Mark (w)
Queue (w)
endif
endfor
endwhile
end
Этот алгоритм заносит в очередь корень дерева обхода по уровням, а затем немедленно удаляет его из очереди. При просмотре соседних с корнем вершин, он заносит их в очередь.
После посещения всех соседних с корнем вершин происходит возвращение к очереди и обращение к первой вершине оттуда.
Поскольку узлы добавляются в конец очереди, ни одна из вершин находящихся на расстоянии двух ребер от корня не будет рассмотрена повторно, пока не будут обработаны и удалены из очереди все вершины на расстоянии одного ребра от корня.
Асимптотическая оценка сложность приведенных алгоритмов – O(N2), где N – количество вершин, или О(М), где М – количество ребер.
С помощью любого из этих методов можно проверить, связен ли рассматриваемый граф. При обходе графа можно составлять список пройденных узлов, а по завершении обхода составленный список можно сравнить со списком всех узлов графа. Если списки содержат одни и те же элементы, то граф связен. В противном случае в графе есть вершины, до которых нельзя дойти из начальной вершины, поэтому он несвязен.
4.4. Поиск остовного дерева минимального веса
Минимальным остовным деревом (MOД) связного взвешенного графа, называется его связный подграф, представляющий собой дерево и состоящий из всех вершин исходного графа и некоторых его ребер, причем сумма весов ребер является минимально возможной (еще говорят – каркас минимального веса).
4.4.1. Алгоритм Дейкстры – Прима
Алгоритм использует для поиска MOД так называемый «жадный» метод. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе анализа этой части.
Для этой задачи – на каждом шаге рассматривается множество ребер, допускающих присоединение к уже построенной части остовного дерева, и из них выбирается ребро с минимальным весом.
Разобьем вершины графа на 3 класса: вершины, вошедшие в уже построенную часть дерева; вершины, окаймляющие построенную часть, и еще не рассмотренные вершины.
Начнем с произвольной вершины графа и включим ее в остовное дерево (выбор вершин в случае единственного MOД значения не имеет).
Все вершины, связанные с данной, заносим в кайму. Затем выполняется цикл поиска ребра с минимальным весом, соединяющего уже построенную часть остовного дерева с каймой.
Это ребро вместе с новой вершиной добавляется в дерево, и происходит обновление каймы. Работа заканчивается, когда в дерево попадут все вершины.
Общее описание алгоритма:
Выбрать начальный узел.
Сформировать начальную кайму (вершины, соседние с начальным узлом)
While в графе есть вершины, не попавшие в дерево do
выбрать ребро из дерева в кайму с min весом
добавить конец ребра к дереву
изменить кайму (для чего добавить в кайму вершины, соседние с новой)
обновить список ребер из дерева в кайму, так чтобы он состоял из ребер наименьшего веса.
endwhile
Работа данного алгоритма по шагам приведена на рис.4.5.
1 шаг (рис.4.5 б). В кайму заносятся вершины D,C,D,F. Минимальное ребро AB = 2, следовательно, к остову добавляем B.
2 шаг (рис.4.5.в) После добавления B, определяем, не следует ли добавить к кайме новые вершины. Выходим на вершины E и G.
Так как они соединены только с вершиной В уже построенной части дерева, мы добавляем соединяющие ребра к списку, рассматриваемому на следующем шаге.
Кроме того, необходимо проверить, являются ли ребра, ведущие из вершины A в C, D и F - кратчайшими, среди ребер, соединяющих эти вершины с деревом; или есть более удобные ребра из B? В исходном графе B не соединена непосредственно ни с C, ни с F, поэтому для них ничего не меняется. А вот ребро BD короче ребра AD, и поэтому должно его заменить.
Наименьший вес в кайме теперь у ребра BE (3), добавляем к дереву Е (рис.4.5г).
На следующем шаге добавляем вершину С (рис.4.5 д). Следующая вершина МОД – F (рис.4.5 д). Добавление очередных вершин показано на рис.4.5 е) и ж) соответственно.
Такой принцип добавления очередной вершины исключает циклы и образуемый алгоритмом на каждом шаге граф является деревом.
Существует красивое доказательство [1] того, что построенное остовное дерево обладает минимальным весом.
4.4.2. Алгоритм Крускала
В отличие от алгоритма Дейкстры – Прима, алгоритм Крускала (Kruskal) [1,2] делает упор на ребрах графа.
В этом алгоритме начинаем с пустого дерева и добавляем к нему ребра в порядке возрастания их весов, пока не получим набор из ребер, объединяющий все вершины графа.
Если ребра закончатся до того, как все вершины будут соединены между собой, то это означает, что исходный граф был несвязным, и полученный результат есть объединение МОД для всех его компонентов связности.
Пример поиска (тот же граф, что и для алгоритма Дейкстра-Прима, рис.4.5 а) приведен на рис. 4.6.
Выбираем ребро с минимальным весом DF на первом шаге. На втором шаге из оставшихся выбираем ребро АВ. Для всех остальных шагов выбираем ребро с минимальным весом. Добавляемое ребро не должно приводить к образованию циклов. Так, на 6-м шаге с одинаковым весом будут ребра CF, DB, DG, FG. Добавление CF или DB приводит к образованию циклов, поэтому их исключаем из рассмотрения. Добавление DG, FG – равнозначно.
Примерные шаги алгоритма:
1. Отсортировать ребра в порядке возрастания весов, инициализировать структуру разбиений.
2. Начав с первого ребра в перечне, добавлять ребра в граф Q, соблюдая условие: добавление не должно приводить к появлению цикла в Q.
3. Повторять шаг 2, пока число ребер в Q не стане равным N -1. Получившееся дерево является МОД.
4.5. Алгоритм поиска кратчайшего пути
Результатом алгоритма поиска кратчайшего пути является последовательность ребер, соединяющая две заданные вершины и имеющая наименьшую длину среди таких последовательностей.
На первый взгляд кажется, что мы можем воспользоваться алгоритмом построения МОД, чтобы отбросить лишние ребра, а затем взять путь, соединяющий заданные вершины в построенном остовном дереве. Но такое действие не всегда приводит к нужным результатам (рис.4.7). Путь по минимальному остовному дереву из А в В дает 4. При поиске МОД как раз исключается ребро АВ. Следовательно, для поиска кратчайшего пути этот алгоритм надо модифицировать.
Модифицированный алгоритм выглядит так:
1. выбрать начальную вершину
2. создать начальную кайму из вершины, соединенных с начальной
while вершина назначения не достигнута do
выбрать вершину каймы с кратчайшим расстоянием до начальной;
добавить эту вершину и ведущее в нее ребро к дереву;
изменить кайму путем добавления к ней вершин, соединенных с вновь добавленной;
for всякой вершины каймы do
приписать к ней ребро, соединяющее ее с деревом и завершающее кратчайший путь к начальной вершине
endfor
endwhile
end
На рис. 4.8 приведен поиск кратчайшего пути из вершины A в вершину G методом Дейкстры-Прима.
На первом шаге (рис.4.8 б) выбираем кратчайшее ребро, выходящее из А – ребро АВ. Далее смотрим, как следует обновить набор путей. С уже построенным деревом соединены теперь вершины E и G, их следует добавить к кайме (рис.4.8 в). Кроме того, мы должны посмотреть на вершину D и сравнить прямой путь из нее в А, длина которого равна 7, и окольный путь через вершину В (длина 8). Прямой путь короче, поэтому приписанное к D ребро менять не следует. Изучив имеющиеся возможности, выбираем кратчайший путь из А в С длины 4. Ребро ВЕ короче (3), но мы рассматриваем полную длину пути из А, а такой путь, ведущий к Е, имеет длину 5. теперь к дереву кратчайший путей добавляется вершина С (рис.4.8 г).
Далее выбираем либо путь из А в Е, либо из А в F, так как оба они имеют длину 5. Пусть алгоритм выбирает вершину с меньшей меткой, то есть Е (рис.4.8 д). Добавление Е не меняет остовных связей, поэтому теперь можно добавить вершину F (рис. 4.8 е).
Путь в вершину D короче пути в G, поэтому в дерево добавляем вершину D. Осталось добавить только вершину G (рис. 4.8 ж). В результате получается дерево кратчайшего пути из А в G, равного 10. Так как вершина G была добавлена последней, то мы получаем полное дерево кратчайших путей. Если бы добрались до нее раньше, то алгоритм тотчас бы завершил свою работу.
4.6. Вопросы для самоконтроля
Структуры данных для представления графов.
Алгоритмы обхода графа в глубину; в ширину.
Поиск минимального остовного дерева методом Дейкстры-Прима.
Поиск минимального остовного дерева методом Крускала.
Поиск кратчайшего пути.
5. Численные методы
Математические вычисления лежат в основе большого числа разнообразных программ. Компьютерная графика требует большого объема вычислений с многочленами и матрицами. Эти вычисления обычно выполняют для каждой точки экрана, поэтому даже незначительные улучшения алгоритма могут привести к заметному ускорению. (Например, при размере экрана в 1024х768 точек – даже выигрыш на одно умножение на каждой из позиций приводит к значительной экономии!).
Умножение матриц встречается в многочисленных приложениях. Модели физических объектов в компьютерной графике, а также компьютерном проектировании, часто представляют собой матрицы.
Общее свойство всех этих применений состоит в том, что матричные операции выполняются часто, поэтому чем быстрее они осуществляются, тем быстрее работают использующие их программы.
Пример: изображение 512х512 точек. При применении шаблона 5х5 точек при свертке – шаблон умножается на блоки картинки для всех возможных положений блока (512 – 5 + 1) = 508 положений по вертикали и столько же по горизонтали. Следовательно, матрица (5х5) должна быть умножена на 258 064 блоков.
При использовании стандартного алгоритма умножения матриц потребуется 32 258 000 умножений. Более эффективный алгоритм позволяет сэкономить значительное время.
В этом разделе нас будет интересовать число сделанных арифметических операций, поэтому будем подсчитывать число сложений (умножений).
При анализе численных алгоритмов в качестве параметра будет выбираться либо наивысшая степень многочлена, либо размер перемножаемых матриц.
5.1. Вычисление значений многочленов
Для полного многочлена n -ой степени вида:
P(x) = anxn + an –1 xn-1 + an-2 xn-2 + … + a1 x + a0 ,
будем предполагать, что коэффициенты (an … a0) известны и записаны в массив. Единственным входным данным служит х, а результат программы – значение многочлена в точке х.
Evaluate (x, A)
// A – массив коэффициентов многочлена
result a[0] + a [1] * x
x_Pow x
for i = 2 to n do
x_Pow x_Pow * x
result result + a [i] * x_Pow
endfor
return (result)
end
В цикле for содержатся 2 умножения, которые выполняются (n – 1) раз. Кроме того, одно умножение выполняется до цикла, поэтому общее число умножений 2(n – 1) + 1 = 2 n – 1.
В цикле выполняется также одно сложение и еще одно до входа в цикл, следовательно, сложений n – 1 +1 = n.
Общее число операций – (2 n – 1) умножений и n сложений.
Схема Горнера
Эта схема основывается на следующем представлении многочлена:
p (x) = (((… ((an x1 + an-1) x + an-2) x + an – 3 + … + a1) x + a0
Соответствующий алгоритм имеет вид:
Horner (x, A)
result a [n]
for i = n – 1 down 0 do
result result * x + a [i]
end for
return (result)
end
Цикл выполняется n раз, внутри одно умножение и одно сложение.
Общее число операций: n умножений и n сложений – двукратное уменьшение числа умножений по сравнению со стандартным алгоритмом.
5.2. Умножение матриц
Матрица - математический объект, эквивалентный двумерному массиву. Числа располагаются в матрице по строкам и столбцам. Две матрицы одинакового размера можно поэлементно сложить или вычесть друг из друга.
Если число столбцов в первой матрице совпадает с числом строк во второй матрице, то эти две матрицы можно перемножить. У произведения будет столько же строк, сколько в первой матрице и столько же столбцов, сколько во второй.
При умножении матриц размером 3х4 на матрицу размером 4х7 мы получаем матрицу размером 3х7.
Умножение матриц некоммутативно: оба произведения А´В и В´А двух квадратных матриц одинакового размера можно вычислить, однако результаты, вообще говоря, будут отличаться друг от друга.
Для вычисления произведения двух матриц каждая строка первой матрицы умножается почленно на каждый столбец второй. Затем подсчитывается сумма таких произведений и записывается в соответствующую клетку результата:
a
b
c
A
B
aA+bC+cE
aB+bD+cF
´
C
D
=
d
e
f
E
F
dA+eC+fE
dB+eD+fF
Умножение вышеприведенных матриц требует 12 умножений и 8 сложений.
5.2.1 Стандартный алгоритм умножения матриц
Стандартный алгоритм умножения матрицы размером a ´ b на матрицу размером b ´ c выполняет a×b×c умножений и a× (b - 1)× c сложений.
MultMatrix(G,H,R)
// R = G ´ H
// размеры матриц R(a´c), G(a´b), H(b´c)
for i=1 to a do
for j=1 to c do
R [i,j] 0
for k = 1 to b do
R[i, j] R[i, j] +G[i, k] * H[k, j]
end for // (k)
end for // (j)
end for // (i)
end
На первый взгляд это минимальный объем работы, необходимый для перемножения 2-х матриц. Однако исследователям не удалось доказать его минимальность, и в результате они обнаружили другие алгоритмы, умножающие более эффективно.
5.2.2. Умножение матриц по Винограду
Если посмотреть на результат умножения 2-х матриц, то видно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц
Рассмотрим два вектора V = (v1, v2, v3, v1) и W =(w1, w2, w3, w4)
Их скалярное произведение V *W = v1w1 + v2w2 + v3w3 + v4w4
Кажется, что второе выражение задает больше работы, чем первое: вместо четырех умножений их шесть, а вместо трех сложений – десять. Менее очевидно, что выражение в правой части допускает предварительную обработку: его части (v1v2, v3v4, w1w2, w3w4) можно вычислить заранее и запомнить для каждой строки первой матрицы и для каждого столбца второй.
То есть над предварительно обработанными элементами нам придется выполнять лишь первые два умножения и последующие 5 сложений, а также – дополнительно 2 сложения.
MultMatrixVinograd(G, H, R)
d b/2
// вычислить построчные произведения rowF для G
for i=1 to a do
rowf[i] G [i, 1] * G [i, 2]
for j = 2 to d do
rowf [i] rowf[i] + G [i, 2j – 1] * G [i, 2j]
endfor j
endfor i
// вычислить произведения для столбцов colF матрицы H
// прибавление членов в случае нечетной общей размерности
if (2 * (b/2)) <> b then
for i = 1 to a do
for j =1 to c do
R[i, j] R [i, j] + G [ i, b] * H [b, j]
endfor j
endfor i
endif
end
В случае четной общей размерности b общее число умножений (a×b×c+a×b+b×c)/2 и сложений (a× (b-2) +c× (b-2) +a×c× (3×b+2))/2.
5.2.3. Умножение матриц по Штрассену
Алгоритм Штрассена работает с квадратными матрицами. На самом деле он настолько эффективен, что иногда разумно расширить матрицы до квадратных, и при этом он все равно дает выигрыш, превышающий расходы на введение дополнительных элементов.
Для умножения 2х2 матриц алгоритм Штрассена использует семь формул. Эти формулы чрезвычайно неестественны, и, к сожалению, в оригинальной статье Штрассена не объясняется, как он пришел к ним. Замечательно, что как сами формулы, так и их использование не требует, чтобы умножение элементов матрицы было коммутативным. Это означает, в частности, что сами эти элементы могут быть матрицами, а, значит, алгоритм Штрассена можно применять рекурсивно. Вот формулы Штрассена:
Теперь элементы матрицы R могут вычисляться по формулам
R1,1= x1+ x4- x5+ x7;
R2,1= x2+ x4;
R1,2= x3+ x5;
R2,2= x1+ x3- x2+ x6.
Анализ общего случая показывает, что число умножений при перемножении двух N ´ N матриц приблизительно равно N2.81, а число сложений 6 N2.81-6 N2.
На практике алгоритм Штрассена применяется редко: его использование требует аккуратного отслеживания рекурсии. Важность его состоит в том, что это первый алгоритм, с помощью которого умножение матриц требует менее, чем О(N3) операций.
Сводная таблица оценок алгоритмов для умножения квадратных матриц размером N ´ N:
Основная идея алгоритма Штрассена для умножения матриц.
6. Алгоритмы сравнения с образцами
Поиск подстроки в длинном тексте - важный элемент текстовых редакторов. Поиск по образцу можно применять не только в текстовых строках, но и для поиска битовых или байтовых строк в двоичном файле. Так, например, осуществляется поиск вирусов в памяти компьютера.
В программе обработки текстов обычно имеется функция проверки синтаксиса, которая не только обнаруживает неправильно написанные слова, но и предлагает варианты их правильного написания.
6.1. Сравнение строк
Необходимо найти первое вхождение некоторой подстроки в длинном тексте.
Стандартный алгоритм начинает со сравнения первого символа текста с первым символом подстроки. Если они совпадают, то происходит переход ко второму символу текста и подстроки.
При совпадении сравниваются следующие символы. Так продолжается до тех пор, пока не окажется, что подстрока целиком совпала с отрезком текста, или пока не встретятся несовпадающие символы.
В первом случае задача решена, во втором - мы сдвигаем указатель текущего положения в тексте на 1 символ и заново начинаем сравнение.
Пример 6.1 Поиск подстроки (РЫБАК) в соответствующем тексте.
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление
Например, для графа на рис.4.4 обход в глубину будет соответствовать следующему порядку посещения вершин: 1, 2, 3, 5, 4, 8, 7 тупик; вернемся к 8 –тупик, возврат к 4 и посетим 9, 6.
