Меню
Главная
Авторизация/Регистрация
 
Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ РЕШЕНИЯ NP-ТРУДНЫХ ЗАДАЧ

Способность недетерминированного алгоритма проверить за полиномиальное время экспоненциальное число возможностей может навести на мысль, что полиномиальные недетерминированные алгоритмы являются более мощным средством, чем полиномиальные детерминированные. Действительно, для многих частных задач класса NP, таких как «Коммивояжер» и др., не найдено полиномиального детерминированного алгоритма, несмотря на упорные усилия многих известных исследователей. Поэтому не удивляет широко распространенное мнение, что Р ф NP, хотя доказательство этой гипотезы отсутствует. Если Р не совпадает с N Р, то различие между NPP и Р очень существенно. Все задачи из Р могут быть решены полиномиальными алгоритмами, а все задачи из NPP труднорешаемы. Поэтому если Р ф NP, то для каждой конкретной задачи II е NP важно знать, какая из этих двух возможностей (Р = NP или Р ф NP) реализуется. Конечно, пока не доказано, что Р ф NP, нет никаких шансов показать, что некоторая конкретная задача принадлежит классу NPP. По этой причине цель теории NP-полных задач заключается в доказательстве более слабых результатов вида: «если Р ф NP, то II с NPP».

Такой условный подход основан на идее полиномиальной сводимости. Будем говорить, что имеет место полиномиальная сводимость языка LI с: Z1* к языку L2 с Z2*, если существует функция f: Z1* —» Z2*, удовлетворяющая двум условиям:

  • 1) существует ДМТ-программа, вычисляющая f с временной сложностью, ограниченной полиномом;
  • 2) для любого X е ?1* слово X е L1 в том и только в том случае, если f(X) е L2.

Если L1 полиномиально сводится к L2, будем писать LI оо L2 и говорить «L1 сводится к L2» (опуская слово «полиномиально»).

Если L2 полиномиально сводится к L1, то будем писать L2 оо L1.

Важность понятия «полиномиальная сводимость» вытекает из следующей леммы.

Лемма 9.1. Если L1 со L2, то из L2 е Р следует, что LI е Р (и наоборот: из LI g Р следует, что L2 g Р).

Доказательство. Пусть Z1 и Z2 — алфавиты языков L1 и L2 соответственно, функция f: ?1* -» Z2* осуществляет полиномиальную сводимость L1 к L2; Mf — полиномиальная ДМТ-про- грамма, вычисляющая f, и М2 — полиномиальная ДМТ-програм- ма, распознающая L2.

Полиномиальная ДМТ-программа, распознающая L1, может быть получена композицией программ Mf и М2. Ко входу X е XU* вначале применяется Mf, чтобы построить f(X) е Х2*. Затем к f(X) применяется программа М2, выясняющая, верно ли, что f(X) е L2. Поскольку X е L1 тогда и только тогда, когда f(X) е L2, то это описание дает ДМТ-программу, распознающую L1. То, что время работы этой программы ограничено полиномом, непосредственно следует из полиномиальности программ Mf и М2. Точнее, если Pf и Р2 — полиномы, ограничивающие время работы программ Mf и М2 соответственно, то |f(X)| < |Pf(|X|)|, а время работы только что построенной программы, как нетрудно видеть, ограничено функцией 0(Pf(|X|) + P2(Pf(|X|))), которая является полиномом от |Х|. Лемма доказана.

Если III и 112 — задачи распознавания, a el и е2 — их схемы кодирования, то будем писать III оо 112 (относительно заданных схем кодирования), если существует полиномиальная сводимость языка ЦШ, el) к ЦН2, е2). Когда будет действовать стандартное предположение о «разумности» используемых схем кодирования, упоминание о конкретных схемах кодирования, как обычно, будет опускаться. Таким образом, на уровне задач полиномиальная сводимость задачи распознавания III к задаче распознавания 112 означает наличие функции f: Dm —» Dn2, удовлетворяющей двум условиям:

  • 1) f вычисляется полиномиальным алгоритмом;
  • 2) для всех I е Dn задача I е Y,,, тогда и только тогда, когда f(I) е Y,I2.

