Проектирование алгоритмов

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

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

Для выражения характеристик быстродействия в вычислительной технике используется О-нотация (big-Oh notation).

О-нотация

В этой нотации используется специальная математическая функция от n, т.е. количества элементов, которой пропорционально быстродействие алгоритма. Таким образом, мы говорим, что алгоритм принадлежит к классу O(f(n)), где f(n) некоторая функция от n. Приведенное обозначение читается как «О большое от F(n)» или, менее строго, «пропорционально f(n)».

Так последовательный поиск принадлежит классу О(n), а бинарный – к классу O(log(n)), откуда собственно и можно сделать вывод, что бинарный поиск всегда быстрее, т.к. log(n)<n.

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

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

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

Метод декомпозиции (или метод разбиения, или метод «разделяй и властвуй») является одним из самых распространенных методов проектирования алгоритмов. Он предполагает такую декомпозицию (разбиение) задачи размера 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. Повторяем указанную процедуру до тех пор, пока ни одно из преобразований из заданной совокупности не позволяет улучшить текущее решение.

CC-BY-CA Цыганенко В.Н., 20.10.2013