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

Кожний хто займається розробкою алгоритмів, повинний опанувати деякі основні методи і поняття. Усім нам колись уперше довелося зіштовхнутися з важкою задачею і поставити запитання: з чого почати? Один з можливих шляхів – переглянути свій запас загальних алгоритмічних методів для того, щоб перевірити, чи не можна за допомогою одного з них сформулювати рішення однієї задачі. Ціль цього параграфа - коротко охарактеризувати кілька фундаментальних методів розробки алгоритмів і розвязків задач.

2.5.1. Методи приватних цілей, підйому і відпрацювання назад

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

Цей метод виглядає дуже розумно. Але, як і більшість загальних методів розвязку задач чи розробки алгоритмів, його не завжди легко перенести на конкретну задачу. Осмислений вибір більш простих задач – скоріше справа мистецтва чи інтуїції, ніж науки. Більш того, не існує загального набору правил для визначення класу задач, які можна вирішити за допомогою такого підходу. Міркування над будь-якою конкретною задачею починається з постановки задачі. Приватні цілі можуть бути встановлені, коли ми одержимо відповіді на наступні питання:

1. Чи можемо ми розвязати частину задачі? Чи можна ігноруючи деякі умови, розвязати частину задачі, що залишилася?

2. Чи можемо ми розвязати задачу для окремих випадків? Чи можна розробити алгоритм, що дає розвязок, що задовольняє всім умовам задачі, але вхідні дані якого обмежені деякою підмножиною усіх вхідних даних.

3. Чи є щось, що відноситься до задачі, що ми не досить добре зрозуміли? Якщо спробувати глибше вникнути в деякі особливості задачі, чи зможемо ми щось довідатися, що допоможе нам підійти до розвязку?

4. Чи зустрічалися Ви зі схожою задачею, розвязок якої відомо? Чи можна видозмінити її розвязок для розвязку нашої задачі? Чи можливо, що ця задача еквівалентна відомій, невирішеній задачі?

Другий метод розробки алгоритмів відомий як метод підйому. Алгоритм підйому починається з прийняття початкового припущення чи обчислення початкового рішення задачі. Потім починається наскільки можливо швидкий рух «нагору» від початкового розвязку в напрямку до кращих розвязків. Коли алгоритм досягає такої точки, з якої більше неможливо рухатися нагору, алгоритм зупиняється. На жаль, не завжди можна гарантувати, що остаточний розвязок, отриманий за допомогою алгоритму підйому, буде оптимальним. Цей «дефект» часто обмежує застосування методу підйому. Назва «підйом» частково походить від алгоритму знаходження максимумів функцій декількох змінних.

Узагалі методи підйому є «грубими». Вони запам'ятовують деяку мету і намагаються зробити усе, що можуть і де можуть, щоб підійти ближче до мети. Це робить їх трохи недальновидними.

Третій метод відомий як відпрацювання назад, тобто починаємо з мети розвязку і рухаємося назад у напрямку до початкової постановки задачі. Потім, якщо ці дії оборотні, рухаємося назад від постановки задачі до розв’язку.