Отношение полиномиальной сводимости особенно удобно, поскольку оно является транзитивным. Это устанавливает следующая лемма.

Лемма 9.2. Если LI оо L2 и L2 оо L3, то LI оо L3.

Доказательство. Пусть XI, Х2, ХЗ — алфавиты языков L1, L2, L3 соответственно. Функция fl: XI* -» Х2* реализует полиномиальную сводимость L1 к L2, а функция f2: Х2* -» ХЗ* — полиномиальную сводимость L2 к L3. Тогда функция f: XI* ХЗ*, которая для всех X е XI* определяется соотношением f(X) = f2(fl(X)), реализует исходную сводимость языка L1 к языку L3. Действительно, f(X) е L3 тогда и только тогда, когда X е L1, а вычислимость f за полиномиальное время получается с помощью рассуждений, аналогичных рассуждениям, использованным при доказательстве леммы 9.1.

Доказав лемму 9.2, можно говорить о том, что языки L1 и L2 (соответственно задачи распознавания II1 и 112) полиномиально эквивалентны, если они сводятся друг к другу, т.е. LI оо L2 и L2 оо L1 (имеет место сводимость III оо 112 и 112 оо III). Лемма 9.2 утверждает, что это отношение является отношением эквивалентности, а также, что отношение «оо» определяет частичное упорядочение возникающих классов эквивалентности языков (задач распознавания).

На самом деле класс Р — это наименьший относительно этого частичного порядка класс эквивалентности, и с вычислительной точки зрения его можно рассматривать как класс самых легких языков задач распознавания. Класс NP-полных языков задач распознавания дает нам другой класс эквивалентности: он содержит «самые трудные» языки задач распознавания из N Р.

Язык L называется NP-полным, если L е NP и любой другой язык L' е NP сводится к L. Говоря неформально, задача распознавания II называется NP-полной, если II е NP и любая другая задача распознавания IP е NP сводится к II. Таким образом, лемма 9.1 позволяет отождествлять NP-полные задачи с «самыми трудными задачами из NP». Если хотя бы одна N Р-полная задача может быть решена за полиномиальное время, то и все задачи из NP также могут быть решены за полиномиальное время. Если хотя бы одна задача из NP труднорешаема, то и все NP-полные задачи труднорешаемы.

Следовательно, любая NP-полная задача II обладает свойством, которое сформулировано в параграфе 9.3: если Р ф NP, то II е NPP. Точнее, II е Р тогда и только тогда, когда Р = NP. В предположении, что Р * NP, можно дать гипотетическую картину класса NP (рис. 9.6).

Гипотетическое соотношение классов Р и NP

Рис. 9.6. Гипотетическое соотношение классов Р и NP

Как видно из рис. 9.6, если предположить, что класс Р отличен от NP, то должны существовать задачи из NP, неразрешимые за полиномиальное время и не являющиеся NP-полными.

В дальнейшем будем изучать в основном NP-полные задачи. Как уже говорилось, имеются простые методы доказательства N P-полноты задачи: для этого необходимо доказать, что любая задача из NP сводится к некоторому кандидату на NP-полную задачу.

Следующая лемма указывает простой путь доказательства NP-полноты новой задачи II, если известна хотя бы одна NP-пол- ная задача.

Лемма 9.3. Если L1 и L2 принадлежат классу NP, a L1 — это NP-полный язык и L1 оо L2, то L2 — также NP-полный язык.

Доказательство. Так как L2 е NP, то достаточно показать, что любой язык L' е NP сводится к L2. Рассмотрим любой язык L' е NP. Так как L1 — это NP-полный язык, то L' сводится к L1. В силу транзитивности отношения «оо» из сводимости LI оо L2 следует L' оо L2. Лемма доказана.

