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

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

Алгоритм Флойда для нахождения циклов (англ.) — находит цикл в итерациях
Генераторы псевдослучайных чисел:
Алгоритм Робинсона-Шенстеда (англ.) — генерация перестановок из пар таблиц Юнга

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

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

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

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

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

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

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

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

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

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

Bogosort (англ.)
Блинная сортировка (англ.)
Блочная сортировка (англ.) (также известен как корзинная сортировка)
Быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Глупая сортировка (англ.)
Гномья сортировка (англ.)
Пирамидальная сортировка (Сортировка кучей) — превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (англ.)
Поразрядная сортировка — сортирует строки буква за буквой
Сортировка Бентли-Седжвика (англ. 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^{о книге}

СсылкиПравить

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