Алгоритм А*

Используется для поиска кратчайшего пути. A* сочетает в себе элементы алгоритма Дейкстры и жадного поиска по принципу «наилучшее первое» для поиска оптимального пути с учетом предполагаемой стоимости.

Ключевые идеи:
⁃ Эвристическая функция h(n):
Оценивает стоимость от текущего узла до цели. Эвристика помогает эффективно направлять поиск к цели.
⁃ Функция стоимости g(n):
Представляет фактическую стоимость от начального узла до текущего узла.
⁃ Общая стоимость f(n):
представляет собой сумму функции стоимости и эвристики: f(n) = g(n) + h(n).

Временная сложность алгоритма A* зависит от эвристики. В худшем случае, число вершин, исследуемых алгоритмом, растёт экспоненциально по сравнению с длиной оптимального пути, но сложность становится полиномиальной, когда эвристика удовлетворяет следующему условию:
| h(n) - h*(n) | <= O (log h*(x))
где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели.

Алгоритм Беллмана-Форда

Широко используемый алгоритм в теории графов и сетевом анализе. Он используется для поиска кратчайшего пути от одной исходной вершины ко всем остальным вершинам взвешенного графа, даже если граф содержит ребра с отрицательным весом.

Ключевые идеи:

⁃ Кратчайший путь из одного источника.
Беллман-Форд фокусируется на поиске кратчайшего пути от исходной вершины ко всем остальным вершинам графа.
⁃ Ребра с отрицательным весом.
В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда может обрабатывать графы с ребрами с отрицательным весом. Однако он не может обрабатывать графы с отрицательными весовыми циклами.
⁃ Релаксация
Основная операция Беллмана-Форда – это релаксация. Алгоритм итеративно улучшает расчетное расстояние до вершин, учитывая все ребра.

Сложность: O(V*E)

Алгоритм Прима

Алгоритм в теории графов для поиска минимального остовного дерева (MST) связного неориентированного графа с взвешенными ребрами.

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

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST). Выберите произвольную начальную вершину (обычно первую) и добавьте ее в MST.
2. Пока MST содержит менее V вершин: Определите ребро минимального веса, которое соединяет вершину в MST с вершиной вне MST и добавьте в MST вершину, соединенную выбранным ребром, вместе с самим ребром.
3. Продолжайте процесс выбора ребер, пока MST не будет содержать все вершины V.
4. Алгоритм завершен, когда MST содержит все вершины исходного графа.

Сложность: O(E + V log V)

Алгоритм Краскала

Алгоритм в теории графов для поиска минимального остовного дерева (MST) связного неориентированного графа с взвешенными ребрами. Он начинает с пустого дерева и неоднократно добавляет к нему ребра, гарантируя при этом отсутствие циклов.

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST).
2. Отсортируйте все ребра графа в порядке возрастания веса.
3. Для каждого ребра проверьте, не приведет ли его добавление к MST к созданию цикла. Обычно это делается с использованием структуры данных с непересекающимися наборами. Если добавление ребра не образует цикл, добавьте его в MST.
4. Продолжайте процесс выбора ребер до тех пор, пока MST не будет содержать все вершины или пока не будут рассмотрены все ребра.
5. Алгоритм считается завершенным, когда MST содержит все вершины или когда все ребра учтены.

Сложность: O(E log E)

Алгоритм Борувки

Алгоритм для поиска минимального остовного дерева в неориентированном взвешенном графе. Он был разработан Йозефом Борувкой в 1926 году и является одним из первых оптимальных алгоритмов для этой задачи.

Алгоритм:
1. Начинаем с произвольного узла графа и инициализируем каждую компоненту связности как отдельное дерево.
2. На каждой итерации алгоритма просматриваем все ребра графа:
- Для каждой компоненты связности выбираем ребро минимального веса, которое соединяет ее с другой компонентой связности.
- Объединяем две компоненты связности в одну, используя выбранное минимальное ребро.
3. Повторяем шаг 2 до тех пор, пока не останется только одна компонента связности.

Сложность: O(E log V)

Алгоритм Миллера-Рабина

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

Алгоритм:
1. Представьте число n в виде n-1 = 2^s * d, где d нечетное.
2. Выберите случайное целое число a в интервале [2, n-2].
3. Вычислите a^d mod n.
4. Если (a^d) mod n = 1 или (a^d) mod n = n-1, перейдите к следующему шагу.
5. Для i от 1 до s-1:
- Вычислите (a^(2^i * d)) mod n.
- Если (a^(2^i * d)) mod n = n-1, перейдите к следующему шагу.
- Если (a^(2^i * d)) mod n = 1, то число n является составным.
6. Если ни в одном из шагов выше не было обнаружено свидетелей простоты, то число n с высокой вероятностью является простым. В противном случае, число n является составным.

Сложность: O(k * log^3(n))

Алгоритм обратного удаления

Тесно связан с алгоритмом Краскала.

В этом алгоритме мы сортируем все ребра в порядке убывания их весов. После сортировки поочередно выбираем ребра в порядке убывания. Мы включаем текущее выбранное ребро, если исключение текущего ребра приводит к отключению в текущем графе. Основная идея — удалить ребро, если его удаление не приводит к отключению графа.

