Новиков Ф.А. Дискретная математика для программистов (860615), страница 66
Текст из файла (страница 66)
Такие приёмы называются методамиулучшения перебора. Например, может оказаться, что некоторые варианты заведомо не могут привести к решению, а потому их можно не рассматривать.ЗАМЕЧАНИЕРекурсивная форма метода поиска с возвратами удобна для понимания, но не являетсясамой эффективной. По сути, рекурсия здесь используется для сохранения контекста —то есть информации, характеризующей текущий рассматриваемый вариант.
Если использовать другие методы сохранения контекста, то поиск с возвратами может быть реализованбез явной рекурсии, а значит, более эффективно.Рассмотрим методы улучшения перебора на примере задачи отыскания всехмаксимальных независимых множеств вершин.Идея: начинаем с пустого множества и пополняем его вершинами с сохранениемнезависимости (пока возможно).Пусть Sk — уже полученное множество из к вершин, Qk — множество вершин,которое можно добавить к Sk, то есть Sk П T(Qk) = 0- Среди вершин Qk будемразличать те, которые уже использовались для расширения Sk (обозначим ихмножество Qk), и те, которые еще пе использовались).
Тогда общая схеманерекурсивной реализации поиска с возвратами будет состоять из следующихшагов.Шаг вперед от к к А; 4- 1 состоит в выборе вершины х еSk+i ' = Sk + x,Qk+l • = Qk \Шаг назад от к + 1 к к:Sk • = Sk+i - х,Qt•= Qt~ х->Q-k: = Q~k+x.Если Sk — максимальное, то= 0 . ЕслиФ 0, то Sk было расширенораньше и не является максимальным. Таким образом, проверка максимальностизадается следующим условием:== 0.Перебор можно улучшить, если заметить следующее.Пусть х еи r ( x ) n Q j = 0 .
Эту вершину х никогда не удалить из, так какизудаляются только вершины, смежные с. Таким образом, существование х, такого, что х Еи Г(х) П= 0, является достаточным условием длявозвращения. Кроме того, к ^р - 1.352Глава 10. Циклы, независимость и раскраска10.5.4. Алгоритм построения максимальныхнезависимых множеств вершинПриведённый ниже алгоритм, обоснование которого дано в предыдущем подразделе, строит все максимальные независимые множества вершин заданногографа.Алгоритм 10.3 Построение максимальных независимых множествВход: граф G(V, Е), заданный списками смежности Г [и].Выход: последовательность максимальных независимых множеств.к: = 0 { количество элементов в текущем независимом множестве }S[k]: = 0 { S[k] — независимое множество из к вершин }:= 0— множество вершин, уже использованных для расширения S[k] }Q+[k]: = V{ Q+[k] — множество вершин, которые можно использовать для расширения S[k] }Ml : { шаг вперед }select v е Q+[k] { расширяющая вершина }S[k + 1]: = S[k] U {г>} { расширенное множество }Q~[k + 1]: = Q~[k] \ Г [г;] { вершина v использована для расширения }Q+[k+l]: =Q+[k)\(r[v]U{v}){ все вершины, смежные с v, не могут быть использованы для расширения }к: = к + 1М2 : { проверка }for и е Q~ [/с] doif Г [и] П Q+[k] = 0 thengoto М3 { можно возвращаться }end ifend forif Q+[k] = 0 thenif Q~[k\ = 0 thenyield S[k] { множество S[k] максимально }end ifgoto M3 { можно возвращаться }elsegoto M l { можно идти вперед }end ifM3 : { шаг назад }v.
= last(S[fc]) { последний добавленный элемент }к: = к- 1ЗД: = 5[А: + 1].- МQ~ [/с]: = Q~ [fc] U {г>} { вершина v уже добавлялась }Q+[k]: = Q+[k]\ Мif к = 0 к Q+ [*;] = 0 thenstop { перебор завершён }elsegoto М2 { переход па проверку }end if35310.6. Доминирующие множестваПример Известная задача о восьми ферзях (расставить па шахматной доске8 ферзей так, чтобы они не били друг друга) является задачей об отысканиимаксимальных независимых множеств.
Действительно, достаточно представитьдоску в виде графа с 64 вершииами (соответствующими клеткам доски), которыесмежны, если клетки находятся на одной вертикали, горизонтали или диагонали.10.6. Доминирующие множестваЗадача о наименьшем покрытии (сокращённо З Н П ) является примером общейэкстремальной задачи, к которой прямо или косвенно сводятся многие практические задачи. Эта задача является классической, хорошо изучена и частоиспользуется в качестве теста для сравнения и оценки различных общих методоврешеиия трудоёмких задач.В этом разделе на основе рассмотрения понятия доминирующего множестваЗ Н П формулируются и приводятся сведения о связи З Н П с другими задачами.10.6.1. Минимальное и наименьшее доминирующеемножествоМножество вершин S С V графа G(V, Е) называется доминирующим множеством(или внешне устойчивым), если S U Г(5) = V, то естьV u e V (veSv 3seS((s, v) e E)).Очевидно, что множество S доминирует тогда и только тогда, когдаVv £ 5(r(v)nS/0),что равносильно утверждению Vv е V (3 s е S (d(v,s) ^ 1)).Доминирующее множество называется минимальным, если никакое его подмножество не является доминирующим.
Доминирующее множество называется наименьшим, если число элементов в нём наименьшее возможное.Пример Известная задача о пяти ферзях (расставить на шахматной доске 5ферзей так, чтобы они били всю доску) является задачей об отыскании наименьших доминирующих множеств.10.6.2. Доминирование и независимостьДоминирование тесно связано с вершинной независимостью.ТЕОРЕМАНезависимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.ДОКАЗАТЕЛЬСТВО[ = > ] Пусть множество вершин S с V — максимальное независимое. Допустим(от противного), что оно не доминирующее.
Тогда существует вершина v, находящаяся на расстоянии больше 1 от всех вершин множества S. Эту вершину можнодобавить к S с сохранением независимости, что противоречит максимальности.354Глава 10. Циклы, независимость и раскраска[ < = ] Пусть S — независимое доминирующее множество. Допустим (от противного), что оно не максимальное. Тогда существует вершина v, не смежнаяни с одной из вершин множества S, то есть находящаяся на расстоянии больше 1 от всех вершин множества S.
Это противоречит тому, что множество S —доминирующее.•Независимое доминирующее множество вершин называется ядром графа.Примернет.В полном графе Кр каждая из р вершин является ядром и других ядерСЛЕДСТВИЕЛюбой граф имеет ядро.Следующий простой алгоритм, основанный на доказательствепредыдущей теоремы, строит некоторое ядро S.£ : = 0 { ядро }while V Ф 0 doselect v € V { любая нерассмотренная вершина }S-.-S + v { расширяем множество S }V; = V \Г*('<;) { удаляем вершины, которые не могут быть использованы длярасширения }end while•ДОКАЗАТЕЛЬСТВОПонятия независимости, доминирования и ядра применимы как к графам, так и корграфам.
Множество узлов S орграфа называется независимым,если\/v G S (Г(и) П S = 0), и называется доминирующим, если V v & S (Г(г;) П S Ф 0 ) .Независимое доминирующее множество узлов в орграфе называется ядром.ЗАМЕЧАНИЕСуществуют орграфы, не имеющее ядра. Например, контур Сз не имеет ядра. Более того,задача выделения ядра в произвольном орграфе оказывается JVP-полной.10.6.3. Задача о наименьшем покрытииРассмотрим следующую задачу. Пусть каждой вершине сопоставлена некоторая цена.
Требуется выбрать доминирующее множество с наименьшей суммарной ценой. Эта задача называется задачей о наименьшем покрытии (сокращённоЗНП).З Н П является весьма общей задачей, к которой сводятся многие другие задачи.10.7. Раскраска графов355Примеры1. Задача о выборе переводчиков. Организации нужно нанять переводчиковдля перевода с определённого множества языков. Каждый из имеющихся переводчиков владеет некоторыми иностранными языками и требует определённую зарплату. Требуется определить, каких переводчиков следует нанять, чтобы сумма расходов па зарплату была минимальной. Задача о выборе переводчиков сводится к З И П следующим образом.
Рассмотрим полный двудольныйграф с долями Vi и V2, где доля V\ соответствует множеству переводчиков,а доля V2 — множеству языков. Вершины v\ £ V\ и v2 6 V2 смежны, еслипереводчик v\ владеет языком v2. Требуется найти наименьшее покрывающеемножество S С V\.2. Задача о развозке. Поставщику нужно доставить товары своим потребителям.Имеется множество возможных маршрутов, каждый из которых позволяет обслужить определённое подмножество потребителей и требует определённыхрасходов. Требуется определить, какие маршруты следует использовать, чтобы все потребители были обслужены, а сумма транспортных расходов быламинимальной.
Задача о развозке сводится к З И П аналогичным образом. ЗдесьV\ — множество маршрутов, V2 - множество потребителей и вершины v\ б V\и v2 6 V2 смежны, если маршрут v\ обслуживает потребителя v2.10.6.4. Связь задачи о наименьшем покрытии с другимизадачамиЗ И П может быть сформулирована многими разными способами.Пример Пусть имеется конечное множество V =,..., vp} и семейство подмножеств этого множества Е = { £ 1 , . . . , Е р ) . Каждому подмножеству Ei приписан вес. Найти покрытие Е ' ( Е ' с Е ) наименьшего веса. На языке графов Vi —это вершина, a Ei — множество смежности вершины, то есть Е(: = Г*ЗАМЕЧАНИЕИз этой формулировки происходит название «задача о наименьшем покрытии».Известно, что З Н П относится к числу трудоёмких задач, и для её решенияприменяются переборные алгоритмы с теми или иными улучшениями.На рис.
10.7 приведена схема (заимствованная из [21]), показывающая связьЗ Н П и некоторых других задач. На этой схеме стрелка от задачи А к задаче Возначает, что решение задачи А влечет за собой решение задачи В.10.7. Раскраска графовЗадача раскрашивания графов, которая на первый взгляд кажется просто праздной головоломкой, имеет неожиданно широкое применение в программировании,особенно при решении фундаментальных теоретических проблем (см., например, [23]).356Глава 10.
Циклы, независимость и раскраска<> ЗНПНаименьшее д о м и н и р у ю щ е емножество вершинЗНП с единичными весамиНаибольшеенезависимоемножество вершинНаибольшаякликаНаименьшее д о м и н и р у ю щ е емножество реберНаибольшее независимоемножество реберР и с . 1 0 . 7 .
Связь различных задач10.7.1. Оценки хроматического числаРаскраской графа G называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины пе получают одинаковыйцвет. Если задана допустимая раскраска графа, использующая т цветов, то говорят, что граф m-раскрашиваемый. Наименьшее возможное количество цветовв раскраске называется хроматическим числом и обозначается x(G).Примерых(Кр) = \, х{Кр)=р,x ( * m , n ) = 2 , х(С2п)=Т — свободное дерево.2, x(G 2 n + 1 ) = 3, х ( Т ) = 2 , гдеОчевидно, что существует m-раскраска графа G для любого га в диапазонеx(G) ^ m < р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
