Список комбинаторных алгоритмов

Общие комбинаторные алгоритмы

•  — находит цикл в итерациях
• Генераторы псевдослучайных чисел:
  • Алгоритм Блюма, Блюма и Шуба
  • Вихрь Мерсенна
  • Метод Фибоначчи с запаздываниями
  • Линейный конгруэнтный метод
•  — генерация перестановок из пар таблиц Юнга

Алгоритмы на графах

• Алгоритм Беллмана-Форда — вычисляет кратчайший путь во взвешенном графе (где некоторые веса рёбер могут быть отрицательны)
•  — находит минимальное остовное дерево в графе
• Алгоритм Варшалла — вычисляет все кратчайшие пути во взвешенном графе
• Алгоритм Дейкстры — вычисляет кратчайший путь в графе с неотрицательными весами рёбер
• Алгоритм Краскала — находит остовный лес минимального веса в графе
• — алгоритм для рисования графа
• Алгоритм Прима — находит остовное дерево минимального веса в связном графе
• — решает проблему нахождения всех пар кратчайших путей во взвешенном направленном графе
• — вычисляет максимальный поток в графе
•  — модификация алгоритма Форда-Фалкерсона
• Метод ближайшего соседа
• Неблокирующий минимальный охватывающий переключатель например, для телефонной связи

Алгоритмы поиска

•  — модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке;
•  — использует бинарное дерево для хранения элементов;
• Двоичный поиск — находит элемент в отсортированном списке
• Интерполирующий поиск (Предсказывающий поиск, Поиск по словарю)
• Линейный поиск — находит элемент в неотсортированном списке
• Поиск в глубину — проходит граф ветка за веткой
• Поиск в ширину — проходит граф уровень за уровнем
• (англ. Best-first search)— проходит граф в порядке важности, используя очередь приоритетов
• — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
• — находит элемент в отсортированном списке
• Поиск в хеш-таблице

Алгоритмы на строках

Алгоритмы поиска строки

• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Рабина-Карпа поиска строки
• (также известен как shift-or, shift-and или Baeza-Yates-Gonnet алгоритм)
• Задача поиска наибольшей общей подпоследовательности
• Задача поиска наибольшей общей подстроки

Примерное соответствие

• Расстояние Левенштейна
• Расстояние Хэмминга
• Soundex

Деревья для строковых последовательностей

• Суффиксное дерево
• Алгоритм Мак-Крейта
• Алгоритм Укконена
• Алгоритм Фрача
• Суффиксные массивы

Алгоритмы сортировки

• (также известен как корзинная сортировка)
• Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
• Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
• Поразрядная сортировка — сортирует строки буква за буквой
• Сортировка Бентли-Седжвика (англ. BeSe sort) — модификация быстрой сортировки для составных ключей, заключающаяся в делении не пополам, а на три части — в третью попадают одинаковые (по текущему символу) ключи
• Сортировка бинарным деревом
• Сортировка методом вставок — определяем, где текущий элемент должен находится в отсортированном списке, и вставляем его туда
• Сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
• Сортировка методом Шелла— попытка улучшить сортировку вставками
• Сортировка перемешиванием (Сортировка коктейлем)
• Сортировка подсчётом
• Сортировка пузырьком
• Сортировка слиянием — сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
• Хитрая сортировка — извлекает из исходной последовательности отсортированные подпоследовательности, производя их слияние с уже извлечёнными данными
• Цифровая сортировка (Сортировка по отделениям)

Алгоритмы слияния

• Простой алгоритм слияния (англ. Simple Merge algorithm)
• К-мерный алгоритм слияния (англ. k-way Merge algorithm)

Литература

• Дональд Кнут . Искусство программирования, том 4, выпуск 4. Генерация всех деревьев. История комбинаторной генерации = The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees -- History of Combinatorial Generation. — М.: «Вильямс», 2007. — С. 160. — ISBN 0-321-33570-8.

Ссылки

• Алгоритмы, методы, исходники