Доказательство

Основное утверждение, на котором основана корректность алгоритма Дейкстры, следующее. Утверждается, что после того как какая-либо вершина становится помеченной, текущее расстояние до неё уже является кратчайшим, и, соответственно, больше меняться не будет.

Доказательство будем производить по индукции. Для первой итерации справедливость его очевидна — для вершины имеем , что и является длиной кратчайшего пути до неё. Пусть теперь это утверждение выполнено для всех предыдущих итераций, т.е. всех уже помеченных вершин; докажем, что оно не нарушается после выполнения текущей итерации. Пусть — вершина, выбранная на текущей итерации, т.е. вершина, которую алгоритм собирается пометить. Докажем, что действительно равно длине кратчайшего пути до неё (обозначим эту длину через ).

Рассмотрим кратчайший путь до вершины . Понятно, этот путь можно разбить на два пути: , состоящий только из помеченных вершин (как минимум стартовая вершина будет в этом пути), и остальная часть пути (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Обозначим через первую вершину пути , а через — последнюю вершины пути .

Докажем сначала наше утверждение для вершины , т.е. докажем равенство . Однако это практически очевидно: ведь на одной из предыдущих итераций мы выбирали вершину и выполняли релаксацию из неё. Поскольку (в силу самого выбора вершины ) кратчайший путь до равен кратчайшему пути до плюс ребро , то при выполнении релаксации из величина действительно установится в требуемое значение.

Вследствие неотрицательности стоимостей рёбер длина кратчайшего пути (а она по только что доказанному равна ) не превосходит длины кратчайшего пути до вершины . Учитывая, что (ведь алгоритм Дейкстры не мог найти более короткого пути, чем это вообще возможно), в итоге получаем соотношения:

С другой стороны, поскольку и , и — вершины непомеченные, то так как на текущей итерации была выбрана именно вершина , а не вершина , то получаем другое неравенство:

Из этих двух неравенств заключаем равенство , а тогда из найденных до этого соотношений получаем и:

что и требовалось доказать.

Реализация

Итак, алгоритм Дейкстры представляет собой итераций, на каждой из которых выбирается непомеченная вершина с наименьшей величиной , эта вершина помечается, и затем просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра делается попытка улучшить значение на другом конце ребра.

Время работы алгоритма складывается из:

· раз поиск вершины с наименьшей величиной среди всех непомеченных вершин, т.е. среди вершин

· раз производится попытка релаксаций

При простейшей реализации этих операций на поиск вершины будет затрачиваться операций, а на одну релаксацию — операций, и итоговая асимптотика алгоритма составляет:

Реализация:

const int INF = 1000000000; int main() { int n;... чтение n... vector < vector < pair<int,int> > > g (n);... чтение графа... int s =...; // стартовая вершина vector<int> d (n, INF), p (n); d[s] = 0; vector<char> u (n); for (int i=0; i<n; ++i) { int v = -1; for (int j=0; j<n; ++j) if (!u[j] && (v == -1 || d[j] < d[v])) v = j; if (d[v] == INF) break; u[v] = true; for (size_t j=0; j<g[v].size(); ++j) { int to = g[v][j].first, len = g[v][j].second; if (d[v] + len < d[to]) { d[to] = d[v] + len; p[to] = v; } } }}

Здесь граф хранится в виде списков смежности: для каждой вершины список содержит список рёбер, исходящих из этой вершины, т.е. список пар , где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

После чтения заводятся массивы расстояний , меток и предков . Затем выполняются итераций. На каждой итерации сначала находится вершина , имеющая наименьшее расстояние среди непомеченных вершин. Если расстояние до выбранной вершины оказывается равным бесконечности, то алгоритм останавливается. Иначе вершина помечается как помеченная, и просматриваются все рёбра, исходящие из данной вершины, и вдоль каждого ребра выполняются релаксации. Если релаксация успешна (т.е. расстояние меняется), то пересчитывается расстояние и сохраняется предок .

После выполнения всех итераций в массиве оказываются длины кратчайших путей до всех вершин, а в массиве — предки всех вершин (кроме стартовой ). Восстановить путь до любой вершины можно следующим образом:

vector<int> path;for (int v=t; v!=s; v=p[v]) path.push_back (v);path.push_back (s);reverse (path.begin(), path.end());

8. Дерева. Приклади реалізації обходу дерева на об’єктно-орієнтованій мові програмування.

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Алгоритм обхода дерева в прямом порядке (рекурсивный)

· посетить корень

· посетить каждое поддерево в прямом порядке

Необходимые данные:

· массив son - список узлов и сыновей для них

· числовые массивы left и right

void Obhod_Dereva_Prymoi_Poryadok (int node) // функция получает в качестве аргумента номер узла

{

printf ("%d \n ", son[node]); // где массив son хранит "сыновей"

if (left[node]!= 0) Obhod_Dereva_Prymoi_Poryadok (left[node]);

if (right[node]!= 0) Obhod_Dereva_Prymoi_Poryadok (right[node]);

return;

}

Алгоритм обхода дерева в обратном порядке (рекурсивный)

· посетить каждое поддерево в обратном порядке

· посетить корень

Необходимые данные:

· массив son - список узлов и сыновей для них

· числовые массивы left и right

void Obhod_Dereva_Obratniy_Poryadok (int node) // функция получает в качестве аргумента номер узла

{

if (left[node]!= 0) Obhod_Dereva_Obratniy_Poryadok (left[node]);

if (right[node]!= 0) Obhod_Dereva_Obratniy_Poryadok (right[node]);

printf ("%d \n ", son[node]); // где массив son хранит "сыновей"

return;

}

Алгоритм обхода дерева во внутреннем порядке (рекурсивный)

Необходимые данные:

· массив son - список узлов и сыновей для них

· числовые массивы left и right

void Obhod_Dereva_Vnutr_Poryadok (int node) // функция получает в качестве аргумента номер узла

{

if (left[node]!= 0) Obhod_Dereva_Vnutr_Poryadok (left[node]);

printf ("%d \n ", son[node]); // где массив son хранит "сыновей"

if (right[node]!= 0) Obhod_Dereva_Vnutr_Poryadok (right[node]);

return;

}

9. Бінарні збалансовані дерева. Приклад реалізації вставки елемента дерева на об’єктно-орієнтованій мові програмування.

По определению, двоичное дерево называется сбалансированным (или АВЛ) деревом в том и только в том случае, когда высоты двух поддеревьев каждой из вершин дерева отличаются не более, чем на единицу. При использовании деревьев, соответствующих этому определению, обеспечивается простая процедура балансировки при том, что средняя длина поиска составляет O(log n), т.е. практически не отличается от длины поиска в идеально сбалансированных деревьях. Как доказали Адельсон-Вельский и Ландис, АВЛ-дерево никогда не превышает по глубине аналогичное сбалансированное дерево больше, чем на 45%.

Чтобы понять, как устроены "самые плохие" АВЛ-деревья, попробуем построить сбалансированное дерево с высотой h, содержащее минимальное число вершин. Обозначим такое дерево через Th. Понятно, что T0 - это пустое дерево, а T1 - дерево с одной вершиной. Дерево Th строится путем добавления к корню двух поддеревьев типа T(h-1). Одно из таких поддеревьев должно иметь высоту h-1, а другое может иметь глубину h-2. Такие "плохо" сбалансированные деревья называются деревьями Фибоначчи (поскольку принцип их построения напоминает принцип построения чисел Фибоначчи) и определяются рекурсивно следующим образом:

• (a) пустое дерево есть дерево Фибоначчи высоты 0;
• (b) единственная вершина есть дерево Фибоначчи высоты 1;
• (c) если T(h-1) и T(h-2) являются деревьями Фибоначчи высотой h-1 и h-2 соответственно, а x - новый корень дерева, то Th = <T(h-1), x, T(h-2)> есть дерево Фибоначчи высотой h;
• (d) другие деревья Фибоначчи не существуют.

Примеры деревьев Фибоначчи высотой 2, 3 и 4 показаны на рисунке 4.11.

(а) Дерево Фибоначчи высотой 2

(b) Дерево Фибоначчи высотой 3

(c) Дерево Фибоначчи высотой 4
Рис. 4.11. Примеры деревьев Фибоначчи

Число вершин в дереве Th определяется из следующего рекуррентного соотношения:

N0 = 0; N1 = 1; Nh = N(h-1) +1 + N(h-2)

Эти числа определяют число вершин в АВЛ-дереве в худшем случае и называются "числами Леонарда". Заметим, что из этого соотношения следует, что длина пути от корня любого листа в АВЛ-дереве может отличаться не более, чем на единицу.

Рассмотрим, как можно поддерживать балансировку АВЛ-дерева при выполнении операций включения и исключения ключей. Начнем с операции включения. Пусть рассматриваемое дерево состоит из корневой вершины r и левого (L) и правого (R) поддеревьев. Будем обозначать через hl высоту L, а через hr - высоту R. Для определенности будем считать, что новый ключ включается в поддерево L. Если высота L не изменяется, то не изменяются и соотношения между высотой L и R, и свойства АВЛ-дерева сохраняются. Если же при включении в поддерево L высота этого поддерева увеличивается на 1, то возможны следующие три случая:

• (a) если hl = hr, то после добавления вершины L и R станут разной высоты, но свойство сбалансированности сохранится;
• (b) если hl < hr, то после добавления новой вершины L и R станут равной высоты, т.е. сбалансированность общего дерева даже улучшится;
• (c) если hl > hr, то после включения ключа критерий сбалансированности нарушится, и потребуется перестройка дерева.

Имеет смысл рассмотреть две разные ситуации. В первой ситуации новая вершина добавляется к левому поддереву L, во второй - к правому поддереву. Правила восстановления балансировки показаны на рисунке 4.12 и проиллюстрированы примерами на рисунке 4.13.

(a)

(b)

(c)

(d)
Рис. 4.12.

(a)

(b)

(c)

(d)
Рис. 4.13.

Как кажется, в данном случае рисунки лучше проясняют суть явления, чем текст и тем более компьютерная программа. Действия, которые требуются для балансировки, авторы механизма назвали "поворотами". Действительно, если внимательно посмотреть на то, что происходит с деревом, это действительно напоминает его повороты относительно выбранной вершины.

При исключении вершин из АВЛ-дерева также возможна его не слишком сложная балансировка. Мы не будем приводить описание требующихся процедур, а проиллюстрируем их на нескольких последовательных примерах (рисунок 4.14).

(a)

(b)

(c)

(d)

(e)

(f)

(g)
Рис. 4.14.

Известно, что оценкой стоимости поиска в АВЛ-дереве, а также выполнения операций включения и исключения ключей является O(log n), т.е. эти деревья при поиске ведут себя почти так же хорошо, как и идеально сбалансированные деревья, а поддержка балансировки при включениях и исключениях обходится гораздо дешевле.

Дата добавления: 2015-11-16