Новиков Ф.А. Дискретная математика для программистов (860615), страница 20
Текст из файла (страница 20)
Пусть имеются конечное множество Е, \Е\ = п, весовая функция w: Е —* R+ и семейство£ с 2е. Требуется найти X е £, такое, чтоw(X) = тахги(У),где w(Z) =f^w(e).eeZCEДругими словами, необходимо выбрать в указанном семействе подмножествонаибольшего веса. Не ограничивая общности, можно считать, что w(e\) ^ ... ^^ w(eTl) > 0. Рассмотрим следующий алгоритм.Алгоритм 2.2 Жадный алгоритмВход: множество Е = { e i , . . . , e n } , семейство его подмножеств £ и весоваяфункция w. Множество Е линейно упорядочено в порядке убывания весовэлементов.Выход: подмножество X, такое, что X е £ и w(X) = m a x w ( Y ) .X : = 0 { вначале множество X пусто }for i from 1 to n doif X + e{ e £ thenX : = X + a { добавляем в X первый подходящий элемент }end ifend for2.6. Матроиды и жадные алгоритмы103Алгоритм такого типа называется жадным.
Совершенно очевидно, что по построению окончательное множество X £ £. Также очевидно, что жадный алгоритмявляется чрезвычайно эффективным: количество шагов составляет 0(п), то естьжадный алгоритм является линейным. (Не считая затрат па сортировку множества Е и проверку независимости X + е* £ £.) Возникает вопрос: в какихслучаях жадный алгоритм действительно решает задачу, поставленную в началеподраздела? Другими словами: когда выгодно быть жадным?ПримерПусть дана матрица7325 14 33 1Рассмотрим следующие задачи:1. Выбрать по одному элементу из каждого столбца так, чтобы их сумма была максимальна.
Нетрудно видеть, что жадный алгоритм выберет следующиеэлементы:0 0134 [3j231которые действительно являются решением задачи.2. Выбрать по одному элементу из каждого столбца и из каждой строки так,чтобы их сумма была максимальна. Нетрудно видеть, что жадный алгоритмвыберет следующие элементы:0513 Щз2[Ц3которые не являются решением задачи,ние:05342 [3]поскольку существует лучшее реше1[Ц1ТЕОРЕМАЕсли М = (Е, £) — матроид, то для любой функции w жадный алгоритм находит независимое множество X с наибольшим весом; обратно, если жеМ = (Е, £) не является матроидом, то существует такая функция w, что множество X, найденное жадным алгоритмом, не будет подмножеством наибольшеговеса.ДОКАЗАТЕЛЬСТВО[ = > ] Пусть М = (Е,Е) — матроид и пусть X = {ал,...,®*.} — множество,построенное жадным алгоритмом.
По построению u>(a?i) ^ . . . ^ w(x k ) > 0.Согласно алгоритму 2.1, множество X — базис матроида М. Пусть теперь Y == {г/ь • • ч У т } € £ — некоторое независимое множество. Имеем m < к, так как104Глава 2. Алгебраические структурыX — базис. Покажем от противного, что У г е 1 ..га (w(yi) < w(xi)).
ПустьЗ г е 1..га (гу(уг) > гу(^г))- Рассмотрим независимые множества А = {х\,... ,£*_].}и В = {г/1,..., Vi-I,yi}. Имеем 3j ^ г ( { x i , . . . ,Xi-I,yj})— независимое множество. Тогда w(yj) ^ w(yi) > it;(rci), откуда следует, чтоЗр ^ i (w(xi) ^ ... ^ w(xp~\) ^ Цг/j) ^w(xp)),что противоречит тому, что х р — элемент с наибольшим весом, добавление которого к множеству { x i , . .
. , xv-i) не нарушает независимости. Следовательно,Уг (ги(уг)) ^ w(xi) и, значит, w(Y) <[ <*= ] Пусть М = (Е\ £) не является матроидом. Если нарушено условие М 2 ,то есть ЗА, В (А с В е £), но А £ £, то определим функцию w следующимобразом:, чI 1,w[e): = <|0,если е е А:если е еЕ\А.Тогда но алгоритму 2.2 А <£. X ==>• w(X)выполнено, но нарушено условие Мз, толюбого элемента е е В \ А множество АТогда р < к. Выберем число е так, что 0 <следующим образом:< w(A) = w(B). Если же условие М 2ЗА, В (\А\ = к) к \В\ = к + 1 и для+ е — зависимое. Пусть р: = \ А П В\.е < 1 /(к - р).
Определим функцию w1 + Е, если е € А\w(e): = < 1,если е е В\А\О,в остальных случаях.Заметим, что при таких весах жадный алгоритм сначала выберет все элементыиз Л и отбросит элементы из В\А. В результате будет выбрано множество X, вескоторого меньше веса множества В. Действительно, w(X) — w(A) — к(1 + е) —= ( f c - p ) ( l + e ) + p ( l + e ) < (fc-p)(l + l / ( f c - p ) ) + p ( l + e ) = ( k - p + l ) + p { l + e ) == w(B).•ЗАМЕЧАНИЕТот факт, что семейство £ является матроидом, означает, что для решения поставленнойэкстремальной задачи можно применить жадный алгоритм, однако из этого не следует,что не может существовать ещё более эффективного алгоритма.
С другой стороны, еслисемейство £ пе является матроидом, то это ещё не значит, что жадный алгоритм пе найдетправильного решения — все зависит от свойств конкретной функции w.ОТСТУПЛЕНИЕЖадные алгоритмы и их свойства были исследованы сравнительно недавно, по их значение в практике программирования чрезвычайно велико. Если удаётся свести конкретнуюэкстремальную задачу к такой постановке, где множество допустимых вариантов (изкоторых нужно выбрать наилучший) является матроидом, то в большинстве случаевследует сразу применять жадный алгоритм, поскольку он достаточно эффективен в практическом смысле. Если же, наоборот, оказывается, что множество допустимых вариантовКомментарии105не образует матроида, то это «плохой признак».
Скорее всего, данная задача окажетсятрудпорешаемой. В этом случае целесообразно тщательно исследовать задачу для предварительного получения теоретических оценок сложности, чтобы избежать бесплодныхпопыток «изобрести» эффективный алгоритм там, где это па самом деле невозможно.2.6.5. Примеры матроидовНиже приведены некоторые примеры матроидов, встречающихся в рассмотренных областях дискретной математики.
В последних главах книги имеются дополнительные примеры матроидов, связанных с графами.1. Свободные матроиды. Если Е — произвольное конечное множество, тоМ = (Е, 2е) — матроид. Такой матроид называется свободным. В свободномматроиде каждое множество независимое.2. Матроиды разбиений. Пусть {Е\,..., Ек} — некоторое разбиение множества Ена непустые множества.
Другими словами,Е к = Е, Ei П E j = 0, E j ф 0 .Положим Е: = {А С Е \ 1 ^П Е^}, то есть в независимое множество входитне более чем один элемент каждого блока разбиения. Тогда М = (Е, £) —матроид. Действительно, условие М2 выполнено. Если А, В е £ и | £ | = |J4| + 1,то Б г (\Ei П А\ = 0 к \Et П В\ = 1). Обозначим е: = Е{ПВ. Тогда А + е е £.Значит, выполнено условие Мз.3. Векторные пространства. Линейно независимые множества векторов любоговекторного пространства образуют матроид. Действительно, условия М\ и М 2 ,очевидно, выполнены для линейно независимых множеств векторов. УсловиеМ4 выполнено по теореме подраздела 2.4.3.4. Матроид трансверсалей.
Пусть Е — некоторое множество и £ — семействоподмножеств этого множества (не обязательно различных), £ С 2Е. Подмножество А с Е называется частичной трансверсалью семейства £, еслиА содержит пе более чем по одному элементу для каждого подмножества Eiсемейства £. Частичные трапсверсали над Е образуют матроид (см. [8]).КомментарииТак же как и в предыдущей главе, сведения, изложенные здесь, настолько общеизвестны, что конкретные ссылки ниже следует рассматривать как примеры, а пекак единственно рекомендуемые источники. Конкретные алгебраические структуры разделов 2.2-2.5 описаны в [24], [7], [31].
Книги [31] и [7] могут бытьиспользованы как введение в общую алгебру. Учебник [13] также содержит необходимые сведения из общей алгебры, включённые в контекст изложения дискретной математики и комбинаторики. Монография [3] исчерпывающим образомосвещает важные для приложений вопросы, бегло затронутые в подразделе 2.5.5.Описание жадных алгоритмов приводится в [8].Глава 2. Алгебраические структуры106Упражнения2.1. Пусть па множестве вещественных чисел заданы две операции:*(а, 6 ) : = а + Ьи+ (а, Ь): = шах(а, 6).Показать, что обе эти операции ассоциативны и коммутативны, операция +идемпотентна, а операция * дистрибутивна относительно +.2.2. Пусть L = f {ах + b \ a, b е R} — множество линейных функций. Операциялинейной замены переменной определяется следующим образом:Def(ах + Ь) о (сх + d) = (а(сх + d) + b) = (ас)х + (ad + b)).Доказать, что множество линейных функций образует группу относительнолинейной замены переменной.2.3.
Пусть на множестве пар вещественных чисел R 2 определены операции+, *: R 2 х К 2 —• К 2следующим образом:Def(a,b) + (c,d)=(а + с, b + d),f(a,b)*(c,d)=(ac,bd).Доказать, что X = f (R 2 ; + , *) образует коммутативное кольцо.2.4. Показать, что множество вещественных чисел R с операцией + являетсявекторным пространством над полем рациональных чисел Q, где операцияумножения на скаляр — это обычное умножение. Доказать, что это пространство не имеет базиса.2.5. Доказать, что булейы алгебры из примеров 1 и 3 подраздела 2.5.5 изоморфны,если \М\ = |Т|.2.6. Доказать, что семейство подмножеств Ъ с 2Е является базисом некоторогоматроида £ над множеством Е тогда и только тогда, когдаV B i , B 2 e ® (ei 6 Bi \В2Зе 2 G В2 \ Bi ((Bi + ег + е2) € £)).Глава 3Булевы функцииДанная глава имеет двойное назначение.
С одной стороны, помимо основныхфактов из теории булевых функций здесь затрагиваются весьма общие понятия,такие как реализация функций формулами, нормальные формы, двойственность,полнота. Эти понятия затруднительно описать исчерпывающим образом на выбранном элементарном уровне изложения, но знакомство с ними необходимо.Поэтому рассматриваются частные случаи указанных понятий на простейшемпримере булевых функций. С другой стороны, материал этой главы служит для«накопления фактов» и овладения базисной логической техникой, что должносоздать у читателя необходимый эффект «узнавания знакомого» при изучениидовольно абстрактного и формального материала следующей главы.3.1.
Элементарные булевы функцииПодобно тому как в классической математике знакомство с основами анализаначинают с изучения элементарных функций (рациональные функции от вещественной переменной х, ех, In я их суперпозиции), так и изложение теориибулевых функций естественно начать с выделения, идентификации и изученияэлементарных булевых функций (дизъюнкция, конъюнкция и т. д.).3.1.1. Функции алгебры логикиФункции / : Е2 —• Е2, где Е2 = f {0,1}, называются функциями алгебры логики,или булевыми функциями от п переменных, по имени Дж. Буля 1 . Множествобулевых функций от п переменных обозначим Рп, Рп = {/ | /: Е2 —> Е2}.Булеву функцию от п переменных можно задать таблицей истинности:1Джордж Буль (1815-1864).108XI0001Глава 3.
Булевы функции. •.ХП — 1 ХП001010/С® 1» • • , Х П )ДО,. .,0,0)Д о , . .,0,1)До,- .,1,0)11Д1,- • ,1,1)Если число переменных равно п, то в таблице истинности имеется 2 П строк,соответствующих всем различным комбинациям значений переменных. Следовательно, существует 2 2 " различных столбцов, каждый из которых определяетбулеву ф у н к ц и ю от п переменных.
Таким образом, число булевых ф у н к ц и й от ппеременных с ростом п растет весьма быстро:|Рп|=22".ЗАМЕЧАНИЕЕсли нужно задать несколько (например, к) булевых функций от п переменных, то этоудобно сделать с помощью одной таблицы, использовав несколько столбцов:Х\0......Хп01...1fi(xi,...,хп)/ 1 ( 0 , . . . , 0)fk(xi,..., хп)Л ( о,...,о)/l(l,...,1)Такая таблица будет иметь 2п строк, ть столбцов для значений переменных и ещё к столбцов для значений функций. Вообще говоря, значения переменных можно пе хранить,если принять соглашение о перечислении наборов переменных в определённом порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
