Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 99
Текст из файла (страница 99)
Сколько независимых испытаний нужно провесгн, чтобы иметь большую уверенность в ра- боте алгоритма чем в работе вычнслигельной машины? 11. а) Установи ге соотношение (19. !6), оненнвающее мощность множест. ва Е'. б) Покажите, что [Р'[>2!" 12. Сформулируйте следующие задачи как дискретные линейные задачи о подмножествах. а) Задача о кратчайшем пути. б) Задача о потоке минимальной стоимости. в) Задача о множестве максимального веса в матроиде. г) Задача о взвешенном пересечении матроидов, д) Задача о взвешенном пересечении трех мшроидов.
13* [5!тУК). Предполоким, что [гг?] — матрица свячностей для неориен- тированного ~рафа 6 =(У, Е), и мы хотим проверить выполнение неравевств гг ) зу нрн всех !, / дла анной матрицы требуемых связностей [з!/), а) Докажите следующее утверждение: если г ~ ~заь гь ~~ заь для вершин ты тз, ..., шг ь, отличных от а, Ь н друг от друга, то аь' гаь ~~ Заь.
б) Покажите, что в том случае, когда зО? й для всех 1, /, результат нз и. з) позволяет проверить связности в графе, используя не более чем л([ У [ — (й+1)/2) проверок. Гж 19, Локальный поиск в) Покажите, что если Х-зацепа в допустимой сети, при которой удаляются ребра [1, ьч) и [1, 1), нарушает допустимость, а именно г,а становится меньше, чем з„ь, то либо гг < з,ь, лаба г г < з,а. !4. [Р51].
Покажите, что если Р м тг*Р, го ннкайой алгоритм локального аоиска для ЗК с полиномиальной врсменнбй сложностью каждой итерации не может давать е-приближенных обходов для любого фиксированного е > О. !5" [%5В). Покажите, что для произвольного обхода и городов число смежных с ним обходов в его минимальной точной онрестности энспаненциальио относительно л. 16. а) Покажите, что А(н з ие является точной системой окрестностей для ЗК с и городами. б) Покажите, что !у„ 1 †точн система окрестностей. Комментария к ссылки й 19,2 [Во] Вас)г Р.
Ап А!йогИЬв 1ог Бо!ч!пй Тгачейпй-Ба!еяпап апб йе!а1еб Ь]е1погй Ор1!в!га((оп РгоЫевя ргезеп(еб а1 !Ье 1оиг(ееп!Ь )4алопа) МееИпй о[ Ьйе Ор. йез. Бос. о1 Авепса, 51. Ьои!з, М!ягюг! (Ос1. 24, 1958). [Сг) Сгоез О. А. А МеЬЬоб (ог Бо1ч!пй Тгачейпй-Ба1езвап РгоЫевз, Ой, 6, Но. 6 (ЫочевЬег — Оесебгйег 1958), 791 — 812. [ЬИ] 1.!п 5. Соври1ег Бо)ыюпз о1 1Ье Тгачейп95а1еяпап РгоЫегп, ВБТЛ, 44, Мо. 1О (ОесевЬег 1965), 2245 — 2269. [НК1! НеЫ М. апб й.
М. Катр. А [)упав!с Ргойгапып)пй Арргоасй 1о Бейиепс!пй РтоЫевз, Л. Б!АМ, !О, 5[о, 1 (МагсЬ 1962), !96 — 2!О. Одно из наиболее ранних описаний локального поисна можно найти в [[)РРЫ] Оипйав В., Рг!бзйа! О., Ргьйзпа) й., Ыог(Ь Л. Н. (Лез!Эп Ьу Ь]а!ига) Бе!еслоп, 1ВМ йез. ()ер!. ЙС-476, Липе 20, 1961. $19.3 [51йгК] Б(е)ййдг К., %е!пег Р., К!ейвап О. Л.
ТЬе Вез(йп о1 М!п(гпа! Соз( Бит. ч!чаЫе Ые(яогйз, !ЕЕЕ Тгапз, С!г, ТЬеогу, СТ-16, Но. 4 (1969), 455 — 460. 4 19.4 [йрйБК) йо1ЫагЬ В., Ргапй Н., йозепЬаив О. М., 51е!8И(г К., К1ейвап ]), Л. ОрИгпа! Осч!йп о( ОИзйоге Ыа!ига)-Оиз Р!реИпе Буз!епгз, Ой, 18, )чо. 6 (Ыо. чепгЬег — ОесевЬег 1970), 992 — 1020.
$19.5 [КЬ] Кегп!ййап В. %., Ып Б. Ап Е(лс!епг НеигмИс Ргоссбиге 1аг Регкпоп!пк Огарйз, ВБТЛ, 49, Ыо. 2 (РеЬгигу !970), 291 — 307. И.К] ЬИп 5., Кегп(ййап В. %. Ап ЕИеслче Неигвйю 1ог !Ье ТгачеИпй-Ба1еяпап РгоЫепг, Ой, 21 (1973), 498 — 516, $19.6 [Ог) Ога1гег Р.
Л. Соври(ег Бо!иИоп о1 Ьагйе МиИ!совгпобйу Р!огч РгоЫевз (неопублинованная диссертация, Рг)псе(оп ()п!чегзку, Бер1ептЬег 1970). [ОЯ Ога1гег Р. Л,, Б!е(йИ!г К. А НеипзИс АрргоасЬ 1о 1 агйе МиИ!сапипабйу Р!огч РгоЫегпз, Ргас. Бувр. Соври(ег-Сагппшп!са(юпз Ые!яогйз апб Те1е(гаИ!с, М!сгогчаче йез. 1пз(. Бувр. Бепез, Чо!.
ХХН, Ро1у1есйп!с Ргея Ь]. 'г'. (1972), рр, 311 — 324, [Кг) Кгопе М. Л. Неигьй!с Ргойгаппп!пй АррИеб 1о Бсйебийпй РгоЫевь (неопубликованная диссертация, Рг!псе1оп 1)п!чегзцу, Бер1евЪег 1970). Коммзи вар и и и ссылки 499 [КЯ Кгопе М. Л„Б(е)8П(з К. Непг!зИс-Ргойгагпв!пй Бо!п$1оп о1 а Р!омзйорБсЬебилпй РгоЫегп, 0$$, 22, по. 3 (Мау — Лопе 1974), 629 — 638. [О1] Оо!бз(е)п А. Л., ).езй А. В. Сопипоп Рва[иге Тесйпщиез 1ог 0ьсге1е ОрИгпЬ хаИоп, Сопгр.
БсЬ Тесй. $(ерог$27, ВеП Те!. 1.аЬз. (Магсй )975), [5$)г] Яе!9И[х К., $!!е!пег Р. Бопге 1вргочеб А!йоп(йвз 1ог Соврп$ег Бо1иИоп о1 (йе Тгаче!Ипй Ба)езвап РгоЫев, Ргос. 5$х(Ь Айя[оп Соп(. оп С)генц апг! Буз(егп ТЬеогу, 1)гЬапа, [И$по!з (1968), 814 — 821. й 19.7 [По] $(осйа1еПаг П. Т. Сопчех Апа1уяз. Рг1псе$оп ЬИ Лл Рг!псе(оп $)п!ч. Ргезз, 1970.
[Имеется перевод: Рокафеллвр Р. Т. Выпунлый анализ.— М.: Мир, 1973.] [Ра2] РарадппППоп С. Н. ТЬе Аб]асепсу Пе)а(!оп оп Ве Тгачелпй Ба)еяпап Ро1у$оре И й(Р-Совр1е(е, МаПь Ргой., 14 (1978), 312 — 324. [Ба1] Бачане Б. Ь. ТЬе Боик!ап о1 0исге1е Ь)пеаг ОрИппгаИоп РгоЫеим Ьу Ие)ййЬогйооб Бевгсй Тесйпщоез, Уа1е ()и!четв!!у, Липе 1973 (неопубликованная диссертация).
]Ба2] Бачайе Б. Ь. Багие ТЬеогеИса! 1врПсаИопз о1 Ьоса! Беатой, МаИк Ргой., !О (1976), 354 †3. [ч)гБВ] %е!пег Р„Бачайе Б. 1., ВайсЫ А. Ие19ЬЬогйооб Беатой А!бог)(йгпз 1ог Опагап[ее!пй Ор1ппа! Тгвче!!пй Ба)еяпап Тонге Моз1 Ье 1пе[1!с!еп$, Л. Совр. Буз. Бей, 12 (1976), 25 — 35. ]Ба%К] Бачвде Б. 1., Фе)пег Р., Кгопе М. Л. Сопчегдеп().оса! 5еагсЬ, Псз. )(ерог$ !4, Оер$. Совр. Бей, Уа!е ()п!чегз1$у, Ь)ем Начеп, Сопп. (1973). ]КР] Катр П. М., Рараб!в)(г!оп С. Н.
Оп [Ппеаг СЬагас1епха(юпз о( СовЫпа1опа1 ОрИв!хаИоп РгоЫевз, Ргос. Тмеп)у-Р)гз$ Апина! Бувр. оп Гоппба1юпз о1 Совр. Бс1., 1ЕЕЕ (1980), 1 — 9. 4 19.8 ]Ра1] Рараб)влг)ои С. Н. ТЬе Согпр!ехпу о1 СовЫпа[ог!а) ОрИпнгаИоп РгоЬ1епи (неопубликованная диссертация, Рппсе1оп 1)вчегзПу, Аннов(1976). [Р51] Рараглпи$гюн С. Н., Яе)9[Па К.
Оп (йе Согпр!ехйу о1 !.оса! Беагсй [ог (йе Тгачеппс Ба!еяпап РгоЫев, Л. 51АМ Согпр„б, 1 (Матей 1977), 76 — 83. Дополнительные кеммектерии и ссылки В литературе описаны приложения локального поиска и н другим задачам. В следующих источиинах сообщается о благоприятных результатах прн разработке механических передач, таких, как привод печатного стола в механизме печатной машины: [[Р] Ьее Т. %., Ггенбепз1е)п Г. НенизИс СовЫпа(ог)а! ОрИвиаИоп !п (йе К1- пегпаИс 0еяйп о1 Месйапипм, Раг$ И ТЬеогу, Раг1 2: АррпсаИопз, Лопгпа! о( Еп91пееппй 1ог 1пбоз1гу, 98, по.
4 (ИочевЬег 1976), 1277 — !284. [Ш Ьее Т. )ч'., Ьапйгапа Ь). Неиг!з$!с Арргоасйез 1о (йе 1пчегзеб 0упав1с 1!пйайе РгоЫевз: Уч'$$Ь Брес1а! Арр)гоаИоп $о В!овесйап)сз, Ргос. ГП(Ь Тьгог)б Сопйгвз оп ТЬеогу о1 МасЫпез апб Месйап!япз, Рарег Мо. $)БА-53, Моп1геа1, Сапаба (Лп1у !979). Построение сетей малого диаметра, рассматривавшееся в задаче 7, описано в работе [ТЯ Тоней Б., 5$е!н!Пх К. ТЬе 0ез!йп о( Бвал-О!аве(ег )Че(могйз Ьу Ьоса! БеагсЬ, 1ЕЕЕ Тгапз. оп Соврн1егз, С-28, Но.
7 (Лп)у 1979), 537 — 42. Задачи 8 и 9 взяты из статьи [Р52] РарагкгпПИоп С. Н., Яе19!Пг К. Бове Ехавр!ез о( 0ПИсиП Тгвчекпа Ба!еяпап РгоЫевз, ОП, 26, $4о. 3 (Мау — Лопе !978), 434 — 43. Гл. 79. Локальный поиск Задача о равномерном разбиении графа (см. задачу 1) — зто вариант задачи о минимальном разрезании на ограниченные множества; доказательство ее МР- полноты см. в работе (СЛБ) багеу М, К., ЛоЬпзоп О.
Б., Б(ос)гпгеуег Е. 2. Боте Б!горИПеб ПР-Сопи р!е(е Сггар)г РгоЫегпз, Т(геог. Согпр. Бс!., ! (1976), 237 — 67. Задача !6(б) основана на теоретико.графовом результате, впервые высназанном в начестве гипотезы Ликом )ь!) и доказанном в работе [ТН) Тйогоазоп А. Сг. Наго(Иоп!ап Сус!ез апб ()п!9не!у Ебде Со1опгаЫе Сггар)гз, Аппа(з о1 0(зсге1е Ма1Ь., 3 (!978), 259 — 268. Предметный указатель Ал Ал гол Упрощенный 27 горитн АЛЬФАБЕТА 152 асинптотнчески оптимальный 285 Бленда 58 двухэтапный 63 Дейкстры 1ЗЗ декомпозиции 104 дерева 426 для задачи МОД второй 286 — — о пересечении матроидов 307 ДОСТРОЙКА 147 допустимый относительно задачи 145 ДП-1 432 ДП-П 434 ДП-П1 435 ДП-!Ч 439 дробный двойственный для задачи ЦЛП 340 жадный для задачи ЛМВ 288 — — натроидов 291 Крнсшофндсса 429 локального поиска 467 НАЙТИПУТЬ 203 недопустиный относительно задачи !47 ПОИСК !99 построения взвешенного паросочетания 270 — ыаксинального потока 2!5 — минимального погонного дерева 282 — паросочетания в двудольнон графе 229 — — — произвольном графе 244 проверки удостоверения 359 пряно-двойственный 106, 1!1 прямо-допустимый 145 псевдополинониальный !97, 401 рекурсивный 220 сильно полинониальный !97 Флойда — Уориилла 136 Форда — Фалхерсома 127 ЦИКЛ 143 зллипсоидов для задачи СЛН 182 — нодифицированный 189 — е.приближенный 421 Алгоритмы 160 — вероятностные 413 — отсекающей плоскости 336 — — — прямые целочисленные 350 — переборные 336 — поланониальные 168 — приближенные 413 — псевдопатнноыиальиые 168 — субэкспонеициальные 168 — экспоненцнальные 168, 413 Алназ 493 Антидерево 414 Арифметическая операция 166 Базис 295 Базисное допустимое решение ~бдр) 34 — — — вырожденное 45 Беглец 193 Блок 28 Булеза переменная 323 Булевы формулы 323 — — выполнимые 323 Вентор лексикографически отрицательный 344 — — положительный 344 Вектор цен 101 Вектор-столбец 25 Вектор-строка 25 Венгерский метод 254, 258 — — в матричной форме 259 Вершина 25, 40 — вырожденная 245 — живая 450 — мертвая 449 — смежная 25 — степень 25 — — захода 25 — — исхода 25 Вершинная связность 470 Вершины внешние 224 — внутренние 224 — объединенные в пары 224 7?редметный ркаватель — свободные 224 — сети 139 — смежные 65 Веса 287 Ветвление 449, 450 Внутренность многогранника !81 Вполне унимодулярность 256 Вращение 181 Время выполнения 319 Выделенный символ 359 Выигрыш 423, 479 Выпуклая номбинация 18 — — строгая 18 Гамильтонов путь 310 — маршрут 444 Гипергрань 40 Гнперплоскость 38 — опорная 40 Грани 39, 4!5 — смежные 415 Граница см.
Пропускная способность Граф 25 — биориентированный 250 — взвешенный 27 — — полный 27 — двойственный 414 — двудольный 26, 223 — двусвязный 220 — диаметр 497 — Дирихле 3!2 — допустимый 266 — насыщенный 165 — ориентированный сль Орграф — планарный 3!2 — разреженный 165 — хордовый 414 — эйлеров остовный 424, 426 — й.регулярный 497 Действительная прямая 24 Дерево 26 — остовное 27 Дефицит 471 Дизъюнкты 323 Динамическое программирование (ДП) 432 — — для задачи о кратчайшем пути в слоистых сетях 461 — — и ЗК 463 Дихотомия 322 Доминирование 456 Дробная часть числа 339 Дуга обратная 125, 208 — прямая 124, 208 Дуги неособые 130 — особые 130 Задача ВЕРШИННОЕ ПОКРЫТИЕ 373, 418 — — — алгоритм 1 4!8 — — — — 2 421 — ВЫПОЛНИМОСТЬ 357 — выпуклого программирования 9 — ГАМИЛЬТОНОВ ЦИКЛ 394 — ГАМИЛЬТОНОВА ДОСТРОЙКА 416 — главная 102 — ГОМЕОМОРФИЗМ ПОДГРАФУ 415 — двойственная (Д) !О? — — к ограниченной прямой (ДОП) 108, 110 — ДОПОЛНЕНИЕ ГАМИЛЬТОНОВА ЦИКЛА 394 — — ЗК 395 — — СВЯЗНОСТИ вЂ” ИЗОМОРФИЗМ ПОДГРАФУ 403 — индивидуальная комбинаторная 354 — КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ 390 — КЛИКА 358 — коммивояжера (ЗК) 11, 12, 359, 453 — — евнлидова 423 — — как задача ЦЛП 317 — — с неравенством треугольника 423 — линейного программирования (ЛП) 9, !3 — — — а канонической форме 31 — — — — общей форме 3! — — — — стандартной форме 31, 32, 175 — — — двойственная 73 — — — индивидуальная общая 30 — — — прямая 73 — ЛИНЕЙНЫЕ НЕРАВЕНСТВА (ЛН) 396 — МАКСИМА)!ЬНОЕ ПАРОСОЧЕ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
