Метод последовательных приближений (МПП)

Для известного приближенного решения существует метод его уточнения. Так, начиная с исходного приближенияf₀ производится последовательное уточнение решения f_1, затем уточнение решений f₂, f₃ и т.д. В результате получается последовательность приближенных решений, которые или сходятся к действительному решению, или приближаются к нему с допустимой для практики погрешностью. Здесь любой элемент последовательности может зависеть или только от предшествующего ему элемента или от всех более ранних приближений.

На основе такого метода разработки алгоритма могут решаться различные задачи:

· вычисления квадратного корня, по методу Ньютона- Рафсона;

· вычисления математических функций

· численного интегрирования.

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

Метод наискорейшего спуска (МНС)

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

Примерами алгоритмов, разработанных на основе МНС, являются алгоритмы решения задач:

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

· Нахождения кратчайшего пути в лабиринте — можно рассматривать как разновидность задачи о коммивояжере;

· формирования последовательных приближений ряд чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13, 21, 34,..., каждое из которых является суммой двух предыдущихформирования последовательностей для получения биноминальных коэффициентов.

Отличия МНС от МПП:

· в МПП за исходное берется любое приближение, которое затем улучшается, а в МНС направление каждого шага планируется так, чтобы он был направлен в сторону нужного решения;

· использование МПП при создании программ заключается в том, что, принимая какую-либо работающую программу за исходную, производится ее последовательное улучшение с помощью отладки и настройки, а МНС применяется в методах нисходящего проектирования и частично в методе пошагового уточнения.

Метод обратного прохода

Метод обратного прохода применяется при заданном порядке (направлении) решения некоторой задачи. Замена этого направления на обратное может помочь упростить задачу без ее изменения.

Метод может быть использован при решении задач:

· выдачи последовательности чисел от 1 до 10. Эта задача направлена, но не обратима, так как перемена направления этой процедуры изменит результат;

· нахождения всех простых чисел между 1 и 100. Задача направлена и обратима, но если начинать со старших чисел, то решение задачи существенно усложнится;

· поиска пути в лабиринте. Задача направлена и обратима, если не осуществляется истинный поиск в «реальном» лабиринте. Но если за исходную точку взять выход и находить путь ко входу, такая задача аналогична первоначальной.

Метод динамического программирования

Понятие метода динамического программирования связано с методом планирования многоэтапных процессов принятия решения и может рассматриваться как:

· метод математического программирования;

· метод решения задач оптимизации, представленных через последовательность этапов принятия решений.

Метод математического программирования охватывает прикладные задачи и вычислительные методы для задач оптимизации, которые формулируются как задачи максимизации или минимизации функции (целевой функции) на ограниченном множестве пространства действительных n-компонентных векторов.

Метод решения задач оптимизации представляют процесс нахождения наилучшего решения задачи, которое определяется по некоторому заранее установленному критерию.

В программировании метод оптимизации используется при разработке алгоритма генерации программы, которая наилучшим способом использует ресурсы компьютера (объем памяти, время исполнения и др.).

Три формы оптимизации:

· глобальная оптимизация — оптимизация, используемая для переупорядочивания установленной последовательности выполнения команд программы с целью исключения избыточности вычисления;

· регистровая оптимизация — оптимизация, связанная с привязкой машинных регистров памяти к переменным и промежуточным численным результатам с целью минимизации числа случаев «холостого» резервирования регистров для их загрузки в дальнейшем;

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

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