1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

Пусть читателя не смущает «ненаучный» вид этих изречений. В каждой точно описанной «омбинаторной задаче эти правила можно одеть в самую изысканную математическую аделаиду, но это пе изменит их сути, которая, особенно на начальной стадии поиска алгоритма, гораздо лучше выражается в таком виде, проникающем непосредственно в подсознание — этот реактор творчества челолека.

Догадка н интуиция играют в нахождении и формулировании правил такого рода не меньшую роль, чем точное знание и логическое рассуждение. Не случайно правила приближенного решения комбинаторных задач называют эвристическими — от греческого восклицания Ьбаге!'а (я нашел1), ставшего со времен Архимеда одним иа наиболее известных научных терминов. Особенностью любого эвристического метода решения задачи является наличие контрцримеров, показывающих неэффективность нли неприемлемость этого метода при поиске идеального решения.

Мы, однако, соанательно примнряем себя с их существованием, веря, во-первых, что этн контрпримеры не слишком портят налг $3А. РАСКРАСКА ВЕРШИЫ ГРАФА. ПОИСИ АИГОРИтмА 129 общую картину, и полагая, во-вторых, что любые попытки преодоления этих особых случаев нам обойдутся дороже, чем достигаемый этим выигрыш. В то же время поиск и анализ таких контр- примеров должен быть неотъемлемой частью всякого честного исследования, чтобы лучше понимать как силу, так и границы применимости эвристических методов. Эвристика раскраски.

В нашей задаче стремление найти алгоритм раскраски с не более чем квадратичной временнбй оценкой означает, что мы можем потратить на окраску одной вершины не более чем порядка п шагов. За и шагов мы можем осмотреть любую окрестность вершины, но не более чем весь граф. Такой акономный режим работы побуждает нас так организовать алгоритм раскраски, чтобы не перекрашнватй вершин, а на основе некоторого анализа окрестности вершины или, быть может, всего графа красить вершину, «не отменяя впоследствии принятых решений».

Этот, казалось бы, почти тривиальный подход уже задает некоторую дисциплину алгоритма: нам теперь надо решить, з каком порядке просматривать вершины графа н какой анализ (окрестности нли всего графа) производить, чтобы распорндиться выбором краски для вершины. «Краска и вершинаэ — наличие этих двух объектов подсказывает двойственный подход к общей организации раскраски. Первый — это взять некоторую краску н красить ей по какому-то выбору вершины, пока не окажется пн одной вершины, которой можно было бы сопоставить эту краску. Второй подход — мы просто повторяем конец предыдущего абзаца — состоит в том, чтобы, рассматривая вершины в некотором порядке, выбирать для очередной вершины подходящую краску.

Мы еще плохо понимаем, в чем состоит разница между первым и вторым подходами, н кому-нибудь эти перефразнровки покажутся просто игрой слов. Однако потребность логического анализа любой ситуации, присущая каждому математику, толкает нас на то, чтобы немного чпоиграть» с этими вариантами. Рассмотрим некоторое промежуточное состояние алгоритма раскраски для каждого из этих подходов. Для того чтобы сделать очередной шаг и раскрасить очередную вершину мы, в частности; должны определить, каковы ограничения (чего нельзя делать) н каковы степени свободы (чем можно распорядиться). При первом подходе — это определение на каждом шагу множества г" нераскрашенных вершин, которым нельзя сопоставить текущую краску а и множество г'" нераскрашенных вершин, которым можно сопоставить краску а. Очевидно, что г" — это вершины, которые смежны хотя бы с одной из вершин, окрашенных краской сг, и только они (будем обозначать такое множество У(а)).

Г'— зто, стало быть, (К~ СР)'~У', где г' — множество всех вершин графя, С'г' — множество раскрашенных вершин к данному мо- «зо гл. з. алгоэитмизхция менту. В частности, условие промежуточного финиша, т. е. исчерпания возмоя ностей для дальнейшего использования краски а — это >>" = Я. Общее окончание работы — это обнаружение, что У = С>>. Во втором подходе анализ ограничений имеет дело с окрестностью Х>(э) 1-го порядка текущей вершины и, т. е. множества смежных с ией вершин. Нн одна из красок, сопоставленных вершинам из Х,(и), не годится для и. В степенях свободы при раскраске вершины и есть две градации: одна — это какую краску выбрать из уже использованных, и вторая — взятие «свежей>» краски.

После этих двух абаацев разница между двумя подходами стала более ощутимой. Первый алгоритм кажется более направленным: на каждом шагу нам надо просто выбрать вершину из У" или взять свежую краску, если «"' пусто. Однако получение р> и У" требует более глобальных операций над графом: манипуляций с множеством >>(а), со всеми окрестностями 1-го порядка его вершин, с множеством С»' и «'. Второй алгоритм локализует анализ в окрестности Х>(и), но предоставляет более расплывчатыэ альтернативы. Очевидно, наше внимание теперь привлекает вопрос, а нельая ли каким-то образом улучшить анализ в первом алгоритме, который мы производим, отправляясь от множества У(а).

