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

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

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

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

Программирование с отходом назад(Backtracking)

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

Перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно. Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

|X[1]-1| + |X[2]-2| + ... + |X[k]-k|

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).

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

X[1],...,X[N],

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.

Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:

procedure Backtracking(k);

begin

for (y in A[k]) do

if P(X[1],...,X[k-1],y) then

begin

X[k]:=y;

if k=N then {X[1],...,X[N] -решение}

Backtracking(k+1)

end

end;