Сложность алгоритма

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.

В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d используется массив, время работы алгоритма есть  . Основной цикл выполняется порядка nраз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма  , но, так как  , оно составляет  .

Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время удаления вершины из   станет  , при том, что время модификации   возрастет до  . Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, скорость работы такой реализации  .

2.Дека́ртово де́рево — это двоичное дерево, в узлах которого хранятся:

ссылки на правое и левое поддерево;

ссылка на родительский узел (необязательно);

ключи x и y, которые являются двоичным деревом поиска по ключу x и двоичной кучей по ключу y; а именно, для любого узла дерева n:

ключи x узлов правого (левого) поддерева больше (меньше либо равны) ключа x узла n;

ключи   узлов правого и левого детей больше либо равны ключу y узла n.

Ссылка на родительский узел не обязательна, она желательна только для линейного алгоритма построения дерева.

Двои́чная ку́ча, пирами́да^[1], или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше, чем значения её потомков.

Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.

Последний слой заполняется слева направо.

Пусть нам известно из каких пар   требуется построить декартово дерево, причем также известно, что  .

Рекурсивный алгоритм

Рассмотрим приоритеты   и выберем максимум среди них, пусть это будет  , и сделаем   корнем дерева (по свойству пирамиды в корне должен быть элемент с максимальным приоритетом). Проделав то же самое с   и  , получим соответственно левого и правого сына  .

Такой алгоритм работает за  .

Операции

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

.

Эта операция устроена следующим образом.

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

: левое поддерево   совпадёт с левым поддеревом  . Для нахождения правого поддерева  , нужно разрезать правое поддерево   на   и   по ключу   и взять  .  совпадёт с  .

Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.

Рассмотрим вторую операцию с декартовыми деревьями —   (слить).

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

Рассмотрим принцип работы этой операции. Пусть нужно слить деревья   и  . Тогда, очевидно, у результирующего дерева   есть корень. Корнем станет вершина из   или   с наибольшим ключом  . Но вершина с самым большим   из всех вершин деревьев   и   может быть только либо корнем  , либо корнем  . Рассмотрим случай, в котором корень  имеет больший  , чем корень  . Случай, в котором корень   имеет больший  , чем корень  , симметричен этому.

Если   корня   больше   корня  , то он и будет являться корнем. Тогда левое поддерево   совпадёт с левым поддеревом  . Справа же нужно подвесить объединение правого поддерева   и дерева  .

Операция   добавляет в дерево   элемент  , где   — ключ, а  — приоритет.

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

Реализация №1

Разобьём наше дерево по ключу, который мы хотим добавить, то есть  .

Сливаем первое дерево с новым элементом, то есть  .

Сливаем получившиеся дерево со вторым, то есть  .

Операция   удаляет из дерева   элемент с ключом  .

Реализация

Спускаемся по дереву (как в обычном бинарном дереве поиска по  ), ища удаляемый элемент.

Найдя элемент, вызываем   его левого и правого сыновей

Результат процедуры   ставим на место удаляемого элемента.

Билет 8

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

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

Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.

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

Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, A_i0 равно 0 при i = s, и +∞ в противном случае.

Теперь рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из   ребра, к которому добавлено последнее ребро. Если про пути длины   все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.

Формальное описание   

Bellman_Ford(G, w, s)

1 Initialize_Single_Source(G, s)

2 for i «- l to |V[G]|-1

3 do for (для) каждого ребра (u, v) є E[G]

4 do RELAX(u,v,w)

5 for (для) каждого ребра (u, v) є E[G]

6 do if d[v] > d[u] + w(u, v)

7 then return FALSE

8 return TRUE

После инициализации в строке 1 всех значений d и prev, алгоритм осуществляет |V| — 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| — 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответству- ющее булево значение.

2.

Дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

1) позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

2) позволяет изменять значение любого элемента за O (log N);

3) требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

4) легко обобщается на случай многомерных массивов.

Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика для суммы

Дерево Фенвика для суммы поддерживает 2 операции:

1) modify с аргументами N и X — увеличить значение N-й ячейки массива a на число X (X может быть как положительно, так и отрицательно).

2) count с аргументом N — найти сумму чисел в ячейках массива a с 1-й по N-ю.

Дерево Фенвика для максимума

Дерево Фенвика для максимума поддерживает следующие операции:

1) modify с аргументами N и X — если значение в N-й ячейке массива a меньше X, то записать в неё число X. В противном случае оставить значение старым.

2) count с аргументами L и R — найти максимум чисел в ячейках массива a с L-й по R-ю.

БИЛЕТ 9

Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике,алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весьпройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается вочереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).

Как и алгоритм поиска в ширину, A* является полным в том смысле, что он всегда находит решение, если таковое существует.

Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, илипреемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. (Монотонность также известна как неравенство треугольника: одна сторона треугольника не может быть длиннее, чем сумма двух других сторон.) Математически, для всех путей x, y (где y — потомок x) выполняется:

A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньшеузлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути).

В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в неком лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.