Файл: Задача сортировки массива заключается в том, чтобы расставить его элементы в определённом порядке (чаще всего по неубыванию. Это означает, что каждый элемент должен быть больше или равен всех предыдущих).docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.11.2023
Просмотров: 45
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
-
Хеширование
Хеш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.
«Хорошая» хеш-функция:
-
Быстро считается — за линейное от размера объекта время; -
Имеет не очень большие значения — влезающие в 64 бита;
«Детерминировано-случайная» — если хеш может принимать n различных значений, то вероятность того, что хеши от двух случайных объектов совпадут, равна примерно 1/n.
Обычно хеш-функция не является взаимно однозначной: одному хешу может соответствовать много объектов. Такие функции называют сюръективными.
Для некоторых задач удобнее работать с хешами, чем с самими объектами.
Хешируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения.
-
DFS.Графы
Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра.
Бывают различные варианты определения графа. В данном определении концы у каждого ребра – равноправны. В этом случае нет разницы где начало, а где – конец у ребра. Но, например, в транспортных сетях бывают случаи одностороннего движения по ребру, тогда говорят об ориентированном графе – графе, у ребер которого одна вершина считается начальной, а другая – конечной.
Алгоритм поиска (или обхода) в глубину (DFS) позволяет построить обход ориентированного или неориентированного графа, при котором посещаются все вершины, доступные из начальной вершины.
Отличие поиска в глубину от поиска в ширину заключается в том, что (в случае неориентированного графа) результатом алгоритма поиска в глубину является некоторый маршрут, следуя которому можно обойти последовательно все вершины графа, доступные из начальной вершины.
Этим он принципиально отличается от поиска в ширину, где одновременно обрабатывается множество вершин, в поиске в глубину в каждый момент исполнения алгоритма обрабатывается только одна вершина. С другой стороны, поиск в глубину не находит кратчайших путей, зато он применим в ситуациях, когда граф неизвестен целиком, а исследуется каким-то автоматизированным устройством.
Если же граф ориентированный, то поиск в глубину строит дерево путей из начальной вершины во все доступные из нее.
Обход в глубину можно представить себе следующим образом. Пусть исследователь находится в некотором лабиринте (графе) и он хочет обойти весь лабиринт (посетить все доступные вершины в графе). Исследователь находится в некоторой вершине и видит ребра, исходящие из этой вершины. Очевидная последовательность действий исследователя такая:
-
Пойти в какую-нибудь смежную вершину. -
Обойти все, что доступно из этой вершины. -
Вернуться в начальную вершину. -
Повторить алгоритм для всех остальных вершин, смежных из начальной.
Видим, что алгоритм является рекурсивным — для обхода всего графа нужно переместиться в соседнюю вершину, после чего повторить для этой вершины алгоритм обхода. Но возникает проблема зацикливания — если из вершины A можно перейти в вершину B, то из вершины B можно перейти в вершину A и рекурсия будет бесконечной. Для борьбы с рекурсией нужно применить очень простую идею — исследователь не должен идти в ту вершину, в которой он уже был раньше, то есть которая не представляет для него интерес (считаем, что интерес для исследователя представляют только вершины, в которых он не был ранее). Итак, уточненный алгоритм может выглядеть следующим образом:
-
Пойти в какую-нибудь смежную вершину, не посещенную ранее. -
Запустить из этой вершины алгоритм обхода в глубину -
Вернуться в начальную вершину. -
Повторить пункты 1-3 для всех не посещенных ранее смежных вершин.
Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку O(N+M).
-
Компоненты сильной связности
Определение. Две вершины ориентированного графа связаны сильно, если существует путь из одной в другую и наоборот. Иными словами, они обе лежат в каком-то цикле.
Понятно, что такое отношение транзитивно: если a и b сильно связны, и b и c сильно связны, то a и c тоже сильно связны. Поэтому все вершины распадаются на компоненты сильной связности — такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильной связности нет.
Самый простой пример сильно-связной компоненты — это цикл. Но это может быть и полный граф, или сложное пересечение нескольких циклов.
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать.
Мосты
Пусть дан неориентированный граф. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности). Требуется найти все мосты в заданном графе.
Неформально, эта задача ставится следующим образом: требуется найти на карте такие дороги, при удалении которых пропадает путь между какими-либо двумя точками.
Конденсация графа
Часто рассматривают граф, составленный из самих компонент сильной связности, а не индивидуальных вершин. Очевидно, такой граф уже будет ациклическим, и с ним проще работать. Задачу о сжатии каждой компоненты сильной связности в одну вершину называют конденсацией графа
-
Кратчайшие пути в графах. BFS. Dijkstra.
Оба алгоритма имеют одну и ту же общую идею. Мы начинаем с исходного узла и исследуем граф, узел за узлом. На каждом шаге мы всегда переходим к узлу, который ближе всего к исходному узлу. Первые два шага - инициализировать расстояния большим значением и добавить исходный узел в очередь. Далее мы выполняем итерации до тех пор, пока очередь не станет пустой. На каждой итерации мы извлекаем узел из очереди, который имеет наименьшее расстояние от исходного узла.
После этого мы посещаем всех соседей извлеченного узла и проверяем новое расстояние, которого нам удалось достичь. Если новое расстояние лучше старого, мы обновляем расстояние этого узла и помещаем его в очередь. Наконец, алгоритм переходит к выполнению еще одной итерации, пока очередь не опустеет.
После завершения работы алгоритма у нас будут кратчайшие пути от исходного узла ко всем остальным узлам графа.
Однако, поскольку графики либо взвешенные, либо невзвешенные, мы не можем использовать один и тот же алгоритм для обоих случаев.
Следовательно, у нас есть два алгоритма.
BFS вычисляет кратчайшие пути в невзвешенных графах
.
С другой стороны, алгоритм Дейкстры вычисляет то же самое во взвешенных графах.
Алгоритм поиска в ширину (англ. breadth-first search, BFS) позволяет найти кратчайшие пути из одной вершины невзвешенного (ориентированного или неориентированного) графа до всех остальных вершин. Под кратчайшим путем подразумевается путь, содержащий наименьшее число ребер.
При работе с невзвешенными графами мы всегда заботимся о сокращении количества посещенных ребер. Поэтому мы уверены, что все прямые соседи исходного узла имеют расстояние, равное единице. Следующее, в чем мы можем быть уверены, это то, что все вторые соседи исходного узла имеют расстояние, равное двум, и так далее.
Эта идея остается в силе до тех пор, пока мы не охватим все узлы графа. Единственное исключение - если мы достигли узла, который был посещен ранее. В этом случае мы должны игнорировать это. Причина в том, что раньше мы должны были достичь этого более коротким путем.
Стоит отметить, что во взвешенных графах, где все ребра имеют одинаковый вес, алгоритм BFS правильно вычисляет кратчайшие пути. Причина в том, что он заботится об уменьшении количества посещенных ребер, что верно в случае равных весов для всех ребер.
Поскольку мы используем обычную очередь, у нас есть O(1) сложность по времени для операций push и pop. Следовательно, общая временная сложность равна O(V + E), где V - количество вершин и E - количество ребер в графе.
Когда дело доходит до взвешенных графиков, необязательно, чтобы соседние узлы всегда имели кратчайший путь. Однако сосед с кратчайшим краем не может быть достигнут каким-либо более коротким путем. Причина в том, что все остальные ребра имеют больший вес, поэтому прохождение их в одиночку увеличило бы расстояние.
Алгоритм Дейкстры использует эту идею для создания жадного подхода. На каждом шаге мы выбираем узел с кратчайшим путем. Мы фиксируем эту стоимость и добавляем соседей этого узла в очередь. Следовательно, очередь должна иметь возможность упорядочивать узлы внутри нее на основе наименьших затрат. Мы можем рассмотреть возможность использования очереди приоритетов для достижения этой цели.
У нас все еще есть одна проблема. В невзвешенных графах, когда мы достигли узла с другого пути, мы были уверены, что в первый раз должен быть кратчайший путь. В взвешенных графиках это не всегда верно. Если мы достигли узла с более коротким путем, мы должны обновить его расстояние и добавить его в очередь.
Это означает, что один и тот же узел может быть добавлен несколько раз.
Поэтому мы всегда должны сравнивать стоимость извлеченного узла с его фактической сохраненной стоимостью. Если извлеченное расстояние больше сохраненного, это означает, что этот узел был добавлен на ранней стадии. Позже мы, должно быть, нашли более короткий путь и обновили его. Мы также снова добавили узел в очередь, поэтому это извлечение можно безопасно игнорировать.
Поскольку мы посещаем соседей каждого узла только один раз, мы посещаем ребра только один раз. Кроме того, мы можем использовать очередь приоритетов, которая имеет временную сложность O(logn) для операций push и pop. Следовательно, общая временная сложность равна O(V + E(logV)) .
-
Алгоритм Форда-Беллмана
Алгоритм Беллмана-Форда находит в ориентированном графе кратчайшие пути от исходной вершины до всех остальных. В отличие от алгоритма Дейкстры, в алгоритме Беллмана-Форда могут быть рёбра с отрицательным весом. Впрочем, если граф содержит отрицательный цикл, то, понятно, кратчайшего пути до некоторых вершин может не существовать (по причине того, что вес кратчайшего пути должен быть равен минус бесконечности); впрочем, этот алгоритм можно модифицировать, чтобы он сигнализировал о наличии цикла отрицательного веса, или даже выводил сам этот цикл.
Алгоритм носит имя двух американских учёных: Ричарда Беллмана и Лестера Форда. Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас.
Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.