Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 96
Текст из файла (страница 96)
~!8.5), а на этапе П ищутся изменения, которые лежат вне этого класса. Веб. Общие аоаекоик локального аоиека Керниган и Лин 1К1) также обсуждают двухэтапный метод для разбиения графа. Они разбивают каждое из множеств А и В в локально оптимальном разбиении на две части А=А,()А, и В=В, 11 В„используя снова локальный поиск, а затем берут раз- биение А, (1В„А,(1В, в качестве нового начального решения. Это основано на эмпирическом наблюдении, согласно которому если лхп-разбиение локально (но не глобально) оптимально, то для по- лучения глобальной оптимальности требуется поменять местами множества мощности около и!2, Лин (И в своей работе 1965 г.
разработал идею, названную сведением. Она основана на том наблюдении, что в конкретных за- дачах некоторые черты присущи всем хорошим решениям. Это мож- но рассматривать как выражение «легких» частей задачи. Страте- гия, разработанная Лином для ЗК, состоит в получении несколь- ких локальных оптимумов и последующем нахождении ребер, общих для всех этих решений. Затем эти ребра фиксируются, в результа- те чего время нахождения новых локальных оптимумов уменьшает« ся. Дальнейшее развитие эта идея получила в работах ().К) и (ОЦ. Как обычно бывает с эвристиками, можно высказать также пря- мо противоположное соображение. Если такие общие черты обна- ружены, то они скорее запреиленноге, чем фиксированные.
Обосно- вание этого таково: если мы опасаемся, что глобальный оптимум избегает нас, то это может быть связано именно с тем, что нашу эв- ристику «обманывают» эти заманчивые черты. Запрещение их мо- жет наконец вывести нас на правильный путь к глобальному опти муму. В работе (5%) это называется огпказом. Еще одна идея, отмеченная в (ЕК), основана на том факте, что когда находится много локальных оптимумов, то среди них очень часто встречаются повторения.
Кроме того, при поиске большая доля времени тратится, по-видимому, на проверку оптимальности каждого локально оптимального решения путем безуспешного просмотра его окрестности. Этого можно избежать, если хранить список ранее полученных локальных оптимумов и их стоимостей и в процессе поиска сравнивать текущие стоимости с локально оп- тимальными стоимостями. Если обнаруживается решение, стоимость которого совпадает с некоторой локально оптимальной стоимостью, то можно посмотреть, ие совпадает ли это решение с ранее найденым локальным оптимумом. Если совпадает, то его проверку можно про- пустить. Для такой проверки нужно использовать какой-нибудь эффективный метод, если мы хотим в целом сэкономить время (см. задачу 5).
Описав отдельные важные практические вопросы применения локального поиска, обратимся теперь к некоторым его теоретичес- ким аспектам. Гл. 19. Локплькиа поиск 19.У Геометрия локального поиска Локальный поиск очень тесно связан с симплекс-алгоритмом; в действительности его можно считать идентичным симплекс-алгоритму на соответствующим образом определенном многограннике. Для обоснования этой идеи введем понятие дискретной линейной задачи о подмножествах.
Определение 19.7. Пусть Ж=(1,...,п), и пусть Р~2н — семейство подмножеств множества У, причем никакое множество из Р не содержится строго в другом множестве. Дискретная линейная задача о подмножествах (ДЛЗП) (Р, й) — это комбинаторная задача оптимизации с допустимым множеством г и стоимостью с6)=Х~сгдо 1Е Е, где Й=(дь...,д„) — заданный вектор весов в 1Е".
Многие важные комбинаторные задачи оптимизации являются ДЛЗП. Пример 19.4. ЗК является ДЛЗП. Пусть и — число ребер в полном графе 6, и пуоть Е содержит в точности множества целых чисел (имеется в виду, что ребра представляются целыми числами), которые соответствуют обходам в О. Вектор стоимости с( — это просто вектор весов ребер, т, е, векторное представление матрицы расстояний. Пример 19.5.
Задача МОД также является ДЛЗП, в которой Р содержит в точности те множества ребер, которые соответствуют остовным деревьям. П Аналогично, в виде ДЛЗП можно сформулировать задачу о кратчайшем пути, некоторые задачи о матроидах, а также многие другие задачи. ДЛЗП тесно связаны с системами подмножеств, описанными в гл. 12. Допустимую точку 1Е Р можно рассматривать как точку из )го, в которой каждая координата 1 равна либо 1, либо О, в зависимости от того входит или соответственно не входит 1 в 1.
Не опасаясь недоразумений, мы будем использовать 1 для представления как множества 1" ~ Р, так и этого и-вектора. Таким образом, г" можно рассматривать как множество вершин единичного куба в 1с" со стоимостью до). Любую точку 1о ~ Е можно сделать единственным оптимальным решением в г, положив О, если ~,=1, с(! —— 1, если Г;=О, поскольку при этом стоимость 1о равна О, а стоимость всех остальных 1 не меньше чем 1, ибо, согласно условию из определения 19.7, никакое допустимое множество не может строго содержаться в другом. Это означает, что через точку 1,9 )го можно провести гипер- 19.7.
Геометрия еояаяьяоео яоиека 487 плоскость (а именно ь('х=-О) так, что все остальные точки из Р окажутся по одну сторону от этой гиперплоскости (2'()О). Таким образом, никакая точка !" не является строгой выпуклой комбинацией других точек, и, следовательно, множество Р состоит из вершин некоторого выпуклого многогранника Я". Рассмотрим далее выпуклую оболочку СН(Р), которая предетавляет собой многогранник в положительном гипероктанте в Яя, множество вершин которого в точности совпадает с Р.
Так как минимальное значение линейной функции ь('! достигается в некоторой вершине множества СН(Р), то исходную задачу ДЛЗП можно рассматривать как задачу минимизации о'! на многограннике СН(Р), т. е, как задачу линейного программирования. Многогранник СН(Р) всегда можно представить как пересечение конечного числа полупространств, т. е. как систему неравенств а!х(Ьо ь'= 1, ..., и, х)0, и, следовательно, ДЛЗП можно представить как вледующую зада чу, которую мы будем называть ЛП!.
ппп е('х, Ах~,Ь, (19,15) х>0, с допустимым множеством Р,ыН". (Доказательство того, что многогранник можно так представить, см. в !Ко, теорема!9.1!. Это одно из тех интуитивно очевидных геометрических утверждений, доказательство которых отнюдь не тривиально.) На первый взгляд кажется, что мы совершили большое дело— свели произвольную ДЛЗП, которая вполне может быть НР-полной, к задаче линейного программирования. Однако нужно более внимательно посмотреть на это сведение и решить вопрос, как по множеству Р получать матричное представление в задаче (!9.15).
Никакие методы сразу не приходят в голову, и поэтому мы начинаем подозревать, что эта задача в общем случае является трудной. Это подтверждается результатом из работы (КР), где показано, что если НРчьсо-ИР, то ни для какой УР-полной ДЛЗП не существует полиномиально краткой характеризацни строк матрицы А. Кроме того, в (Ра 2! показано, что для ЗК определение того, представляют ли два обхода несмежные вершины многогранника СН(Р), само является ЮР-полной задачей. Продолжим интерпретацию ДЛЗП в виде задач ЛП и получим две характеризации отношения смежности в многограннике СН(Р), первоначально предложенные в работах (За!, За2, ьЧЯВ, Ба%К!.
Чтобы воспользоваться тем, что мы знаем о вершинах и смежности из симплекс-алгоритма, обычным способом добавим Гл. 19. Локальныд лоиск к ЛП, переменные недостатка и перейдем к задаче в )тл+'л, получая стандартную форму ЛП, с допустимым множеством Р,~Й"+: ппп д'х, Ах =Ь, (19.16) х)0, где д=(й10 ),А = [А11 ], х=(х)ео ..., е„). (Вспомните обозначение из равд. 2.3.3.) Определим преобразование точки х Е Р, в соответствующую точку хЕР.: рл х- (х)Ь вЂ” Ах) =х, и обратную проекцию из Р; в Рб и; х — (первые и компояент х) =х. Отметим, что каждую точку х Е Р, можно однозначно представить в виде рх, где х Е Р, и х=лх.
Далее нам потребуется лемма, которая связывает отношения смежности в Р, и Р,. Лемма 19.2. Пусть х, у — две различньм вершины в Р;. Тогда рх и ру — различные вершины в Р,. Кроме того, х и у смежны в Р, тогда и только тогда, когда рх и ру смежны в Р,. Доказао~ельство. Предположим, чтох является вершиной, а рх нет. Тогда рх можно представить в виде )лх — ((сй + ро), ! где ри и ро — различные точки в Рь Тогда х=(й+о)12, поэтому и = о„откуда следует, что )лй =(хй — противоречие.
То, что руру, если х~ у, следует непосредственно из определения р. Покажем теперь, что ссли х и у смежны, то (лх н (лу также смежны. Предположим, что это не так. Тогда произвольную точку рг на отрезке (,=[ух, (су] можно представить в виде рг=-(уй+)лй)л2, где ри и ро не лежат на 1,. Тогда г=(й+й))2, где и и о не лежат на Е=[х, у],— противоречие. Аналогично доказывается, что если рх и ру смежны, тох и у также смежны. Д Теперь мы можем установить первую характеризацию отношения смежности.
Теорема 19.2. Пусть некоторая ДЛЗП порождает соответствУюи(Ую ЛПг (19.15) так, как описано выше. Тогда две Раз- 19.7, Геемеврия локального ньиека личньче вершин г х, у ~ Р, смежны в том и только в пюм случае, если суп!ес ует пикой вектор стоимости й, что х является единственной оптимальной вершиной и у — вторая по стоимости вершина. Доказательство. Докажем вначале необходимость. Пусть х и у — две различные и смежные вершины выпуклого многогранника Е,. Так как они смежны, существует гиперплоскость, содержащая х и д и не содержащая других вершин и опорнал для этого выпуклого многогранника, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
