Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 89
Текст из файла (страница 89)
() То, что мы описали, включает в себя только процесс ввпевления в методе ветвей и границ. Если продолжить процесс ветвления до г1 -2.5 Уб реше 4 сто Пусто г5 "3 Целые ац =2 ' 2 Ркс. ЦИ4. Бинарное дерево, пркводждее к ре- шеккю задачи. того момента, когда все вершины будут листьями дерева и будут соответствовать либо целочисленным решениям,,пибо недопустимым задачам ЛП, то лист с наименьшей стоимостью должен быть оптимальным решением исходной задачи ЦЛП.
Мы приходим к важной составной части метода ветвей и границ. А именно, предположим, что в некоторый момент наилучшее полностью целочисленное решение, найденное к этому моменту, имеет стоимость г,„н мы намереваемся произвести ветвление в вершине, в которой нижняя граница га — — с(х") больше или равна г . Это означает, что любое решение х, которое можно получить в качестве потомка решения ха, будет иметь стоимость с(х))гд)г„, и, следовательно, нам не нужно продолжать ветвление из ха.
В таком случае будем говорить, что вершина х" убита, и будем называть ее (как можно догадаться) мертвой. (Используется также термин (а(пошес(.) Остальные вер- 15 м аааа 450 Гл. >З, Метвд ветвей и границ шины, ветвление из которых еще быть может выгодно, будут называться живыми. Пример 18.1(продолжение). Обращаясь снова к рис. 18.1 и 18,4, замечаем, что нижняя граница в вершине, соответствующей задаче 1, равна — 2.5, что больше, чем стоимость — 3 решения, соответствующего вершине 5. Поэтому эта вершина убивается вершиной 5. Так кзк не остается живых вершин, то вершина 5 должна представлять оптимальное решение.
Д В этом алгоритме остаются две важные детали, которые нужно уточнить: нужно решить, как выбирать на каждом шаге, из какой вершины проводить разветвление; и нужно-решить, как выбирать, какая нецелая переменная должна определять дополнительное огра. ничение. Дэйкин (Ра) рекомендует проводить разветвление по принципу в глубину для уменьшения обьема памяти, необходимой для промежуточных таблиц.
Если память не является ограничивающим фактором, то в качестве разумной эвристики может рассматриваться разветвление из живой вершины с наименьшей нижней оценкой. Мы обсудим эту проблему позднее в данной главе в более общем контексте; но вообще относительно этого выоора извес~но очень мало. Относительно второго выбора (переменной для добавления ограничения) Дэйкин Юа! сообщает, что наилучшая стратегия — это найти то ограничение, которое приводит к наибольшему возрастанию нижней границы г после выполнения одной итерации двойственного симплекс-алгоритма после добавления э~ого ограничения, и добавить либо это ограничение, либо альтернативное ему ограничение 1Оа].
Обоснованием этого является желание найти ветвь из данной вершины, которая, наиболее вероятно, будет убита, и сохранять таким образом дерево поиска коротким, Здесь опять нет теорем, дающих наилучшую стратегию, и единственным известным руководством при разработке быстрых алгоритмов этого типа в настоящее время являются вычислительный эксперимент и интуиция. Метод ветвей и грзниц применим не только к задачам, формулируемым в виде задач ЦЛП (или сме>ванного ЦЛП), а почти к любой задаче комбинаторной природы. Ниже мы построим соответствующий алгоритм в очень широком контексте. 18.2 Метод ветвей и границ в общем виде При построении дерева в алгоритме ветвей и границ для задачи ЦЛП нэм потребовались две вещи.
1. Ветвление. Множество решений, представляемое вершиной, можно разбить на попарно непересекающиеся множества. Каждое подмножество в этом разбиении представляется сыном исходной вершины. 2. Получение нижних границ. Имеется алгоритм для вычисления нижней границы стоимости любого решения в данном подмножестве. 45! !8.г. й!гтод еетеед и границ в общем виде Никакие другие свойства задачи ЦЛП не использовались, Поэтому рассматриваемый метод можно сформулировать для любой задачи оптимизации, в которой выполняются свойства (1) и (2), независимо от того.
линейна или нет функция стоимости. Ьей!п активноемножестео:=(О); (сошшеп1; "0" — это вскодная задача) (у:=оа; лучщггаыкущгг:= что угодно; ый!1е актавнагмножгстео не пусто до Ьей! и выбрать вершину ветвления К на активногмножгство; удалять вершину й на активнагмножество; породить сыновей сын 1, 1=1, ..., пю вершнны К н соответствующие ннжззне границы аи !ш 1=1, ..., П„до' Ье51п И аз ) У Шеп убить сына з е!ае и сын ! — полное решение дзеп Оп=аз, лучшеетгкущее:=сын ! еые добавить сына 1 к активногмножгство епд епд епд Рнс. 18.5. Основной алгоритм ветвей и границ. Основной алгоритм приведен на рис.
18.6. В нем множество активноемножество используется для хранения живых вершин в любой момент; переменная (! используется для представления стоимости наилучшего полного решения, полученного к данному времени ((! является верхней границей оптимальной стоимости). Заметим, что в процессе ветвления может порождаться не два сына данной вершины, как в задаче ПЛП, а любое конечное число сыновей. Пример 18.2 (задача о кратчайшем пути).
Рассмотрим задачу о кратчайшем пути в графе с неотрицательными весами дуг. Хо!я мы уже имеем эффективный алгоритм ее решения, к ней можно также очевидным образом применить метод ветвей и границ. На рис. !8.6 (а) приведена индивидуальная задача о кратчайшем пути. Для решения этой индивидуальной задачи (задачи О) методом ветвей и гранин производится ветвление путем выдра очередной дуги в пути.
Таким образом, подмножество допустимых решений соответствует всем путям из в в 1, начинающимся с уже выбранной последовательности дуг. На рис. !8.6(б) приведено дерево поиска, получаемое в некоторый момент, при условии, что ветвление на каждом шаге производится в вершине с нзименьшей нижней границей. В качестве нижней границы совершенно естественно используется суммарная длина частичного пути до некоторой вершины графа, представляемого данной вершиной в дереве поиска. Например, путь Ь-д-! приводит нас в вершину с нижней границей 10, равной 15а в к (в) Рио. 18.6.
Задача о кратчайшем пути и ее реше- ние методом ветвей и границ. 18.2. Метод ветвеа и границ в общем виде сумме стоимостей ребер Ь, й и й Заметим, что в этом примере довольно легко вычислить нижние границы для всех сыновей вершины, в которой производится ветвление. При применении метода ветвей и границ к задаче ЦЛП нам приходилось для получения нижней границы решать задачу линейного программирования, поэтому мы ие обяза1ельно искали обе нижние границы непосредственно при ве1влении, ибо была надежда, что некоторых из этих вычислений можно избежать из-за последующих убийств.
На рис 18.6(в) представлено заключительное дерево поиска для этого примера. Перв; е полное найденное решение имеет стоимость 8, и оказывается, что оно оптимально. Убитые вершины отмечены подчеркиванием снизу соответствующих нижних границ. Д Пример 18.3 (задача коммивояжера) Более реалистическое применение метода ветвей и границ дают ЖР-полные задачи, такие, как ЗК. Процесс ветвления для ЗК можно сформулировать многими способами; возможно, простейший — это разбиение пространства решений каждый раз на два множества в зависимости от того, входит или не входит данное ребро в обход. Этот подход, вместе с эвристикой для получения нижних границ, использовали Литтл и др.
П.МБК). В другом подходе, приписываемом Истмену (Еа!, используется сушешвование эффективного алгоритма для задачи о взвешенном двудольном паросочетании, или задачи о назначениях (см. гл. 11). Это дает еще один пример представления одной задачи в виде простой подзадачи для более сложной задачи. Если положить хм=1, когда ребро 11,11 содержится в обходе, и х;;=О в противном случае, то обход для ЗК с и городами и с весами сы должен удовлетворять условиям пн(па =,~~ с, хко ь!=! ~ хы ~в ~х /= ! 1=1, ...,и, (18,4) =и 1, 1=1, ..., и.
Здесь два множества равенств выражают тот факт, что в каждую вершину входит ровно одно ребро и ровно одно ребро выходиз из каждой вершины. Эта формулировка (задача о назначениях из 5 11.2) недостаточна для адекватного описания ЗК, зак как мы не можем быть уверены, что решение будет единым обходом ровно с одним циклом. Поэтому ограничения (18.4) необходимы, но не достаточны для ЗК, и решение задачи (18.4) дает величину г, которая является нижней границей стоимости ЗК.
При етом, если решение задачи (18.4) является обходом, гогда зно является решением нашей ЗК. Если решение не является обхо. Ге. И. Метод ветвеа и границ дом, то оно содержит цикл длины, меньшей, чем и, т. е. подобход !хгм х„,..., ха,1, такой, что х„=хаа= ..— — хи,— — 1.
В ЗК не могут все эти переменные равняться 1, поэтому пространство решений можно разбить на й подмножеств, добавляя каждый раз одно из ограничений х„=О, х,„=О,..., х„=О. Это приводи~ к й задачам, каждая из которых гакже являетгя задачей о назначениях (Для исклк;пении ребра х„из решения достаточно приписать ему очень больц.ую стоимость.) Шаг ветвления проиллюстрирован на рис 18.7.
ит полобход ке( ! ац о Рис. !8.7. Шаг ветвления в методе ветвед н гранин для ЗК. Нижнюю гранину в каждой вершине можно получить, решая задачи о назначениях, соответствующую этой вершине, методом, описан ным в гл. 1!. Пример 18.4 (граница для ЗК, получаемая с помощью остовного дерева) Хелд и Карп (НК1, НК2! описали очень эффективный алгори|м ветвей и границ для ЗК, основанный на вычислении нижних границ по соответствующим минимальным остовным деревьям. Для этого требуется Определение !8.1. Пусть дан полный граф б=()г, Е) с матрицей расстояний Ыгт! и и= !)г! вершинами. Тогда 1-дереаом называется граф, образованный некоторым деревом на множестве вершин (2,... ...,л), плюс два ребра, инцидентных вершине 1. Г) Каждый обход является 1-деревом (но не наоборот), поэтому минимальная стоимость 1-дерева является нижней границей стоимости обхода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
