Алгоритмы — это однозначные шаги, которые должны дать нам четко определенный вывод, обрабатывая ноль или более входных данных. Это приводит ко многим подходам при разработке и написании алгоритмов. Было отмечено, что большинство алгоритмов можно классифицировать по следующим категориям.
Жадные алгоритмы
Жадные алгоритмы пытаются найти локализованное оптимальное решение, которое в конечном итоге может привести к глобально оптимизированным решениям. Однако, как правило, жадные алгоритмы не обеспечивают глобально оптимизированных решений.
Таким образом, жадные алгоритмы ищут простое решение на данный момент без учета того, как это повлияет на будущие шаги. Это похоже на то, как люди решают проблемы, не вдаваясь в подробности предоставленных данных.
Большинство сетевых алгоритмов используют жадный подход. Вот список немногих из них —
- Задача коммивояжера
- Алгоритм минимального связующего дерева Прима
- Алгоритм минимального связующего дерева Крускала
- Алгоритм минимального связующего дерева Дейкстры
Разделяй и властвуй
Этот класс алгоритмов включает в себя разделение данной проблемы на более мелкие подзадачи и последующее решение каждой из подзадач независимо. Когда проблема не может быть разделена далее, мы начинаем объединять решение каждой из подзадач, чтобы прийти к решению для более крупной проблемы.
Важные примеры алгоритмов «разделяй и властвуй»:
- Сортировка слиянием
- Быстрая сортировка
- Алгоритм минимального связующего дерева Крускала
- Бинарный поиск
Динамическое программирование
Динамическое программирование включает в себя деление более крупной проблемы на более мелкие, но в отличие от «разделяй и властвуй», оно не предполагает решения каждой подзадачи независимо. Скорее, результаты меньших подзадач запоминаются и используются для аналогичных или перекрывающихся подзадач. В основном, эти алгоритмы используются для оптимизации. Прежде чем решить подзадачу, находящуюся в руках, динамический алгоритм попытается изучить результаты ранее решенных подзадач.
Динамические алгоритмы мотивированы для общей оптимизации задачи, а не локальной оптимизации.
Важными примерами алгоритмов динамического программирования являются —