«'(с«) принадлежит С>> и, стало быть, является, так сказать„ «отработанной» частью графа. Все вершины из $'(а) попарно не смежны. Нас интересует для последующих решений только характер связей вершин >>(а) со смежными им вершинами. Эту ситуацию можно вообразить в виде картинки на рис.

3.11, а). При таком изображении (автор надеется) естественно появляется мысль, что если «склеить» вместе вершины из У(а) так, как это покааано. на рис. 3.11, б), то тогда Г становится просто окрестностью 1-го порядка новой вершины э>. Каждый согласится, что зто уже лучше, но для того, чтобы склеить вершины Ъ'(~), их все равно нужно перед этим собрать все вместе. Но тут уже начинает работать обычная сообразительность: на предыдущих этапах использования краски ««мы по очереди держали «в руках)> все вершины иа Г(с>)г имея очередную вершину и, окрашенную краской а, мы находила пополнение и' в семью «'(а), черпая ее из Г'. Так вот в этот-то момент мы и склеим» с и' и будем поступать так всегда, превращая процесс назначения краски вершине в последовательность копарных склеиваний несмежных вершин.

Еще не разобравшись до конца, что такое склеивание, основываясь на наглядном представлении об этом, ваятом из картинки, отрабатываем эту идею до конца. Представим, как будет раавиваться процесс с начала„ т. е. с работы с первой краской ап Множество СУ в нлчнльныймомент пусто. На каждом шаге склеивания У ' = (У~й)«(»,))'>, '~, (иД, где гх — это вершина, в которую мы «вклеиваемэ >юршикы, » 3.4. РАСКРАСКА ВИРШИН ГРАФА. ПОИСК АЛГОРИТМА йзг раскрашиваемые краской сдп Промежуточный финиш состоится, когДа г' ' = Я, откУДа слеДУет, что (од) 0 ддд(ид) = )г, т. Е.

когда вершина ид становится звездой. Если мы после этого начнем работать со второй краской а», начав вклеивать покрашенные ею веРшины в некотоРУю веРшинУ ид, то, так как ивенЛд(ид), мноидест. во СР = (и,) становитсЯ автоматически подмножеством Лд(и,), откуда мыполучаем, что и для ив и ' = (р'~Лд(р»))~(и»).

Немного а»)а> l 1 а Рис. ЗЛ1. Склеивание вершин'графа. в) До склейки. 6) После склейки. поразмыслив, мы обнаруживаем, что правило выбора множества Г' и условие промежуточного финиша (очередная вершина после серии склеиваний становится звездой) сохраняются для любой очередной краски. Очень любопытно звучит теперь и условие окончания работы алгоритма: для каждой вершины и графа Лд(и) () (о) = $', где, однако, и' — это уже не множество вершин исходного графа, а, выражаясь языком высокой математики, множество гомоморфных образов вершин исходного графа, так как каждая вершина результирующего полного графа (вспомните его определение!) есть совокупность склеенных попарно несмежных вершин исходного графа.

Склеивание вейшин. Теперь нам надо остановиться и подумать как следует. Мы не просто нашли некоторую наглядную перефорыулировку первого подхода к алгоритму раскраски, а ввели в некотором смысле совершенно новую трактовку процесса раскраски вершин. Вместо раскраски мы осуществляем последовательные преобразования графа 6, состоящие в «склеивании» несмеидных вершин. Склеивание двух вершин о и и, с окрестностями Л,(и,) и дгд(о») состоит в устранении из графа вершиц рд и ив вместе 132 гл. 3. Алгогнтмизлцкя пеппе Ф' с инцидентными им ребрами идобавления новойвершины ии инци' дентных ей ребер таким образом, чтобы Л,(и) '= Л,(п1)()Лд(цл)„ Результирующий граф С' имеет на одну вершину меньше', а также может иметь меньшее число ребер.

Меньшее число ребер получается потому, что если для вершин иг и и, существует третья вершина пз, смежная как с им так и с и„то вместо двух дуг (пп нз) и (нм из) в графе С останется только одна (щ из). Так происходит„ если и, и ил находятся друг от друга, как говорят, на расстоянии 2, если измерять расстояние мвлсду вершинами графа как число ребер в кратчайшем пути„ соединяющем эти верде шины.

Это можно выра- зить еще и такими слодп вами, как то, что и,ен ~ Л,(пл) и, наоборот, и,~Лл(из), понимая под окрестностью 2-го порядка некоторой вершины множество всех вершин, находящихся пеппе от данной на расстоянии 2. Вершину и, естественно прн атом назвать вершиной, разделяющей ит и и,.

Характеристики

Список файлов книги