Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

4 </li>

5 <li>MergeSort - алгоритм "разделяй и властвуй", который рекурсивно делит массив пополам, сортирует половинки, а затем объединяет их обратно.

6 </li>

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

8 </li>

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

10 </li>

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

12 </li>

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

14 </li>

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

16 </li>

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

18 </li>

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

20 </li>

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

22 </li>

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

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

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

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

27 <h3>Поехали! 🚀</h3>

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

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

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

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

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

33 Детальное объяснение можете найти<a>тут</a>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48 Рассмотрим, как вычисляется значение 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].

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

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

51 <h3>На этом все!</h3>

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