Н.М. Новикова - Дискретные и непрерывные задачи оптимизации

УЛК 519.85 Ответственный редактор академик . П. С. Краснощеков Работа написана на базе семестрового курса лекций, читаемого автором в течение последних пяти лет студентам 4-го курса программистского потока факультета ВМиК МГУ. В сжатой форме дается изложение основ теории сложности, линейного программирования (ЛП) — с описанием полиномиальных алгоритмов, целочисленного ЛП, математического программирования (необходимые условия экстремума при ограничениях-неравенствах, локальные методы безусловной оптимизации, метод штрафов, идеи глобальной оптимизации), схем методов динамического программирования и ветвей и границ. Работа частично поддержана грантом РФФИ Но.95-01-00232а, а также грантом Хо.ЭСП100 1ЯР и Российского правительства. Рецензенты: С. К.

Завриев, А. В. Лотов Научное издание (С) Вычислительный центр РАН, 1996. Св.план 1995, поз.53 1. ВВЕДЕНИЕ В ТЕОРИ1О СЛОЖНОСТИ Литература: 1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Мл Мир, 1982. 2. Пападимитриу Хе Стайглиц К. Комбинаторная оптимизация. Мл Мир, 1985. 11. Понятие о сложности решения задач Основные овределсиию: индивидуальною и массовою задачи, кодировка, алеоритм решсиию массовой задачи, времепиаю сложность влеоритма.

Классы Р и 1Ч1Р (формальныс опрсдслсиаю, примеры). 1. На вопрос, для чего надо иметь представление о сложности решаемых задач, наиболее наглядный ответ дан во введении к книге [1]. В этой книге также приводится более 500 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых в настоящее время нет оснований надеяться построить эффективные алгоритмы их решения. Что это значит формально, будет рассказано в данном разделе (Ц1-4), а соответствующие практические выводы каждый человек, так или иначе связанный с разработкой алгоритмов и программ, делает для себя сам.

Кроме того, теория сложности — новая, модная, интенсивно развивающаяся область математики и кибернетики, ее терминология широко распространена в современной научной литературе и требует определенного с ней знакомства. Появление вычислительной техники привело к тому, что все реже приходится решать отдельную конкретную задачу, а все больше писать программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому имеет смысл говорить о сложности не для одной индивидуальной задачи 1, а для массовой задачи, илв проблемы П, соответствующей множеству индивидуальных задач. Формально массовая задача П определяется 1о)общим списком всех параметров задачи (свободных параметров, значения которых не заданы), 2~)формулировкой свойств, которым должен удовлетворять ответ (решение задачи).

Индивидуальная задача 1 Е П получается из П, если всем параметрам присвоить конкретные значения. !1ля примера рассмотрим задачу коммивояжера: найти минимальный маршрут обхода группы объектов (условно говоря, городов) с возвратом в начальную точку. Лля П коммивояжера введем 1'увходные параметры: число городов и! или множество городов С = (с!,..., см) и набор расстояний между городами (и(сю, су) ) 0 ". сб су Е С, ! ф у); 2с)требования к решению: [с,<!В...,с рч!] реализует !т-! ппп ~~ п(с~(0~ ст(в+!)) + !4(се(т)~ с~(\)) !ж! где минимум берется по всем возможным перестановкам !г на множестве индексов городов.

Конкретизируем параметры 1~, чтобы получить индивидуальную задачу 1 коммивояжера: гп = 4, в(с!, сз) = 10, !!(с!, сз) = 5, !!(с!, с4) = 9, !!(сз, ся) = 9, !((сз, ся) = 3, !з(сз, сз) = 6, И(с!,су) = Ы(су,с;). Тогда в задаче 1 оптимальным оказывается маршрут [с!, сз, сю сз], реализующий путь минимальной длины 21. Кроме первичных понятий массовой и индивидуальной задачи (П и 1) мы будем использовать термин алгоритм и обозначение А для пой!аговой процедуры (решенкя задачи), в частности машины Тьюринга или программы для ЭВМ.

Будем говорить, что алгорввим А рсшасш массовую задачу П, если для любой индивидуальной задачи 1 Е П алгоритм А применим к 1 (т.е. останавливается за конечное число шагов) и Л Е П алгоритм А дает решение задачи 1. Например, для П коммивояжера сушествует алгоритм, который решает ее на основе полного перебора всех маршрутов (перестановок я). Большинство дискретных и комбинаторных задач допускает решение с цомощью некоторого процесса перебора вариантов, однако число возможных варнантов растет экспоненцизльно в зависимости от размеров задачи (так, в задаче коммивояжера гв! маршрут!эв).

Поэтому переборные алгоритмы решения массовых задач считаются неэффективными (могут решать лишь небольшие индивидуальные задачи). В отличие от них эффективными называются иеляиомиальяые алгоритмы решения массовой задачи, т.е. такие, которые решают произвольную 1 Е П за время, ограниченное полиномом от "размера" 1. Несмотря на определенную условность этого разделения с точки зрения практического счета, оно обаясняется прежде всего тем, что центральным для дискретной оптимизации является вопрос, можно ли построить алгоритм решения массовой задачи (т.е.

любой индивидуальной), не перебирающий всех или почти всех вариантов ее решения. Если для массовой задачи П существует полиномиальный алгоритм, ее решаюшяй, значит, ее можно решить не путем перебора — эффективно. Укаэанные задачи П называются полиномиальными. Перейдем к их формальному определению. 2.

формализация проводится для задач распознавания своэспае. Это — массовые задачи, предполагающие ответ "да" или "йет" в качестве решения. Таким образом, в п.2е определения П распознавания свойств стоит некоторый альтернативный вопрос и решением каждой индивидуальной задачи 1 Е П является правильное распознавание, принадлежит ли она к задачам с ответом "да"'. Последнее подмножество множества индивидуальных задач будем обозначать к. Теперь введем обозначение Р для множества всех возможных значений параметров, заданных в пЗЯ определения П. Очевидно, что набор (Р(П),~г(П)] полностью характеризует соответствующую массовую задачу П распознавания свойств. Несмотря на специфичность постановки, класс задач распознавания свойств является достаточно широким: по крайней мере, для любой задачи дискретной оптимизации можно указать аналогичную П распознавания свойств. В.частности, для П коммивояжера, если ввести в п.1 еще один параметр  — длину маршрута, то вопрос в п.2е "существует ли маршрут длины, не превышающей В?" дает ее переформулировку как задачи распознавания свойств.

Полученная П коммивояжера имеет в литературе обозначение КМ (или ЗК [2)), для нее ЩКМ) = (С, (и(с;, су) Е Е+~ с;, с~ Е С, з < у), В Е Е+). Здесь и далее 3~ — множество натуральных чисел, Š— целых. Лля формализации "размера" индивидуальной задачи свяжем с каждой проблемой П определенную схему ходароеааая (кодировку). Введем конечное множество — аяфаеаш Е = (аД, например Е = (О, 1), а также множество Е* слое яад алфавящом Š— произвольных конечных последовательностей, составленных из символов алфавита,возможноповторяющихся, а = х;,о;,...а;, а;,. б Е чз например, пустое множество 9 или 011000.

Число а называется длааен слеза х и обозначается знаком модуля, и = ф. Кодировкой задача П назовем такое отображение е: П- Е*, ставящее в соответствие любой индивидуальной задаче 1 б П ее код е(1) = и Е Е' (слово из алфавита Е'), что 1 )возможно однозначное декодирование: УХ~ ф 1з е(1~ ) ус е(1з); 2') е, е ' полиномиально вычислимы: существует алгоритм, реализующий е, е ~, и полипом р( ), для которого Л б П время определения с(1) и с ~(с(1)) не превосходит рОс(1)О; ' 3") кодировка неизбыточна: для любой другой кодировки е', удовлетворяющей условиям 1",2', найдется полипом р'( ) такой, что Л б сП )е(1)~ < р'(~е'(Ц).

