Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 35
Текст из файла (страница 35)
рис. 8.5) однородна относительно Вь и, следовательно, при умножении всех элементов матрицы В> на некоторый скаляр все элементы матрицы В;, умножаются на тот же скаляр. Мы хотим доказать, чзо при подходящих Р и 6 полуэллипсоид 9 Е,' = (х> х Е Е;, а' (х — 1;) ( О) содержится в Ено Для этого достаточно показать, что эллипсоид Н,.=-(Р(1;, В;), 6(1'ь В;)(1+6)>) содержится в Ерм так как по теореме 8 3 (1>2) Е; Н, Для этого в свою очередь достаточно показать, что все точки на грани>!г Нг также лежат Гл. З. Алгодитмы и сложность внутри Е~„, т.
е. из условия (х — Р((;, В;))'6(19 В~) '(х — Р((;, В~))=(1+6)! (3.10) вытекает хс Е,'о,. (8.1 1) Но (8.11) эквивалентно неравенству (х — Р((и В;))'6((и В;) '(х — Р(1;, В~))((1+6)л+'. (8.12) Пусть г — любое число, появляющееся в алгоритме эллипсоидов (» может быть элементом В, или 0 для некоторого / или некоторым промежуточным результатом). Нетрудно доказать, что )г)~М= =2лко для некоторого с)0, где К вЂ” число итераций (см. задачу 16; тот же результат справедлив для модифицированного алгоритма эллипсоидов с точностью Р, который мы анализируем), Поэтому любая арифметическая операция над такими числами, выполняемая с точностью Р, дает результат с абсолютной ошибкой, не превосходящей М.2 н. Совокупная ошибка любой последовательности из р таких операций не превосходит РМ 2 н, Поскольку вычисления Р и 6 включают в себя 6(л') арифметических операций, то (опуская для простоты аргументы В; и г; в Р, Р, 6 и 6) получаем Р=Р+ОМ2'" г для некоторого с> О.
(Мы используем с в различных равенствах для обозначения положительных констант, не обязательно связанных друг с другом.) Заметим, что здесь Π— вектор. Отсюда х — Р=х — Р+ОМ2ло и. (863) Допустим, что рассматриваемая индивидуальная задача СЛН имеет решение — в противном случае алгоритм эллнпсоидов, очевидно, корректен. Нетрудно показать (задача 15), что )х — Р!)2 'лт для любой точки х на границе эллипсоида НР Тогда из (8.13) вытекает х — Р = (х — Р) (1+ ОМ2'"х о) н, следовательно, для любого х, удовлетворяющего (8.10), (х — Р)' 6 ' (х — Р) = (х — Р)' б"'(х — Р) (1+ОМ2'лт и)', (8,14) Рассмотрим теперь произвольный элемент д матрицы 6-'.
Он равен частному от деления определителя 0 некоторого минора матрицы 6 на определитель матрицы б. Так как определитель порядка и является суммой а! произведений и аналогично (8.13) максимальная ошибка каждого сомножителя в каждом произведении не превосходит М2"-', то бе1(6)=бе1(6)-~-ОМ"2лс-н. По теореме 8.4, учитывая, что )ья итерация не была последней, 191 Задачи получаем бе1(В;) > 2 щ+')с (1 + 5) /и и, следовательно, бе( (6) > = 2-<и"а)с-' (1+5) /". Таким образом г)е((6) = г)е1 (6) (1+ ВМп2'пс ") (1+5)"". (8.15) Аналогично, если Р— подопределитель матрицы 6, соответствующий Р, то 0=Р+0Мп2спс-л, и если у — элемент матрицы 6 ', соответствующий д, то ВМп+г2с ) -и (1 1„5)ка Поэтому (8.14) принимает вид (х — Р)'6 '(х — Р)=(х — Р)'6 '(х — Р) х г (1 1 ВМ2сас-Р)э 1 ВМасз2спс Р (] 1 5)Ка — (1 1 5)/ (1 1 ВМа+е2сас-л (1 1 5)Ка) Если взять К=32п (п+1)/„5=1/Кп и Р=сКп'- для достаточно большого с, то получим неравенство (8.12), и полуэллипсоид (1/2)Е/ действительно содержится в Е/ч и Остается показать, что объемы эллипсоидов Е/ убывают со скоростью геометрической прогрессии.
Из теоремы 8.3 (п. в)), равенства (8.15) и определения Е/+, имеем /+г),~~ 2-1/а(п+)).(1 1 5)а.(1 1 Мп2сс-и(] 1 5)яа) чо1 (Е/) Положив опять Р=сКп' для достаточно большого с, получаем 2 иа(а+)) чо) (Е;) (Заметим, 'что Р ограничено полиномом относительно 1..) Согласно тем же рассуждениям, что и в теореме 8.4, после К=32п(п+1)Е итераций модифицированный алгоритм эллипсоидов либо даст решение, либо с полной достоверностью выяснит, что решения не существует.
Таким образом, доказана Теорема 8.5. Для задачи ЛП сущесп)сует полиносниальный алгоРильк. За,цвчм 1. Опишите хорошо известный метод вычитания десятичных целых чисел как алгоритм. При этом можно представлять алгоритм аналогично тому, как это делается в данной кинге. Входом для вашего алгоритма являются число а разрядов ° двух данных целых числах н два а-элементных массива Л и В, содержащие десятичные разряды этих чисел.
2. Можно доказать, что для приведенных ниже трех проблем ие существует алгоритма. Рассмотрите каждую из этих проблем и убедитесь по крайней мере в том, что некоторые очевидные подходы к их решению ие годятся. а) Проблема остановки, описанная а й 8.1, (Если вы честолюбивы, попытайтесь обьяснить почему не может существовать алгоритма, решающего эту про. блему. у)сэзание: допустим, чго существует....) Гл. (). Алгоритмы и сложность 192 б) В проблеме соотеетстеия Поста дан словарь, связывающнй два языка; т, е. конечное множество пар слов. Каждая пара содержит одно слово из языка 1 и одно слово из языка 2.
Спрашивается, существует ли фраза (последоватеяьность слов, возможно, с повторениями), имеющая одно н то же значение в обоях языках. (Предполагается, что слова в этих языках пишутся подряд без раэделяюп«нх пробелов,) Например, если словарь имеет внд Язык 2 Номер слова Язык ! то ответ в этом случае «да», поскольку в обоих языках фраза, состоящая нз слов 2, 4, 2 и 3, имеет внд шЫВш)шИ«(ш). в) Дано коне п«ое множество ч»девиц различной формы, я спрашивается, можно ли замостить всю плоскость, имея в запасе бесконечное число черепиц каждой формы.
Например, если имеются черепипы следующнх четырех форм; то ответ в этом случае «да», поскольку можно следующим образом замостить пласкостьс 193 Задачи 3. Дайте детальное описание алгоритма, который по данной иХ п-матрице расстояний снстематнческн порождает все обходы п городов н выбирает самый дешевый обход (вспомнкте пример 3.1).
4. Постройте алгоритмы для решения каждой нз описанных ниже задач. В каждой задаче зафиксируйте представленне ахала н лайте верхнюю оценку времени работы вашего алгоритма в виде функции ог размера входа. а) Для данного графа 6=(У. Е) выяснить, существует ля в 6 такой цикл ]и, а, ю, г, и), что ]и, г], ]и, ю)еиЕ. б) Для данных п>2 прямь1х на плоскости (иьт+ь?у=об 1=1, ..., п), гле ии Ьь с; — целые Лля всех 1, выяснить, существует ли точка, лежащая нз всех атнх прямых, в) Для данного целого числа р выясннтш является ли опо простым. гч] Для данных целых чисел х, у н г выяснить, существует лк такое целое число п>0, что к"+у"=-г". л) Для данных графа 6=(У, Е) и з, (ц'г' выяснить, существует лн а 6 путь нззв!. е) Для данных графа 6=(У, Е) и з, (ц !г определить, сколько существует цепей из з в ! в графе 6.
ж") Для данной шахматной позиции выясню ь, имеется ли в ней форсированный выигрыш за белых.(Вопрос: сколь большими в данном случае могут быть инливнлуальпые задачи? Имеет лн смысл в этой задаче понятие скорости росши сложности алгорнгма?) з) Длн данной познцин в и-лгерног! иере а «рестихи и нолики па .,оске размером ЗХЗХ... ХЗ и раз выяснить, имеется лн форсированный выигрыш за Х. и*) Граф можно использовать Лля представления карты системы шуииелей, в которых прячется беглец. Для ланпога графа 6 и целого числа й>0 выяснить, достаточна ли У человек лля ареста беглеца, даже если считать его бесконе|но хитрым и везучим к) Решить проблему соответствия Поста (залача 2(в)) только с уславнем, что во фразе на допусхиюнся ноыпаргния слов.
(Предупремдение: возможно, чго ваши алгоритмы лля неноторых иэ этих задач булут очень неэффективными ) 5. Процедура, которая абращаетса к самой себе, называется рекурсивной. Часто используется следующий зарпаш рекурсии. Скажем, мы хотим оешнть ннднвипуальную задачу размера и. Если п мало ю инднаидуальную задачу решить легко. В противном случае нам пожег бып известно, как решить индивидуальную задачу, имея решения одной или более игиьигих индивидуальных задач. При этом мы получаем решения этих меньших задач, вызывая ту же процедуру.
Пусть, например, нам дано и н требуется вычислять п]. Если п=-О, то, естествен. но, п1= 1. В противном случае предположим, гго мы уже вычислили (и — 1)!в решеняа меньшей задачи. Тогда можно получить и1, умножая (и†!)' на п. Ого~ела вытекает слепующий рекурсивный алгоритм: ргосейиге фанториал(п) В и=О !пеп ге(нгп 1 е1зе ге]нгп п факториал(п — 1] а) Проследите шаг за шагом эа вычислением факториал(3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
