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