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

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

Сведение задачи к самой себе (рекурсия)

    Задача также, как и в предыдущем методе сводится к более простой. Но эта более простая задача имеет ту же формулировку, что и исходная, с той лишь разницей, что решаться она должна для более простых исходных данных. Это чистый вариант упрощения исходных данных.

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

    Сначала каким-либо образом угадывается значение x0, близкое к решению. Задача P нахождения решения сводится к многократному решению задачи R улучшения решения. Метод предполагает, что каким-то образом может быть оценено "качество" решения (обычно - точность). Чаще всего абсолютная точность недостижима, поэтому процесс потенциально бесконечен, т. е. не выполняется свойство финитности алгоритма. Для того чтобы этого избежать, несколько изменяют первоначальную формулировку задачи: требуют отыскать не точное решение Y, а любое решение, отличающееся от Y не более чем на некоторую величину ε - т.е. приближенное решение. Характерный пример - задача отыскания корня уравнения или задача отыскания корня p-й степени из x.

    Основной проблемой является построение задачи R по исходной задаче P, доказательство факта сходимости процесса к искомому решению и обеспечение достаточно высокой скорости сходимости.

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

    На следующем шаге мы рассмотрим решение обратной задачи и метод полного перебора.




Предыдущий шаг Содержание Следующий шаг