Алгоритм:
1. Отсортируйте все ребра графа в порядке невозрастания весов ребер.
2. Инициализируйте MST как исходный граф и удалите лишние ребра, используя шаг 3.
3. Выберите ребро с наибольшим весом из оставшихся ребер и проверьте, разъединяет ли удаление ребра граф или нет. Если отключается, то ребро не удаляем. В противном случае мы удаляем край и продолжаем.

Сложность: O((E*(V+E)) + E log E)

Алгоритм Флойда — Уоршелла

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

Алгоритм:
1. Создайте матрицу для хранения кратчайших расстояний между всеми парами вершин и инициализируйте ее.
2. Каждую вершину графа рассматривайте как промежуточную вершину пути.
3. Обновите матрицу, учитывая, приводит ли использование промежуточной вершины к более короткому пути между любой парой вершин.
- Для каждой пары вершин (i, j) рассмотрим все вершины (k) как потенциальные промежуточные звенья:
- Если путь от вершины i до j через вершину k короче текущего расстояния от i до j, обновите расстояние в матрице.
4. Продолжайте, пока не будут рассмотрены все пары вершин.

Сложность: O(V^3)

Топологическая сортировка

Алгоритм, используемый для линейного упорядочения вершин ориентированного ациклического графа таким образом, что для каждого направленного ребра (u, v) вершина u предшествует вершине v в линейном порядке.

1. Инициализировать место, где вы будете хранить отсортированные вершины.
2. Выберите любую вершину без входящих ребер в качестве отправной точки.
3. Пока в графе есть необработанные вершины: Выберите вершину (v), у которой нет входящих ребер (степень 0), и удалите ее из графа. Добавьте вершину v в конец линейного порядка. Обновить степени соседних вершин (уменьшить на 1), поскольку вершина v была удалена.
4. Продолжайте шаг итерации, пока все вершины не будут обработаны.

Сложность: O(V + E)

Кодирование длин серий (Run-Length Encoding, RLE)

Метод сжатия данных, который основан на замене повторяющихся последовательностей символов кодом, состоящим из символа и длины этой последовательности.

Алгоритм:
1. Читаем символы исходной строки один за другим.
2. Если текущий символ повторяется, увеличиваем счетчик повторений.
3. Если текущий символ отличается от предыдущего или достигнут максимальный предел длины серии, записываем в выходной поток код, состоящий из повторяющегося символа и длины серии.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Завершаем сжатие.

Сложность алгоритма зависит от размера исходной строки и количества повторяющихся символов. В худшем случае сложность: O(n^2), где n - размер строки.

Алгоритм LZW

Метод без потерь для сжатия данных, который основан на построении и использовании словаря. Он был разработан Терри Велчем в 1984 году.

Алгоритм:
1. Создаем словарь, содержащий начальный набор символов (обычно это все возможные символы, например, ASCII).
2. Читаем символы исходной строки один за другим.
3. Проверяем, есть ли текущая последовательность символов в словаре:
а. Если да, добавляем текущий символ к последовательности.
б. Если нет, записываем индекс текущей последовательности в выходной поток и добавляем новую запись в словарь с текущей последовательностью символов.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Записываем последний индекс в выходной поток.
6. Завершаем сжатие.

Сложность алгоритма LZW зависит от размера исходной строки и размера словаря. В худшем случае: O(n^2), где n - размер строки.

Алгоритм Кнута-Морриса-Пратта

Алгоритм для поиска всех вхождений шаблона в тексте.

1. Создайте массив префиксов (также известный как LPS — самый длинный суффикс префикса), который поможет избежать ненужных сравнений на этапе поиска.
2. Начните сопоставлять шаблон с текстом с самого начала. Используйте два указателя: «i» и «j», чтобы отслеживать позиции.
3. Продолжайте поиск шаблона в тексте, обновляя i и j по мере необходимости.

Алгоритм выводит позиции всех вхождений шаблона в текст.

Сложность: O(N + M)

Алгоритм Рабина-Карпа

Алгоритм поиска строки в тексте, использующий хэш-функции для эффективного сравнения подстроки с искомой строкой.

Алгоритм:
1. Вычисляем хэш-функцию для искомой строки.
2. Вычисляем хэш-функцию для первой подстроки текста, длиной равной длине искомой строки.
3. Если хэш-значения совпадают, сравниваем каждый символ искомой строки с соответствующим символом подстроки текста. Если все символы совпадают, значит, мы нашли вхождение искомой строки.
4. Если хэш-значения не совпадают, перемещаем окно подстроки текста на один символ вправо и повторяем шаг 3 до конца текста.
5. Если мы достигли конца текста и не нашли вхождений искомой строки, значит, она отсутствует в тексте.

Сложность: O(n + m), где n - длина текста, а m - длина искомой строки. Однако, в худшем случае: O(n * m).

Алгоритм Бойера-Мура

Алгоритм поиска подстроки в строке. Он основан на идее использования информации о самом шаблоне для пропуска большого количества символов в тексте во время поиска.

