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

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

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

Проиллюстрируем этот метод на известной головоломке «Ханойские башни». Имеются три стержня А, B и С. На стержень А вначале одеты несколько дисков разного размера, причем диск меньшего размера должен лежать только на диске большего размера. Цель головоломки – перемещать диски по одному со стержня на стержень так, чтобы диск большего размера никогда не оказывался выше диска меньшего размера. Требуется переместить все диски на стержень B. Стержень С является вспомогательным и используется для временного хранения дисков.

Применяя метод декомпозиции, представим задачу перемещения n дисков состоящей из двух подзадач размера n-1. Сначала переместим n-1 наименьших дисков со стержня А на стержень C, затем оставшийся наибольший диск переместим на стержень B. Далее аналогично поступаем к задаче перемещения n-1 дисков, но со стержня С на стержень B, выполняя подзадачи перемещения n-2 дисков. Это перемещение выполняется путем рекурсивного применения описанного метода.

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

«Жадный алгоритм» на каждой отдельной стадии решения задачи выбирает тот вариант, который на данном этапе является локально оптимальным. Для примера рассмотрим задачу составления заданной суммы, например 63 коп., из имеющихся монет достоинством 25, 10, 5 коп. и 1 коп.. «Жадный» алгоритм заключается в выборе каждый раз монеты наибольшего достоинства, не превышающей по стоимости оставшейся суммы, добавление ее в список монет и вычитании ее стоимости из оставшейся суммы. Алгоритм быстро приведет к решению: 2 монеты по 25 коп., 1 монета в 10 коп., 3 монеты по 1 коп.. «жадные» алгоритмы позволяют получать хорошие решения, однако не всегда эти решения являются оптимальными при различных условиях задачи. Так, если надо набрать сумму в 15 коп. из монет достоинством 11, 5 коп. и 1 коп., то «жадный» алгоритм даст результат: 1 монета в 11 коп. и 4 монеты по 1 коп. (всего 5 монет). В то же время, можно было бы обойтись 3 монетами достоинством в 5 коп..

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

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

1. Начнем с произвольного решения.

2. Для улучшения текущего решения применим к нему какое-либо преобразо-

вание на некоторой заданной совокупности преобразований. Это улучшенное решение становится новым «текущим» решением.

3. Повторяем указанную процедуру до тех пор, пока ни одно из преобразова-

ний из заданной совокупности не позволяет улучшить текущее решение.