Как следует из леммы 9.3, для доказательства NP-полноты новой задачи II достаточно показать, что:

  • 1) II е NP;
  • 2) какая-то одна известная NP-полная задача сводится к II.

Однако, прежде чем воспользоваться этим методом доказательства, необходимо найти хотя бы одну NP-полную задачу.

В настоящее время известен обширный список NP-полных задач (среди которых рассмотренная нами задача «Коммивояжер»).

Из вышеизложенного следует, что при анализе любой новой задачи, связанной, например, с оптимальным распределением ресурсов в экономической системе, естественно сначала задать вопрос: «Можно ли рассматриваемую задачу решить полиномиальным алгоритмом?» Если ответ на этот вопрос положителен, то с точки зрения NP-полноты ничего больше сказать о задаче нельзя. Дальнейшие усилия должны быть сконцентрированы на поиске как можно более эффективных полиномиальных алгоритмов. Если же ответ отрицателен и для решения задачи неизвестны полиномиальные алгоритмы, то естественно возникает вопрос: «Является ли рассматриваемая задача NP-полной?» Если задача оказалась NP-полной, это сильный аргумент в пользу того, что ее нельзя решить за полиномиальное время.

На практике при анализе новой задачи пользуются двусторонним подходом. С одной стороны, предпринимаются попытки доказательства NP-полноты задачи, с другой — осуществляется поиск эффективных (полиномиальных) алгоритмов ее решения. Естественно, что успешное применение на практике такого двустороннего подхода требует от исследователя мастерства как в отыскании доказательств NP-полноты, так и в построении полиномиальных алгоритмов. С методами построения эффективных алгоритмов можно ознакомиться, например, в [23]. Мы же сосредоточили внимание на следующем вопросе: если доказана NP-полнота задачи, каким образом продолжить ее анализ с точки зрения получения практических рекомендаций по отысканию решения задачи?

Один из таких методов анализа заключается в том, чтобы, налагая дополнительные ограничения, рассмотреть подзадачи исходной задачи, по возможности разграничивая NP-полные и полиномиальные задачи.

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

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

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

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

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

Комбинаторная оптимизационная задача II (минимизации или максимизации) состоит из трех частей:

  • 1) множества D,, индивидуальных задач;
  • 2) конечного множества Sn(I) допустимых решений индивидуальной задачи I для каждой I е D,,;
  • 3) функции тп, сопоставляющей каждой индивидуальной задаче I е Djj и каждому допустимому решению а е Sn(I) некоторое положительное целое число шп(1, а), называемое величиной решения а.

Если II — задача минимизации, то оптимальным решением индивидуальной задачи I е D,, является такое допустимое решение а* е Sn(I), что для всех а е Sn(I) выполнено неравенство тп(1, а*) < тп(1, а). Соответственно, для задачи максимизации тп(1, о*)>тп(1, а).

Для обозначения величины тп(1, а*) оптимального решения индивидуальной задачи I будем использовать символ Optn(I) (в тех случаях, когда задача ясна из контекста, индекс II может опускаться).

Алгоритм А называется приближенным алгоритмом решения задачи II, если для любой индивидуальной задачи I е Dn алгоритм А отыскивает некоторое допустимое решение а е Sn(I).

Через А(1) будем обозначать величину шп(1, а) того возможного решения а, которое А строит по I. Если A(I) = Opt(I) для всех I е Dn , то А назовем точным алгоритмом решения задачи II.

Если оптимизационная задача NP-трудна, то, как было сказано ранее, скорее всего нельзя построить точный полиномиальный алгоритм ее решения. Более реалистично попытаться построить приближенный алгоритм А, время работы которого ограничено полиномом невысокой степени и величина А(1) близка к Opt(I).

