линомиальным алгоритмом?» Если ответ на этот вопрос положителен, то с точки зрения NP-полноты ничего больше сказать о задаче нельзя. Дальнейшие усилия должны быть сконцентрированы на поиске как можно более эффективных полиномиальных алгоритмов. Если же для решения задачи неизвестны полиномиальные алгоритмы, то естественно возникает вопрос: «Является ли рассматриваемая задача NP-полной». Если задача оказалась NP-полной, то это сильный аргумент в пользу того, что ее нельзя решить за полиномиальное время.
На практике при анализе новой задачи пользуются двухсторонним подходом. С одной стороны, предпринимаются попытки доказательства NP-полноты задачи, с другой- осуществляется поиск эффективных (полиномиальных) алгоритмов ее решения. Естественно, что успешное применение на практике такого двухстороннего подхода требует от исследователя мастерства как в отыскании доказательств в NP-полноты, так и в построении полиномиальных алгоритмов. С методами построения эффективньпс алгоритмов можно ознакомиться в книгах по построению алгоритмов, например [25]. Мы же сосредоточили внимание на вопросе: если доказана NP-полнота задачи, каким образом продолжить ее анализ с точки зрения получения практических рекомендаций по отысканию решения задачи. Один из таких методов анализа заключается в том, чтобы, налагая дополнительные ограничения, рассмотреть подзадачи исходной задачи, по возможности разграничивая NP-полные и полиномиальные задачи.
Другим подходом является максимальное сокращение объема перебора при решении задачи, хотя при этом признается возможность экспоненциального времени работы алгоритма на какой-либо из индивидуальных задач. К наиболее широко используемым приемам сокращения перебора относятся приемы, основанные на методе «ветвей и границ» или других методах неявного перебора. Эти приемы состоят в построении частичных решений, представленных в виде дерева поиска и применении мощных методов построения оценок, позволяющих идентифицировать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге может быть отсечена целая ветвь «плохих» решений. Известны и другие методы, кроме метода «ветвей и границ». Это метод динамического программирования, методы отсечений и метод Лагранжа.
И, наконец, еще один подход основан на приеме, который можно назвать «снижение требований». Он заключается в отказе от поиска оптимального решения и нахождение вместо этого хорошего решения за приемлемое время. Алгоритмы, основанные на этом приеме, обычно
называются эвристическими, поскольку они используют различные соображения без строгих обоснований. Методы, применяемые при построении таких алгоритмов, сильно зависят от специфики задачи, хотя существуют несколько исходных принципов, которые могут служить некоторой отправной точкой. Наиболее широко используется так называемый метод «локального поиска». В этом случае заранее выбранное множество локальных операций используется для последовательного улучшения начального решения до тех пор, пока такое улучшение возможно, а в противном случае оказывается достигнутым «локальный оптимум». Эвристические алгоритмы, построенные этим и другими методами, на практике оказываются весьма удовлетворительными, хотя для получения удовлетворительных характеристик требуется большая работа, связанная с последовательным улучшением применяемых эвристик. В результате только в очень редких случаях удается заранее предсказать и оценить поведение таких алгоритмов. Вместо этого такие алгоритмы оцениваются и сравниваются на основе сочетания эмпирических данных и аргументов, опирающихся на здравый смысл. В то же время в некоторых случаях удастся доказать, что решения, получаемые эвристическим алгоритмом, всегда будут отличаться от оптимальных в процентном отношении не более чем на определенную величину. Подобные результаты можно рассматривать как «оценки погрешности» алгоритмов.
Рассмотрим один из примеров применения приближенных алгоритмов для задачи «упаковка в контейнеры». Дадим формальное описание понятия и обозначений комбинаторной оптимизационной задачи.
Комбинаторная оптимизационная задача II есть либо задача минимизации, либо задача максимизации и состоит из трех частей:
1)множество Ai индивидуальных задач;
2)для каждой / е Пц существует конечное множество Sn(/) допустимых решений индивидуальной задачи /; 3) функции шц, сопоставляющей каждой индивидуальной задаче I е Оци каждому допустимому решению а е Sjj(I) некоторое положительное целое число ш/Х/,бг), называемое величиной решения а. Если II задача минимизации (максимизации), то оптимальным решением индивидуальным решением индивидуальной задачи I е Вц является такое допустимое решение (т* е Sn(I), что для всех а е Su{I) выполнено неравенство 7Wn(/,o-*) < тп(1,а). Соответственно wn(/,tT*) > mriho).
Для обозначения величины тп(1,(7*) оптимального решения индивидуальной задачи / будем использовать символ ОРЩ!) (в тех случаях, когда задача ясна из контекста, индекс II будет опускаться). 404
Алгори™ А назьгоается приближенным алгоришом решения задачи II, если для любой индивидуальной задачи I е Dn алгори™ А отыскивает некоторое допустимое решение а е Su(I). Через А(1) будем обозначать величину ти(1,(7) того возможного решения о, которое А строит по /. Если А(1) = OPTII) для всех I е Dn, то А назовем точным алгоритмом решения задачи Я.
Если оптимизационная задача NP, трудна, то, как бьшо сказано ранее скорее всего нельзя построить точный полиномиальный алгоритм решения этой задачи. Более реалистично попытаться построить приближенный алгоритм А, время работы которого ограничено полиномом невысокой степени и величина (7) близка к ОРТ(/).
Перейдем к изучению свойств приближенных алгоритмов применительно к задаче об «упаковке в контейнеры». Она формулируется следующим образом. Задано конечное множество К= (С/1, Un) «предметов» и «размеры» S(U) е (0,1) каждого предмета U е К (размер предмета задан рациональным числом). Требуется найти такое разбиение множества V на непересекающиеся подмножества К1, ..., FX:, что сумма размеров предметов в каждом из подмножеств и Vi не превосходила 1 и чтобы к было наименьшим из возможных. Можно считать, что предметы, принадлежащие каждому множеству Vi, упаковываются в один контейнер размера 1, а наша цель - упаковать предметы множества V в как можно меньшее число контейнеров. Если контейнер один, а каждый предмет обладает определенной ценностью, то в некоторых ситуациях необходимо упаковать в контейнер те предметы, которые максимизируют суммарную ценность упакованных предметов. В такой формулировке данная задача используется при формировании портфеля ценных бумаг для ситуации, когда известна динамика изменения курсовой стоимости входящих в портфель ценных бумаг. Данная задача является NP-трудной, поэтому надежд на отыскание эффективного точного алгоритма ее решения немного. В то же время имеется несколько заслуживающих внимания простых приближенных алгоритмов. Один из них известен под названием «в первый подходящий». Алгоритм заключается в том, чтобы помещать предметы в контейнеры по очереди в порядке возрастания номеров. Предметы помещаются в контейнер согласно следующему простому правилу: «Очередной предмет U помещается в контейнер с наименьшим номером, у которого сумма размеров уже помещенных в него предметов не превосходит 1 - S(Ui), Другими словами, Ui помещается в первый из контейнеров, куда он может попасть, не нарушая ограничений по размеру. На рисунке 12.7 показан пример работы этого алгоритма. Здесь каждый предмет представлен прямоугольником, имеющим высоту, пропорциональную размеру предмета.