Этот алгоритм находит кратчайшее расстояние до какой-либо точки при конкретных условиях. Все действие разворачивается в сети с узлами и дугами. Они имеют свой вес, влияющий на поиск кратчайшего пути в процессе работы алгоритма.
Поворот бинарного дерева происходит во многих алгоритмах. Зачастую это дерево поиска, в котором при смещении узлов их порядок относительно корневого элемента всегда остается неизменным. Значения слева должны быть не больше, а справа не меньше, чем корневой элемент.
Когда речь заходит о поиске, это означает, что понадобится граф. В данном случае используется произвольный граф, муравьи и феромоны (направление движения по графу). После каждого прохода алгоритма муравьи будут находить кратчайшие пути в графе, следуя по феромонам.
В этом видеоуроке автор расскажет, как работают алгоритмы сортировки, и как можно отсортировать любой список. Для понимания процесса будет рассмотрено два подхода. В первом подходе вычисляется большее значение и меняется местами с меньшим, а во втором упор сделан на вставку элементов в список слева или справа.
Данный вид сортировки – самый простой способ отсортировать массив. В качестве примера дан массив из четырех чисел, сортируемых парами. Если одно из чисел больше – они меняются местами.
Этот видеоурок описывает первый из трех способов оптимизации пузырька. В данном подходе оптимизируется длина пузырька путем сокращения ненужных сравнений, когда заведомо известно, что числа с максимальными значениями уже на своих местах.
Второй подход оптимизации заключается в том, что не всегда обязательно выполнять все возможные проходы в сортировке (пузырьки). Это может понадобиться, если массив уже почти отсортирован или добавляются новые элементы.
Это третий и последний способ оптимизации пузырьковой сортировки, достаточно сложный в реализации, поэтому используется очень редко. Он заключается в том, чтобы изменить направление пузырька после первого прохода, что позволяет значительно сэкономить время сортировки.
Видеокурс по алгоритмам продолжает урок о том, как применить в бинарном поиске различные виды деревьев. Бинарное дерево – это дерево, в котором у каждого узла может быть не более двух дочерних нод. У данного дерева есть “модификация” – сортированное бинарное дерево. В таком дереве значения левой части узлов меньше или равны, а слева больше или равны, чем значение корневой ноды.
Данный вид деревьев не имеет ничего общего с бинарными деревьями, т. к. они всегда жестко сбалансированы. Каждый узел такого дерева может содержать в себе более чем одно значение. Максимальное количество значений в B-дереве обычно обозначается отдельным параметром c буквой М.
Для того чтобы данная информация была понятна в полной мере, необходимо четко представлять, что такое массивы и как они устроены. В этом видеоуроке рассматриваются плюсы и минусы использования связанных списков.
Алгоритм Флойда – это алгоритм поиска кратчайшего пути из одного в другой узел графа. Он очень похож на алгоритм Дейкстры, но с одним большим отличием – позволяет искать сразу множество кратчайших путей через все ноды.
Самый простой алгоритм гномьей сортировки подразумевает, что сравниваются две ближайшие ячейки. Если при сравнении двух соседних ячеек массива оказалось, что значения идут не по порядку, они меняются местами и итерация возвращается на шаг назад для очередного сравнения.
Видеокурс по алгоритмам включает в себя простой, но интересный алгоритм: алгоритм перемешивания.
Данный способ сортировки очень похож на пузырьковую сортировку, но есть небольшое отличие: прогон начинается с первого элемента и идет до конца списка. После этого возвращается назад с предпоследнего элемента к первому. Следующая итерация – со второго к предпоследнему и т. д.
Данный алгоритм поиска обычно используется в компьютерных играх для быстрого нахождения кратчайшего пути при помощи эвристической функции А-звезда.
Завершает видеокурс по алгоритмам ролик, в котором автор разбирает решение задачи коммивояжера при помощи алгоритма муравьев. Программный код реализован на C++.