Перейдем к изучению свойств приближенных алгоритмов применительно к задаче об упаковке в контейнеры. Эта задача весьма актуальна в логистике складирования. Она формулируется следующим образом. Заданы конечное множество V= {Uv ..., ?7} «предметов» и «размеры» S(U) е (0, 1) каждого предмета U е К (размер предмета задан рациональным числом). Требуется найти такое разбиение множества Vна непересекающиеся подмножества Vv ..., Vk, чтобы сумма размеров предметов в каждом из подмножеств Vf не превосходила единицы и чтобы к было наименьшим. Можно считать, что предметы, принадлежащие каждому множеству К, упаковываются в один контейнер единичного размера, а наша цель — упаковать предметы множества V в как можно меньшее число контейнеров. Если контейнер один, а каждый предмет обладает определенной ценностью, то в некоторых ситуациях необходимо упаковать в контейнер те предметы, которые максимизируют суммарную ценность упакованных предметов. В такой формулировке задача об упаковке в контейнеры используется при формировании портфеля ценных бумаг для ситуации, когда известна динамика изменения курсовой стоимости входящих в портфель ценных бумаг.

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

Алгоритм «в первый подходящий» заключается в том, чтобы помещать предметы в контейнеры по очереди в порядке возрастания номеров. Предметы помещаются в контейнер согласно следующему простому правилу: «Очередной предмет U помещается в контейнер с наименьшим номером, у которого сумма размеров уже помещенных в него предметов не превосходит 1 - Б(Щ. Другими словами, ?7. помещается в первый из контейнеров, куда он может попасть, не нарушая ограничений по размеру. На рис. 9.7 показан пример работы этого алгоритма.

Иллюстрация алгоритма решения задачи об упаковке в контейнеры

Рис. 9.7. Иллюстрация алгоритма решения задачи об упаковке в контейнеры

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

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

Проанализируем, насколько близко к оптимальному решение, полученное алгоритмом «в первый подходящий». Вначале рассмотрим число контейнеров, требующихся для указанного алгоритма, как функцию от параметров задачи. Обозначим эту функцию как FF(I). Имеют место неравенства:

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

индивидуальной задачи

Поскольку никакие два предмета не могут попасть в один ящик, то FF(I) = п, в то время как сумма размеров предметов равна;

и если е достаточно мало, то она будет сколь угодно близка к п/2.

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

то отсюда для всех индивидуальных задач I вытекает неравенство

В [23] приводится теорема, что для FF(I) имеется лучшая оценка. Теорема 9.2. Для всех индивидуальных задач I об упаковке имеет место неравенство

Более того, существуют индивидуальные задачи I, для которых Opt(I) сколь угодно велико и

Таким образом, теорема 9.2 характеризует асимптотическое поведение в худ ш е м случае алгоритма «в первый подходящий». Величина FF(I) никогда не отличается от оптимума более чем на 70%, и в некоторых случаях такое отличие действительно достигается.

Далее перейдем к анализу алгоритмов с лучшей оценкой поведения. Ясно, что алгоритм «в первый подходящий» можно видоизменить, пользуясь, например, следующим более совершенным правилом размещения: каждый следующий предмет U. помещают в контейнер, содержимое которого ближе всего к величине 1 - S(Uj), но не превосходит ее (если имеется несколько таких контейнеров, то выбирается контейнер с наименьшим номером). Этот алгоритм называется «в наилучший из подходящих». Как показано в [23], в наихудшем случае он имеет, по существу, те же характеристики, что и алгоритм «в первый подходящий».

Несколько лучший приближенный алгоритм получается, если учесть, что наихудшей для алгоритма «в первый подходящий» (а также для алгоритма «в наилучший из подходящих») оказывается ситуация, когда в упорядочении предметы с наибольшими размерами идут раньше предметов с наименьшими размерами, т.е. -S^t/j) > S(U2) > ... > S(Un). Алгоритм применения процедуры

«в первый подходящий» к переупорядоченному таким образом списку предметов называется «в первый подходящий в порядке убывания» (соответствующая функция обозначается FFD(I)). Работа этого алгоритма характеризуется следующей теоремой Джонсона.

Теорема 9.3. Для всех индивидуальных задач об упаковке выполняется неравенство

Более того, существуют индивидуальные задачи, для которых Opt(I) произвольно велико и

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

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

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы