Дискретная математика (998286), страница 49
Текст из файла (страница 49)
Таким образом, множество Я, а следовательно, и множество Х вЂ” независимые. В тот момент, когда множество Я нельзя расширить (е = Га)зе), оно максимально по определению. Переменная гп глобальна, поэтому среди всех максимальных независимых множеств в конце работы алгоритма Х является наибольшим независимым множеством вершин.
'П 11.2.3. Улучшенный перебор Применение метода поиска с возвратами не гарантирует эффективности — трудоемкость поиска с возвратами имеет тот же порядок, что и другие способы перебора (в худшем случае). 275 1ц2. Построение независимых множеств вершин Используя конкретную информацию о задаче, в некоторых случаях можно существенно сократить трудоемкость выполнения кахсдого шага перебора или уменьшить количество перебираемых возможностей в среднем (при сохранении оценки количества шагов в худшем случае). Такие приемы называются методами улучшения перебора.
Например, может оказаться, что некоторые варианты заведомо не могут привести к решению, а потому их можно не рассматривать. ЗАМЕЧАНИЕ Рекурсивная форма метода поиска с возвратами удобна длн понимания, но не является самой эффективной. По сугн, рекурсия здесь используется длн сохранения конвмксвш— то есть информации, характеризующей текущий рассматриваемый вариант.
Если использовать другие методы сохранения контекста, то поиск с возвратами может быть реализован без явной рекурсии, а значит, более эффективно. Рассмотрим методы улучшения перебора на примере задачи отыскания всех мак- симальных независимых множеств вершин. Идея: начинаем с пустого множества и пополняем его вершииамир сохранением независимости (пока возможна).
Пусть Я» — уже полученное множество из й вершин, Я» — множество вершин, которое можно добавить к Я», то есть Я» й Г(~») = И. Среди вершин Я» будем различать те, которые уже использовались для расширения Я» (обозначим Я» ), и те, которые еще пе использовались (Я» ).
Тогда общая схема нерекурсивиой реализации поиска с возвратами будет состоять из следующих шагов. Шаг вперед от й к й+ 1 состоит в выборе вершины х б Я~+: Я»+1 = Я» О(х), Я» = Я» — Г(х), 9~~+» —— Я~~ — (Г(х) О (х)). Шаг назад от к + 1 к к: Ю» = Я»+з — (х), Я» = Я»+ — (х), Я, = Щ О(х). Если Я» — максимальное, то Я~+ = о.
Если Я» ф а, то Я» было расширено раньше и не является максимальным. Таким образом, проверка максимальности задается следукнцим условием: с„Г»' = щ = я. Перебор можно улучшить, если заметить следующее, Пусть х б Я» и Г(х) и Я+» = а. Эту вершину х никогда не удалить из Я», так как из Я» удаляются только вершины, смежные с Я~+.
Таким образом, существова- ние х, такого что х б Я, и Г(х) Г1 Я~~ = Э, является достаточным условием для возвращения. Кроме того, » ( р — 1, 276 Глава 11. Независимость и покрытия 11.2.4. Алгоритм построения максимальных независимых множеств вершин Приведенный ниже алгоритм, обоснование которого дано в предыдущем разделе, строит все максимальные независимые множества вершин заданного графа. Алгоритм 11.2. Построение максимальных независимых множеств Вход: граф с.
(Гг, Е), заданный списками смежности Г[е] Выход: последовательность максимальных независимых множеств й: = О ( количество элементов в текущем независимом множестве ) 3[й]: = И ( Я]й] — независимое множество иэ й вершин ) Г'„з ]й]: =за Я [й] — множество вершин, использованных для расширения о[й] ) ГГ+ [й]: = е' ( я+ [й] — множество вершин, которые можно испольэовать для расширения Я[й] ) М1:( шаг вперед ) ве1ест е б Я+,[й] ( расширяющая вершина ) Я[й + Ц: = Я[й] Ы (е) ( расширенное множество ) з З [й+ Ц: = Г'„з [й] зз Г[е] ( вершина е использована для расширения ) зе+ [й+ Ц: = Д+ [й] з (Г[о] ы(е) ) ( все вершин аз, смежные с е, не могут быть использованы для расширения ) й:=й+1 М2: ( проверка ) Еог иб Я [й] Йо 1Е Г[и! Гз г',)з'[й] = згз с[зев ного МЗ ( можно возвращаться ) епз( 1Е епд Еог зЕ О+ [й] = йз ь(зеп 1Е Г„] [й] = кз 1]зеп узе!з1 5[й] ( множество Я[й] максимально ) епб зЕ пото МЗ ( можно возвращаться ) е1эе ного М1 ( можно идти вперед ) епд зЕ МЗ; ( шаг назад ) е: = 1ааз(Я[й]) ( последний добавленный элемент ) й:=й — 1 Я[й]:=Я[й+ Ц вЂ” (е) Я [й]з=Я [й] 0(е) ( вершина е уже добавлялась ) Я'[й]: = Я+[й! 'з (е) 1Е й = О Зз О+ [й] = а Г(зеп егор ( перебор завершен ) е1эе ного м2 ( переход на проверку ) епз( 1Е 11.3.
Доминирующие множества Пример Известная задача о восьми ферзях (расставить на шахматной доске 8 ферзей так, чтобы они не били друг друга) является задачей об отыскании максимальных независимых множеств. Действительно, достаточно представить доску в виде графа с 64 вершинами (соответствующими клеткам доски), которые смежны, если клетки находятся на одной вертикали, горизонтали или диагонали.
11.3. Доминирующие множества Задача о наименьшем покрытии (сокращенно ЗНП) является примером общей экстремальной задачи, к которой прямо или косвенно сводятся многие практические задачи. Эта задача является классической, хорошо изучена и часто используется в качестве теста для сравнения и оценки различных общих методов решения трудоемких задач. В этом разделе на основе рассмотрения понятия доминирующего множества ЗНП формулируется в различных вариантах, и приводятся сведения о связи ЗНП с другими задачами. 11.3.1. Определения Для орграфа С('г', Е) множество вершин Я с У называется доминирующим множеством, если Я 0 Г(Я) = )г, то есть для любой вершины о Е )г либо о Е Я, либо существуют вершина в Е Я и ребро (в', о). Доминирующее множество называется минимальным, если его подмножество не является доминирующим.
Доминирующее множество называется наименьшим, если число элементов в нем минимально. Пример Известная задача о лягни ферзях (расставить на шахматной доске 5 ферзей так, чтобы они били всю доску) является задачей об отыскании наименьших доминирующих множеств. 11.3.2. Доминирование и независимость Доминирование тесно связано с вершинной независимостью. ТЕОРЕМА Независимое множество вершин является максимальным тогда и только тогда, когда оно является доминирующим.
Доклзлткльство Необходимость. Пусть множество вершин Я (Я с У) — максимальное независимое. Допустим (от противного), что оно не доминирующее. Тогда существует вершина е, находящаяся на расстоянии больше 1 от всех вершин множества Я. 278 Глава 11. Нвзззиоимость и покрытии Эту вершину можно добавить к Я с сохранением независимости, что противоре- чит максимальности. достаточность.
Пусть Я вЂ” независимое доминирующее множество. Допустим (от противного), что оно не максимальное. Тогда существует вершина и, не смежная ни с одной нз вершин множества Я, то есть находящаяся на расстоянии больше 1 от всех вершин множества Я. Это противоречит тому, что множество Я— доминирующее. П Независимое доминирующее множество вершин называется ядром графа. 11.3.3. Задача о наименьшем покрытии Рассмотрим следующую задачу. Пусть каждой вершине сопоставлена некоторая цена. Требуется выбрать доминирующее множество с наименьшей суммарной ценой. Эта задача называется задачей о наименьшем покрытии (сокращенно ЗНП). ЗНП является весьма общей задачей, к которой сводятся многие другие задачи.
Пример 1. Задача о выборе переводчиков. Организации нужно нанять переводчиков для перевода с определенного множества языков. Каждый из имеющихся переводчиков владеет некоторыми иностранными языками и требует определенную зарплату. Требуется определить, каких переводчиков следует нанять, чтобы сумма расходов на зарплату была минимальной. 2. Задача о развозке. Поставщику нужно доставить товары своим потребителям.
Имеется множество возможных маршрутов, каждый из которых позволяет обслужить определенное подмножество потребителей и требует определенных расходов. Требуется определить, какие маршруты следует использовать, чтобы все потребители были обслужены, а сумма транспортных расходов была минимальной.
11.3.4. Эквивалентные формулировки ЗНП ЗНП может быть сформулирована многими разными способами. 1. Пусть имеется конечное множество Ъ' = (щ,..., пр) и семейство подмножеств этого множества Е = (Ем...,Ер), Каждому подмножеству Е«приписан вес. Найти покрытие Е' (Е' с Е) наименьшего веса. ЗАМЕЧАНИЕ Из этой формулировки происходит название «зааача о наименьшем покрмтииь. 279 11.3. Доминирующие множества Наименьшее доминирующее множество вершин иничными весами Набольшее независимое множество вершин Наименьшее доминир множество Наибольшее независимое множеотво вершин Рио.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