Алгоритм:
1. Построение таблицы смещений.
2. Начинаем сравнивать символы шаблона и текста справа налево.
-Если символы совпадают, продолжаем сравнивать следующие пары символов.
-Если символы не совпадают, используем таблицу смещений для определения максимального смещения.
3. В случае неполного совпадения переносим шаблон на максимальное смещение по таблице смещений.
4. Повторяем шаги 2 и 3 до тех пор, пока не найдется полное совпадение или не достигнем конца текста.

Сложность: O(n/m)

Алгоритм Форда — Фалкерсона

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

Алгоритм:
1. Инициализируем максимальный поток равным нулю.
2. Пока существует дополняющий путь в остаточной сети:
- Находим дополняющий путь с помощью любого подходящего алгоритма поиска в глубину или поиска в ширину.
- Находим минимальную пропускную способность на этом пути.
- Увеличиваем поток вдоль этого пути на минимальную пропускную способность.
- Обновляем остаточную сеть, уменьшая пропускные способности на прямых ребрах и увеличивая на обратных ребрах.
3. Возвращаем полученный максимальный поток.

Сложность: O(E*V^2)

Алгоритм Хопкрофта-Карпа

Алгоритм для поиска максимального паросочетания в двудольных графах.

Алгоритм:
1. Создаем пустое паросочетание и расстояния для каждой вершины, устанавливая их в бесконечность.
2. Используем алгоритм поиска в ширину (BFS) для поиска кратчайших путей от ненасыщенных вершин левой доли к ненасыщенным вершинам правой доли. Обозначим полученные расстояния как d[v], где v - вершина.
3. Запускаем глубинный поиск (DFS) из каждой ненасыщенной вершины левой доли. В ходе DFS осуществляем насыщение вершин в паросочетание, улучшаем текущее паросочетание и снижаем расстояния для каждой рассматриваемой вершины.
4. Повторение до насыщения. Повторяем шаги 2 и 3 до тех пор, пока больше нет насыщенных вершин в правой доле.

Сложность: O(E * sqrt(V))

Наивный алгоритм поиска по шаблону

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

Алгоритм:
1. Начинаем с позиции 0 в тексте.
2. Перебираем все позиции от 0 до (длина текста - длина шаблона):
- Сравниваем каждый символ шаблона с соответствующим символом текста в текущей позиции.
- Если все символы шаблона совпадают с символами текста, считаем это вхождением шаблона и записываем позицию.
3. Переходим к следующей позиции в тексте и повторяем шаг 2.
4. Возвращаем список всех позиций, где найдены вхождения шаблона.

Сложность: O((n-m+1) * m)
длина текста (n) и длина шаблона (m)

Алгоритм Тарьяна

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

Алгоритм:
1. Начните с произвольной вершины в графе.
2. Пройдитесь по всем смежным вершинам текущей вершины и рекурсивно вызовите алгоритм для каждой непосещенной вершины.
3. Определите минимальное из времени обхода (lowlink) для вершины.
4. Если текущая вершина имеет минимальное время обхода равное времени обхода, то все вершины, которые достижимы из текущей вершины, являются сильно связной компонентой.
5. После поиска и обработки всех вершин в компоненте, вернитесь на вершину, из которой начался поиск и продолжите смежными вершинами для поиска других компонент.

Сложность: O(|V| + |E|)

Алгоритм Косараджу (Косарайю)

Алгоритм, используемый для определения сильно связных компонент в ориентированном графе.

Алгоритм:
1. Начните с произвольной вершины в графе и выполните обход в глубину, отмечая каждую вершину временным меткой времени первого прохода.
2. Перейдите к обратному графу (поменяйте направление всех ребер).
3. Сортируйте вершины в порядке убывания их временной метки первого прохода.
4. Снова выполните обход в глубину, но на этот раз в порядке отсортированных вершин.
5. Каждый получившийся обход в глубину будет формировать сильно связную компоненту.

Сложность: O(|V| + |E|)

Алгоритм Ахо-Корасика

Алгоритм для множественного поиска подстрок в заданном тексте.

Алгоритм:
1. Построение бора (trie) для множества шаблонов (подстрок, которые необходимо найти).
2. Добавление суффиксных ссылок в каждую вершину бора, чтобы обрабатывать несовпадающие префиксы.
3. Присвоение каждой вершине бора "выходных ссылок" в другую вершину с шаблоном, совпадающим с префиксом подстроки из этой вершины.
4. Поиск в тексте: сначала вы начинаете с корневой вершины бора и последовательно проходите по символам текста.
-Если символ не соответствует ни одной исходящей ребру из текущей вершины, вы переходим на суффиксную ссылку и повторяете этот шаг.
-Если символ совпадает с шаблоном в следующей вершине, то удачное совпадение, и вы переходите к следующей вершине.
-Если вы достигли конечной вершины, значит, вы нашли одно из искомых шаблонов.

Сложность: O(n + m + z), где n – длина текста, m – суммарная длина всех шаблонов и z – количество найденных совпадений.