Например, для записи целых чисел неиэбыточной является любая Й-ичная система счисления с Й ) 1, кодировка чисел тем же количеством палочек (случай Й = 1) нзбыточна. 'УПРАЖНЕНИЕ 1. Предложить веизбыточную кодировку н оценить по порядку длину входа задачи коммивояжера, сравнить полученную оценку с указанной в [1) ва с. Зб: из + (1ойз В) + шах(/1онз й(сь су)) ~ сч су б С) . Здесь и далее знаком Ц обозначается ближайшее целое сверху к числу в скобках, а Я вЂ” целая часть числа. Начиная с этого момента, в Я 1-3 мы будем, как правило, рассматривать П распознавания свойств, оговаривая другие случаи особо.

После того как для массовой задачи П введена кодировка, с любой индивидуальной задачей 1 б П будет связано некоторое слово е в алфавите Е этой кодировки. Слова, которые соответствуют индивидуальным задачам распознавания свойств, имеющим. ответ "да", условимся считать "правильными" и множество правильных слов в Е' назовем языком. Формально, язык Ь(Пэе) =' е( я (П))гм =' (а б Е'~ Š— алфавит с, о = е(1), 1 б Ъ'(П)). С алгоритмом А решения задачи П распознавания свойств будем ассоциировать машину Тьюринга (программу для детермини- роваыыой машины Тьюринга) с входным алфавитом Е и коыечыыми состояниями ау ("да") и гдо ("ыет") и аналогично назовем языком алгоритма А множество слов, вравямасмых А (с которыми ыа входе А остаыавливмтся в состоянии йу — "да"), Ь(А) =' (о' б Е'~ Š— алфавит А, и А(а) = ау).

Опгкделеиие 1. Алгоритм А рсшасш массовую задачу П с кодировкой е, если ЦА) = ЦП,с) и %г б.Е' А останавливается. Обозначим 4л(о) время работы ыад словом о б Е' (число шагов) алгоритма А до остановки. Врсмсннбя саохсыосщьш алгоритма А решеыия массовой задачи П назовем фуыкцию Тл( ), определяемую как Тл(п) = шах 1А(о) ов б Е»..

ояв'. ~а~сп Таким образом, при оцеыке времеыыбй сложыосты алгоритмов мы рассчитываем ыа "худшую" из возможных индивидуальных задач (даыыого размера), поскольку заранее ые известно,, с какой коыкретыой задачей придется работать. ~ПРА~КНЕНИЕ 2. Леть алгоритм распознавал простоты числа, оценить временнУю сложзюсть алгоритма. Опгкдвдкцик 2. Класс вохамомаааьяо разрешимых задач Р =' (ЦП,е)~ ЗА, решающий П с кодировкой е, Эр( ) — поливом: Тл(п) < р(в) Ув б Е+). Если для задачи П существует такая кодировка с, что ЦП,с) б 6Р, то будем ыазывать задачу П воавяомаааьяо разрешимой или просто волвномиахьвоа и пользоваться обозначением ПЕР, отождествляя массовую задачу и язык.

(С учетом условия ыеизбыточыости кода указаыыая процедура корректыа, ибо для полиыомиальиой П получаем ЦП,с) б Р Ус.) Примером поливомиальыой задачи является распозыаваыие четности целого числа. (С еще одной полиыомиальыой задачей мы встретимся в разд.2.) Зля задачи распозыаваыия простоты числа (ПН) вопрос о ее полиыомиальыости пока открыт.