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

Розкладання завдання в послідовність різнорідних підзадач

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

Цей метод називають іноді методом "розділяй і володарюй".

У цьому методі зазвичай виділяється відносно невелике число підзадач. Наприклад: завдання - виконати програму на ЕОМ; підзадачі - ввести початковий текст програми; транслювати програму в машинні команди; приєднати до машинного коду стандартні процедури з бібліотеки; завантажити програму в оперативну пам'ять; запустити про-цесс виконання; завершити процес виконання програми.

Результати рішення першої підзадачі стають початковими даними для другої підзадачі і т. д. Таким чином, тут використаний другий підхід в чистому вигляді - декомпозиція функції, завдання її суперпозицією простіших. Помітимо також, що така суперпозиція може бути задана послідовним з'єднанням машин Т'юринга.

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

Розкладання завдання в послідовність однорідних підзадач (ітерація)

Важливий окремий випадок попереднього методу, що придбаває, однак, нова якість за рахунок того, що завдання P зводиться до n екземплярів більш простого завдання R і до простого завдання Q, що об'єднує n рішень.

Дуже простий приклад: обчислення скалярного твору двох векторів A і B:

S:=0; {Завдання Q - підготовка місця для підсумовування.}

for i:= 1 to n do_

S:=S+A[i]*B[i]; {Завдання R - перемножування компонент і сумування.}

Цей алгоритм використовує розбиття початкових даних на частини - окремі компоненти векторів.

Однорідність підзадач дозволяє значно скоротити довжину тексту алгоритму за рахунок застосування операторів повторення. Ітерація на рівні великих підзадач або окремих невеликих операторів зустрічається у більшості реальних алгоритмів і служить основним джерелом ефективного використання комп'ютера в порівнянні з іншими обчислювальними засобами (наприклад, непрограмованим калькулятором).

Зведення завдання до самої собі (рекурсія)

Завдання також, як і в попередньому методі зводиться до більше за просту. Але це простіше завдання має те ж формулювання, що і початкова, з тією лише різницею, що вирішуватися вона повинна для простіших початкових даних. Це чистий варіант спрощення початкових даних.

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

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

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

Дата добавления: 2014-11-08