Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 36
Текст из файла (страница 36)
б) Приведите рекурсивную программу лля решения задачи а Ханойской башне (залача 1(б) нз гл, !). в) Можно использовать рекурсию для гортировхи массива, содержащего 2" различных целых чисел (т.. лля перестановки нх в неубывающем порядке). Идея состоит в следующем. Доволыю легко слить лва отсортированных массива в единый отсортированный массив. Поэтому если первая н вгорая половнны массива отсортнрованы, то легко отсортировать сам массив.
Длв сортировки этих Лвух половин можно использовать рекурсию. ма заза Гх. В. Алгоритмы и сложность 194 г«] Основываясь на ал> орптме из п. н), покажите, что массив нз >у элементов можно отсортировать зз «реня 0(>У !ой >У). 6.
Докажите, по а) (!ой л]"=0(л«) для всех целых Ф и всех в)О; б) 2«+>~~2«. г) (!ой л) !«я "=!>(лз) для всех целых и. 7. Пусть функции / и В определяются следующим образом л", если л простое, [ ль з противном случае, >Р, если л нечетио, В (л) =- ! ! л' н противном случае. Какие из следующих соотношений справедливы2 а) /(л), п(л)=й (лз), б) /(л)=-0(В(л)). в) пр>)=0(/(л)). 8.
Допустим, что в симплекс-алгоритме, приведенном на рис. 2.3, всегда выбирается столбец /, для которого с <О является наименьшим. Покажите, что, используя это правило, симплекс-алгорн>м прнченнв одну операцию >зменге ния, решил бы зздзчу ЛП (8.2) 9. Допустим, что з симплекс.алгоритме, приведенном на рис.
2.3. всегда выбирается тот столбец 8 ко>орый после применения операции замещения прн. водит к наибольшему уиеньшеншо стоимос>з. Покажи>с, что, испол>,зуя это пра- вило, снмплскс.злгорнгм. применив одну операцию замещения, решил бы за- дачу ЛП (8.2). !О*. Допустим, что в симплекс. алгоритме. приведенном н«рис 2 3, столбец / выг>ирается слрчадныхг ооразом и с равной вероягностыо среди всех столбцов, для ко>орых сук О. Покажите, что при испол~зовании этого правила матгмати мског ожидание числа операпий >вмещения, применяеъпкх симплекс-алгоритмоч при ре>ненни задачи ЛП (8.2„«сть 0(л). 11. Докажите лел>му 8.8. 12. Дока>ките лемму 8.!О. 13*. Итера>гия алгори>ма эллипсоидов вычисляет новый эллипсоид Ер„г, содержащий полузллнпсоид — Е/ [а[ =Е/П[х~/2«.
а' (х — / ] т'. о' ! Покажите, что по формулам Ва !/ гг=!/ — — = > лз Г 1о;лй 2 (В/и) (ВЛ>) /ьт> и' — ! ~ у л+1 !+д аВ/а где а=(а'х — Ь)/ЭГи'В а, можно вычислить новый эллипсоид Е(э>, содержащий множество — Е([а]=Е П(х~/2«> а' (х — //) ~ В]. 1 2 (В примере на рис. 8.6(а) это множество совпадает с меньшей областью, отрезаемой от Е пунктирной линией.) Докажите, что эта модифицированная итерация корректна в том смысле, что теорема 8.4 остается для нее сира.
ведливой и что она может существенно ускорять сходимость в методе эллипсоидов. 7(оммснтараа и ссылки 195 14. (Метод эллипсоидов в виде проглззедския.) Напомним следующее равенство из доказательства леммы 8.!3; В, гтоВ(зг()т Это равенство можно переписать в виде 37„= Е,)(,В, где 1) з3 г)7 =Вг для всех 1 2) О=6(ай( —,, ..., ) ! 3) (47 — это вРащение, зависЯ щее от О . и пеРеводЯщее г7 а в Ц () лч((, О,...,О). Основываясь на этом равенстве, докажите, что ()7 можно представить в виде ОзД'"! Рг, и приведите явную формулу, выражающую сомножитель р, через а и ()р 15. а) Пусть эллипсоид Е=(х: (х — ()' В ' (х — 1) (1) содержит некоторый шар радиуса г.
покажите, что тогда он содержит шяр (х:(х — 1)' (х — г)(гз). б) Рассмотрим п-мериып симплекс в Азл с вершинами иш ..., суо Пусть э ч~р. гу((п+!) — центр тяжести этого симплекса, и допустим, что все )=о су — рациональные числа, знаменатели которых не превосходят 2Г. Покажите, что существует шар с центром с, и радиусом г=2-зчг, целвком лежащий внутри симплекса.
2) Выведите из п. а) н б] след)поше~ утверждение. если система СЛН имеет решение и эллипсоид Е заведомо содержит асе решения, лежащие внутри шара 1, 'х():а п2г, то любая точка нз границе Е отстоит от центра Е не менее чем на 2 16. а) Покажите, что если (гзу) — врлшеннс, то ~,=, гг;=1. б) Используя п, з) и задачу 14, покажите, что все элементы г вектора (у и матрицы Ву в алгоритме эллипсоидов удовлетворяют неравенству ) г(~ ~ 2<з! з! !оя «+зг. Комментарии и ссылки Машины Тьюринга как формализация понятия алгоритма были введены в работе (Ти! Тиг!пй А. М. Оп Сотри1аЫс НшпЬегя, тий йе Арр!!са(1оп 1о ап Еп1ясйе1- бипйяргоЫет, Ргос.
(.опбоп Май. 5ос., 5ег 2, 42 (1936), 230 — 265. Согг(йепбшп, зЬЫ, 43 (1937), 544 — 546. Т(ругие (эквиналентные) модели алгоритмоа предложены в работах (Ро) Роя1 Е.!.. Еоггпа! Вебис!(опя о1 йе Оепега) СотЫпа1ог(а! Пес!я(оп РгоЫет. Атег. 3. Май., 65 (1943). (Ма) Марков Л. А. Теория алгорифмов.— Тр. Матем. ни-та АН СССР им. В, А.
Стеклова, 1954, 42. (Е)т! Е1йо! С. С., ЕоЫпяоп А. Рапбот Ассеяя 5(огеб Ргойгат МасЫпея, Л. АСМ, 11, 1(о. 4 (19641, 365 — 399 Примечательно, что полипомиальнзлй алгоритм в л|обой вз этих отличных друг от друга моделей можно перевести в полиномнзльпый алгоритм в любой другой модели. См., например, гл. 1 а ките (АН()) Айо А.
т'., Норсгой 3. Е., ()1(тап 3. О. Тйе Оемйя апб Апа)умз о1 Сотри1ег А!бог(йтя. Веаб!пйя, Маяял Абб(яоп-%ея(еу РиЫВЬ!пй Со., 1пс., 1974. уэ !96 Гл. 8, Алгоритмы и сложногть (Имеется перевод: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислителысых алгоритмов.— Мл Мир, !979.! Дихотомию между полнномиальными и экспоненциальными алгоритмами можно проследить, что давольно интересно, да Джана фон Неймана, отца современной вычислительной машины. (ч)4! чоп Ыепшапп Л.
А Сег(а!и 2его-5пгп Тва-Регзоп Оагпе Ецшча)еп1 1о йе ОрНша! Азз!йпшеп! РгаЫеш, сп Соп1пЬцИапэ 1о йе ТЬеогу о1 Оашез П, ес[. Н. сЧ, Кпйп апб А, ссс. Тпсйег Рппсе1оп, ЬЬ йл Ргспсе1оп 1)п]ч Ргеш, 1953. Более явно о полинамиальных вычислениях впервые сказано в работах [Со[ СоЫсагп А.
ТЬе !п1гспжс Согпрп1а1!апа! О!11!спйу о1 РцпсНопз, рр. 24 — 30 !п Ргос, 1964 (п1. Сопйгезз !ог 1ой!с Мейаба!ойу апб РЫ1. о] 8с)епсе, ей. У. Ваг.Н)Ие1. Ашз1егбаш: Могй НаИапд, 1964. [Ед! ЕсЬпопбз 3. Райэ, Тгеез, апй Р!авета, Салай. Л Май., 17 (1965), 449 — 467, Результаты й 8.6 взяты из рабаты [КМ! К!ее Ч., М]п(у О, 3.
Нотч Особ В йе сйпср!ех А1йопйгпр рр. 159 — 175 сп 1пецпаИ(сез )П., ед. О. 5Ь!зйа. Мев Уотерс Асадеш!с Ргеш, 1пс., 1972. Патологические примеры с экспаненциальным числом замещений существуют для вариантов симплекс-алгоритма, в каторьж выбирается самый отрнцагельный столбец (задача 8), столбец, дающий наибольший выигрыш стоимости (эадача 9), и для других вариантов; [Яе[ Зегаз!ов И. Л ТЬе Ыгпр!ех а!Хогййгп в!й йе р!чо1 гц)е о1 снах)гп)ыпй спр 1ег!оп !гпргачегпепс, ()!зсге1е Май., 4 (19731, 367 — 378, а также для прямо-двойственного алгорвтма и его вариантов: [Ха!! ХзбеЬ Н А Ьаб ссе1вогй ргаЫеш 1ог 1Ье юшр!ех шейой апб ойег ш!п)шшп соэ1 Иов а!йогИЫпь, Май.
Ргой. 5 (1973), 255 — 266. [Ха2! Хабсц ЬЬ Маге райо!ой!са! ехашр!ез 1ог пе1вог1с Пов ргоЫешь, Май. Ргой,, 5 (!973), 217 — 224. Истоки алгоритмы эллипсандов восходят к более общему методу Шара: (Шо)! Шор Н, 3. Использование операции растяжения пространства в задачах лсинимизации выпуклых функций.— Кибернетика, 1970, № 1, с, 6 — 12. Алгоритм эллипсондов для выпуклых — не обязательно линейных — ограничений был описан в работах ДИо2! Шор Н. 3. Метод отсечения с растяжением пространства для решения задач выпуклого программирования.
— Кибернетика, 1977, № 1, с. 94 — 95. [ЮН]Юдин Д. Б., Неинравский А. С. Информационная сложность н эффективные иетоды решения выпуклых экстреиальных задач.— Эканаьссска и математические методы, 1976, т, !2, вып. 2, с. 357 — 369. Важные следствия этих результатов для линейного программирования были впервые уназаны в работе [Ха! Хачиян Л.
Г. Полнномиальный алгоритм в линейном программированин.— ДАН СССР, 1979, т. 244, № 5, с. 9393 — 1096. Наше изложение алгоритма эллипсоидав следует работе [А5! Азрча11 В., клопе И. Е. КЬасЫуап'з Ипеаг ргойгашш)пй а!йогИЬш, йопгпа( а( А!цапйгпз, 1, Но. 1 (1980). Несмотря ны большое теоретическое значение алгоритма эллипсаидов, совсем не ясно, может ли он быть полезен нз практике. Наиболее очевидным среди боль- 197 Комментарии и са«лки шаго числа препятствий является гребование большой точности вычиСЛенИй. С другой стороны, нет убедительных внд«елы:гв в пол~зу гого, что алгоритм эллнпсоидов (и все его возможные усовершенствования) заведомо не может использоваться на практике 1!екоторые нэ тих аспектов обсуждаются в работах [0а! Оап1з!й С.
В СопипепИ оп КЬас)<<а< '» а)дог<!пи< (о< 1<пеаг ргойгагпш1пй, Тесйп)са) («ерог! ВОЬ 79 — 22, Оер1 о1 Орегаыопл Реьеагс)з, 5(ап1огд ()и!ч., ! 979. [ОТ! Оо1гИагЬ О., Тодд М. Л МоддюаИопл апд ипр!егпеп1а(юп о1 Гпс 5сйог— КЬас1нап а(оог(!Ьш 1о< Ипеаг ргойгашпипй, 0ср1, о1 Со<при(ег 5сзепсе, СогпеИ Уп!ч., 1980 Некоторые следствия алгоритма эллннсондов для вопросов сложности в комбннаторной оптимизации исследуются в работах [КР! Ка;р К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
