10 алгоритмов для программистов, которые упрощают нам работу. Часть 2
2026-02-26 20:41 Diff
https://ru.hexlet.io/blog/posts/10-algoritmov-dlya-programmistov-kotorye-uproschayut-im-rabotu-chast-2

В этой статье я хотел бы представить свой топ-10 алгоритмов, которые могут помочь вам в работе. Бонусом покажу на примерах, как ими пользоваться.

Сам список включает в себя следующие алгоритмы:

  1. QuickSort - алгоритм разделения и покорения, который рекурсивно разбивает массив на более мелкие подмассивы и сортирует их.

  2. MergeSort — алгоритм «разделяй и властвуй», который рекурсивно делит массив пополам, сортирует половинки, а затем объединяет их обратно.

  3. Бинарный поиск - алгоритм поиска, который многократно делит интервал поиска пополам, ища определенное значение в отсортированном массиве.

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

  5. Breadth-first Search (BFS) — алгоритм обхода графа, который исследует все вершины графа или все узлы дерева уровень за уровнем.

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

  7. Алгоритм Беллмана-Форда — алгоритм кратчайшего пути с одним источником, который также может обнаруживать отрицательные циклы в графе.

  8. Алгоритм Дейкстры — алгоритм кратчайшего пути с одним источником, который работает путем многократного ослабления оценок расстояния между вершинами.

  9. Алгоритм поиска A* - алгоритм поиска, который использует эвристику для направления поиска и обычно используется для поиска пути и решения задач обхода графа.

  10. Knapsack Problem — задача комбинаторной оптимизации, целью которой является максимизация общей стоимости предметов в рюкзаке без превышения его вместимости.

Для примерах реализации я буду использовать Typescript, так как это ЯП с сильной типизацией, но в тоже время достаточно простой для понимания.

Заметка: все вышеперечисленные алгоритмы реализованы с помощью Typescript и могут быть найдены в менеджере пакетов npm.

Реализацию QuickSort, MergeSort, Бинарного поиска, Поиска в глубину (DFS) мы можете найти в первой части.

Сегодня мы разберем Breadth-first Search (BFS), Динамическое программирование и Алгоритм Беллмана-Форда

Поехали! 🚀

Пример алгоритма поиска в ширину (BFS), реализованного на TypeScript:

Данная реализация BFS использует представление графа в виде списка смежности, где каждая вершина представлена ключом в карте, а ее значение — массив соседних вершин.

Функция bfs начинает работу с инициализации очереди, добавления в нее начальной вершины и пометки ее как посещенной. Затем с помощью цикла while выполняется итерация по очереди, удаление первой вершины, ее печать, добавление в очередь всех ее непосещенных соседей и пометка их как посещенных.

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

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

Детальное объяснение можете найти тут

Динамическое программирование

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

Существует две основные техники, используемые в динамическом программировании:

— Мемоизация: Этот метод предполагает хранение решений подпроблем в кэше или таблице, чтобы их можно было использовать в дальнейшем. — Табулирование: Эта техника предполагает заполнение таблицы снизу вверх, начиная с наименьших подпроблем и доводя до окончательного решения.

Вот пример использования динамического программирования для решения проблемы последовательности Фибоначчи:

В этом примере функция fibonacci принимает на вход число n и массив memo и возвращает n-е число последовательности Фибоначчи, используя мемоизацию. Функция проверяет, хранится ли уже результат для текущего n в массиве memo, если да, то возвращает его, в противном случае вычисляет результат путем сложения результатов (n-1)-го и (n-2)-го чисел Фибоначчи и сохраняет его в массиве memo для дальнейшего использования.

Этот подход имеет временную сложность O(n), поскольку мы вычисляем каждое число последовательности Фибоначчи только один раз и можем повторно использовать результаты предыдущих вычислений.

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

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

Алгоритм Форда-Беллмана позволяет найти кратчайшие пути из одной вершины графа до всех остальных, даже для графов, в которых веса ребер могут быть отрицательными. Тем не менее, в графе не должно быть циклов отрицательного веса, достижимых из начальной вершины, иначе вопрос о кратчайших путях является бессмысленным. При этом алгоритм Форда-Беллмана позволяет определить наличие циклов отрицательного веса, достижимых из начальной вершины.

Алгоритм Форда-Беллмана использует динамическое программирование. Введем функцию динамического программирования:

— F[k][i] — длина кратчайшего пути из начальной вершины до вершины i, содержащего не более k ребер.

Начальные значения зададим для случая k=0. В этом случае F[0][start] = 0, а для всех остальных вершин i F[0][i] = INF, то есть путь, состоящий из нуля ребер существует только от вершины start до вершины start, а до остальных вершин пути из нуля ребер не существует, что будем отмечать значением INF.

Далее будем вычислять значения функции F увеличивая число ребер в пути k, то есть вычислим кратчайшие пути, содержащие не более 1 ребра, кратчайшие пути, содержащие не более 2 ребер и т. д. Если в графе нет циклов отрицательного веса, то кратчайший путь между любыми двумя вершинами содержит не более ребра ( - число вершин в графе), поэтому нужно вычислить значения F[n-1][i], которые и будут длинами кратчайших путей от вершины start до вершины i).

Рассмотрим, как вычисляется значение F[k][i]. Пусть есть кратчайший маршрут из вершины start до вершины i, содержащий не более k ребер. Пусть последнее ребро этого маршрута есть ребро j-i. Тогда путь до вершины j содержит не более k-1 ребра и является кратчайшим путем из всех таких путей, значит, его длина равна F[k-1][j], а длина пути до вершины i равна F[k-1][j] + W[j][i], где W[j][i] есть вес ребра j-i. Дальше необходимо перебрать все вершины j, которые могут выступать в качестве предыдущих, и выбрать минимальное значение F[k-1][j] + W[j][i].

Получаем следующий алгоритм:

Реализацию на других языках можно найти тут и тут

На этом все!

Спасибо за ваше внимание. В следующей части реализуем такие алгоритмы как Knapsack Problem и Алгоритм поиска A*.