Алгоритмизация задач
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
°нном конкретном случае использование известных оптимизационных методов или необходимо разработать эвристический алгоритм.
При решении приведенных вопросов возникает необходимость оценки качества алгоритмов. Существует много критериев. Чаще всего используется критерий сложности алгоритма, который характеризует время, затрачиваемое алгоритмом на получение решения в зависимости от размера задачи. При этом под размером задачи понимается некоторое число, которое выражает меру количества входных или выходных данных.
Предел временной сложности при увеличении размера задачи называется асимптотической временной сложностью. Аналогично определяется емкостная сложность и асимптотическая емкостная сложность. Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера п за время сn2, где с - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть О(п2) (читается "порядка n2"). Точнее, говорят, что неотрицательная функция g(n) есть O(f(n)), если существует такая постоянная с, что g(n) ? cf(n) для всех, кроме конечного (возможно пустого) множества неотрицательных значений п.
Пусть дано пять алгоритмов А1 - A5 (табл. 1). Под временной сложностью здесь понимается число единиц времени, требуемого для обработки входа размера п. В табл. 5.1 приведены размеры задач, которые можно решить за 1 с, 1 мин и 1 ч каждым из этих пяти алгоритмов. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм А4 алгоритмом А3, можно решить задачу в 6 раз большую, а заменяя А4 на А2, можно решить задачу, большую в 125 раз. Если в качестве основы для сравнения взять 1 ч, то различие алгоритмов становится еще значительнее. Отсюда можно заключить, что асимптотическая сложность алгоритма служит важной мерой его качества, причем такой мерой, которая приобретает все большее значение с увеличением размера вычислений.
Таблица 1
Сложность алгоритма определяет также то увеличение размера задачи, которого можно достичь с увеличением скорости машины. Увеличение скорости вычислений в 10 раз увеличивает размер задачи, которую можно решить, для алгоритма А5 только на 3, тогда как для алгоритма А3 - более чем втрое. Однако алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером. Например, если временные сложности алгоритмов А1 - A5 равны соответственно 1000n, 100n, logn, 10n2, n3 и 2n, то алгоритм А5 будет наилучшим для задач размера 2 ? п ? 9, А3 - для задач размера 10 ? п ? 58, А2 - при 59 ? n ? 1024, a A1 - n > 1024.
Для того чтобы показать, что не существует алгоритма, выполняющего решение задачи менее чем за определенное время, необходимо точное определение того, что есть алгоритм. Уточнение понятий алгоритма и его сложности требует привязки к некоторой конкретной схеме вычислений. Обычно в качестве такой схемы рассматривается машина Тьюринга или так называемая адресная машина. Однако можно принять модель, более близкую к реальному ходу вычислений в оперативной памяти машины с одним процессором, и считать, что вычисления реализуются программой, написанной на некотором упрощении (подмножестве) языка АЛГОЛ.
На первоначальных этапах развития теории сложности в ней чаще всего рассматривались задачи, на которые можно дать лишь один из двух ответов: ДА или НЕТ. Например, классическая "сложностная" постановка известной задачи о ранце (с ограничением в виде равенства) будет заключаться в выяснении того, существуют ли для заданных чисел aj, j = 1,2, ..., n и b значения булевых переменных xj, удовлетворяющие ограничению
(1)
Обычная же формулировка задачи о ранце состоит в максимизации суммы
(2)
при условии (1). Однако легко заметить, что ответы на последовательность задач типа "существует ли набор булевых переменных xj, удовлетворяющих (1), такой, что z = k при k = 0, 1,2, ..." дадут решение задачи о ранце в привычной формулировке. При этом под задачей понимается весь класс однотипных вопросов, различающихся входными данными. Например, в задаче (1), (2) вход представляет собой набор {k, {аj}, {сj}, b}, так что задача о ранце сводится к решению вопроса "существует ли значение целевой функции, равное k, в ситуации, описываемой остальными входными данными". Конкретный набор исходных данных определяет реализацию задачи.
Обозначим задачу через П, ее реализацию - через ?. Под размером реализации будем понимать число символов, необходимых для записи входных данных этой реализации. Размер реализации ? будет обозначаться . Под временем решения t? реализации ? понимается сумма времен выполнения всех команд программы.
Введем понятие класса задач Р, разрешимых за полиномиальное время. Этот класс состоит из всех задач П, обладающих следующим свойством: для любой существует АЛГОЛ-программа uП и полином fП (), такие, что любая реализация uП за время t? (uП) ? fП (). Примерами задач из класса Р являются задачи нахождения кратчайшего пути между двумя вершинами графа, минимального разреза в сети, минимального дерева.
Общепринято, что если задачу нельзя решить быстрее, чем за экспоненциальное время, то ее следует рассматривать как трудно разрешимую. Такие задачи образуют класс задач, недетерминированным образом разрешимых за полиномиальное время (NP-класс). Для определения NP класса необходимо расширить язык, добавив к нему новую команду CHOOSE(x). Эта команда придает недетерминированным образом переменной х значение О или 1. Ра