Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 93
Текст из файла (страница 93)
Объяснение, по-видимому, следующее: 3-замена достаточна сильна, поэтому она быстро улучшает случайный обход, и, начиная с совершенно случайных обходов, мы получаем широкий набор локальных оптимумов. Однако в тех задачах, где мы вынуждены использовать относительно слабые окрестности, использование «хороших» начальных решений может играть решающую роль. Еще одним важным результатом работы Лина является демонстрация того, что 3-оптимальные решения намного лучше, чем 2-оптимальные, по 4-оптимальные решения не настолько лучше, чем З-оптимальные, чтобы оправдать дополнительные затраты машинного времени Правда, не совсем ясно, почему это так.
Лин эмпирически нашел, что для его класса примеров вероятность того, что 3-оптимальный обход будет оптимальным, равна приблизительно 2-"" о, где п — число городов. Такая оценка позволяет ре',цить, сколько раз нужно производить вычисления из случайных начальных точек, чтобы обеспечить заданную вероятность оптимальности решения.
Но, к сожалению, до сих пор нет теоретических подтверждений эмпирических результатов такого вида. Результаты Лина, касающиеся ранее опубликованных задач, известных своей трудностью, оказались настолько эффектными, а общий подход к ЗК настолько успешным, что это стимулировало применение локального поиска к множеству других задач. 19.3 Задача е: надежные сетн мнннмапьной стонмостн Задача коммивояжера является прототипом применения локального поиска и обладает многими удобными чертами, которые не всегда присутствуют в других задачах. Например, для нее очень легко порождать полностью случайные решения и очень легко проверять их на допустимость.
Этим свойством не обладает наш второй пример — задача построения сети с заданной связностью и минимальной стоимостью. Для формулировки этой задачи нам потребуется предварительное определение. Определение 19.1. Пусть даны связный неориентированный граф 6=(Г, Е) и две различные вершины 1, 1~ )с. Множество пу- 470 Гл. 19. Локальный поиск тей из ! в 1 называется множеством вершинно не!!ересекаюи(ихся путей, если никакая верн!ина, отличная оз ! и), не лежит более чем на одном из этих путей Вершинной связностью между ! и 1 называется максимально возможное число вершинно непересекающихся путей между ними.
! ) Пример 19.1. На рис. 19.2 представлен граф, в котором вершинная связность между любыми двумя различными вершинами равна 3. Такой граф называется 3-связным. Если граф 6 представляет сеть связи, то вершинная связность между двумя вершинами является мерой надежности связи между ними, связный граф. Рис !92' ТРех поскольку она равна минимальному числу вер- шин, которые нужно удалить из сети для разделения данных двух вершин (читателю предлагалось доказать этот результат в задаче 8 в гл.
6). Если дана матрица стоимостей, то интересной задачей является построение сети с заданными связностями между всеми парами вершин и минимальной общей стоимостью. Более формально определим следующую задачу, Определение 19.2. Пусть даны матрица стоимостей (й! ! и матрица связностей Ь!,!. Тогда задача о надежной сети минимальной стоимости (НСМС) состоит в нахождении графа 6=()7, Е) с минимальной суммарной стоимос!ью ~!н,!аей! и вершинной связностью г; между различными вершинами !', 1, удовлетворяю!цей неравенству г,т)зы для всех 1, 1, (Ф( В работе (БЮК! к задаче НСМС был применен локальный поиск и ниже мы опишем полученные результаты.
Понятие д!р-полноты в 1969 г. еще не было введено, но на самом деле соответствующий вариант этой задачи является ЮР-полным (вспомните разд 16.3.1), Первая трудность, которая здесь возникает,— это вычисление действительной матрицы связиостей (67! для данного графа. В следующей теореме устанавливается верхняя оценка сложности вычисления связности между двумя точками. Теорема 19.! Грусть даны иеориентированный граф 6= — ((7, Е) и две различные вершины !, 1Е )7. Тогда вершинную связность П, можно найти за время 0 (!(ГР").
Доказательство. Построим ориентированный граф 6'=()7', Е'), заменяя каждую вер!инну сЕ (7 двумя вершинами о и и" Е )7', как показано на рис !9.3. Затем рассмотрим потоковую еть, получаемую приписыванием каждой дуге из 6 единичной пропускной способности.
Тогда величина максимального потока из ! в 1 в дан. ной сети совпадаез с вершинной связностьо 6, поскольку единичная пропускная способность дуги, идущей из й' во", означает, что вершина и в исходном графе 6 может лежать только на одном пути 1У.З. Задача Зг надежные сети минимальной стоимости 47! из т в 1. Потоковая сеть, соответствующая 6', является простой, поэтому, согласно теореме 9.4, максимальный поток в ней можно вычислить за время О((!г!ь'ь). ~З Сколько раз нужно вычислять связность между двумя точками, чтобы проверить условие допустимости гг,' ьзг для всех 1, 1, 1~1, Вершинаиа и Вершины и',и: а у* Рис. 19.3.
Конструкция из доказательства георемм 19,1. для данного графа? Как мовсно догадаться, не обязательно вычислять все !)г!(!1'! — 1)г2 вершинных гвязностей г;,. Например, можно показать, что в том случае, когда все з,, равны й, достаточно й(!(л! — (й+1)г2) вычислений, что можно записать как 0(/г!У!) (см. задачу 13 в этой главе и задачу 13 из гл. 9).
Таким образом, задача проверки допустимости графа полнномиальна, однако она значительно сложнее, чем в ЗК. Лалее мы приходим к проблеме построения началыгого допустимого решения. Мы опишем метод, использованный в (3!т1ггК), который является эмпирически эффективной жадной эвристикой. Его идея основана на том, что степень вершины г' должна быть не меньше, чем гпах,с,, Определим дефицит в вершине г' в неориентированном графе ст равенством ДвфИЦИт(1) е ШаХГГу — СТЕПЕНЬ (1).
l Будем добавлять ребра к графу б до тех пор, пока все дефициты не станут неотрицательными. Затем проверим полученный граф на допустимость, используя упомянутый выше алгоритм нахождения максимального потока. Рассмотрим это более детально. Вначале у нас имеется массив размера ) !т), содержащий дефициты всех вершин. На каждом шаге мы добавляем ребро между вершиной с наибольшим дефицитом и вершиной со следующим по величине дефицитом. Из всех вершин со следующим по величине дефицитом выбирается та, которая дает в результате наименьшее увеличение стоимости; все остальные неопределенности разрешаются выбором вершины, которая раньше всех встречается в массиве.
Кратные ребра не допускаются. Пример !9.2. Рассмотрим задачу с однородными требованиями на связность: з,, =3 для всех 1, ! и матрицей стоимостей, определяемой евклидовым расстоянием на плоскости между восьмью вер- Гл. 79. Локальный поиск шинами, приведенными на рис. !9.4(а), Начальный массив имеет вид Вершина 1 2 3 4 5 6 7 8 Дефицит 3 3 3 3 3 3 3 3 Наибольший дефицит, естественно, 3, и первым выбирается ребро (1, 2), так как вершина 2 — ближайшая к вершине ! среди Об 5 5О 4О ОЗ 7 7О 2О 10 Оа ) (а) (в) (б) Рис. !9.4.
а) Расположение вершин для примера )9.2 б) Резул~тат работы алгоритма описка начального решения. в) Выгодная Х-замена, приводящая н недопустимому графу. всех вершин с дефицитом 3. Затем по порядку добавляются ребра (3, 41, 15, 61, !7, 81, !1, 71, !2, 31, !4, 51, (6, 81, !1, 81, !2, 71, 13, 61, (4, 6! и !5, 71; получаемый в результате граф приведен на рис. )9.4(б). Читатель может проверить, что в этом графе вершинная связность между любой парой вершин равна 3. Заметим, что в нем имеются две вершины степени 4; нумерация вершин может влиять на число ребер в получаемом графе. Кроме того, если вершины занумерованы другим способом, результат вполне может оказаться недопустимым.
Мы уже упоминали, что алгоритм выбора начальной точки желательно делать вероятностным; в предыдущем случае это достигается случайным упорядочением вершин перед применением описанного алгоритма. Указанный метод це только дает набор начальных допустимых решений, но к тому же эти начальные решения имеют, как правило, низкую стоимость и малое число ребер. Было обнаружено, что в отличие от ЗК задача НСМС требует начальных решений с относительно низкой стоимостью. Это связано с используемыми окрестностями, которые мы сейчас опишем. Определение !9.3. Пусть множество графов, допустимых в инди- видуальной задаче НСМС, обозначается через Р.
Это значит, что !9.З. Задана Зе надежные ееыи минимальной отоимоолеи 47З Е состоит из всех графов с данным числом вершин и вершинными связностями, удовлетворяющими неравенствам ге, з,, для всех Л /, тФ/. Рассмотрим граф 6(1', Е) Е Е, в котором ребра ((, т! и Ц, Л присутствуют, а ребра (Л Л и (!', т) отсутствуют (рис. 19.5). ребра Рис. !9.5.
Онреетность относительно Х-замены. Определим новый граф 6'=((г, Е'), получаемый удалением ребер (Л т! и (1, Л и добавлением ребер ((, Л и ((, т1, т. е, Е' Е () ('(с', (], (), и]) — ((Л и], 11, (]) Тогда, если 6' ЕЕ, будем говорить, что 6' является Х-заменой графа 1, и множество Х-замен графа 6 определяет его окрестность относительно Х-замены.
Если новая стоимость меньше старой, т. е. (!9.!) А и+с~у (А„+йуь то Х-замена называется выгодной. Окрестность относительно Х-замены обладает тем свойством, что в ней сохраняется число ребер и степень каждой вершины, в связи с чем желательно иметь набор начальных решений по возможности с различным числом ребер и различными степенями вершин. При поиске по окрестности относительно Х-замены имеется некоторая трудность.
Довольно легко ищутся все пары ребер (Л т) и (!', Л, удовлетворяющие (19.1). Однако получаемый граф 6' может оказаться недопустимым. Это проиллюстрировано на рис. 19.4(в), где изображенный граф получен из графа, приведенного на рис. !9.4(б), удалением ребер (2, 3) и (7, 8! и добавлением ребер (2, 8) и (3, 7!. В полученном графе вершинная связность меньше 3; например, имеется только два вершинно непересекающихся пути из 1 в 3. Если бы нужно было проверять весь граф на допустимость после каждой обнаруженной выгодной Х-замены, то алгоритм локального поиска был бы очень медленным, но, оказывается, полная проверка не обязательна (см.
задачу 13). В случае когда все г,, принимают одно и то же значение й, необходимо на самом деле рассмотреть только две вершинные связности, чтобы проверить допустимость нового графа. Гл. 79. Локальный поиск 474 Обнаружено, что алгоритм локального поиска с использованием начального алгоритма и окрестностей, описанных выше, эффективен для большого числа задач Ниже мы приведем результаты для одной простой задачи. Пример 19.3.
На рис. !9.6 приведен пример (из !3!ФК!) с 7 вершинами и однородными требованиями на связность, которая должна равняться 3 Для матрицы стоимостей, полученной взятием це- 40 40 ЗО 20 20 ЭО 10 0 30 20 30 40 0 !О 20 ЗО 40 (б) (а) Рис. !9.6. а! Пример с семмо вершинами !5!тн'К), 6! Оптимальное решение лых частей от евклидовых расстояний, было порождено 100 локальных оптимумов со следующим распределением стоимостей: Стоимост~ Числю понвлений ит ! ОО Стоимость Число появлений нн с 00 242 245 250 25! 253 258 265 270 39 9 20 что, как можно доказать, больше, чем вероятность выполнения на вычислительной машине 1-секундной программы без необнаруженной ошибки !см. задачу 10) Отметим также, что имеется большое множество локальных оптимумов со стоимостями, близкими к оптимальной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
