Методы разработки алгоритмов.

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

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

Динамическое программирование - способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.

Метод подъема:

Этот метод, как и предыдущий, можно отнести к одному из общих «рецептов» разработки алгоритмов. Его суть заключается в следующей процедуре: алгоритм начинается с принятия начального предположения или построения начального решения задачи. Затем начинается (насколько возможно) быстрое движение «вверх» от начального уровня по направлению к лучшим решениям. Когда алгоритм достигает точки, из которой больше невозможно двигаться «наверх», он останавливается. Такой метод применяется, например, в задачах поиска экстремумов (максимумов и минимумов) среди некоторой совокупности числовых данных. Начальное решение можно сформулировать так: пусть экстремальным значением является значение первого элемента из заданной совокупности данных. Лучшим решением по отношению к начальному является такой элемент совокупности, у которого значение больше ( в случае поиска максимума) или меньше (в случае поиска минимума) по отношению к начальному значению или к промежуточному “лучшему” решению. Критерием окончания алгоритма (точкой из которой больше невозможно двигаться “наверх”) является просмотр всех элементов из заданной совокупности.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.