Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 78
Текст из файла (страница 78)
Значения переменных пн Хн ..., Хэмн, пм Ун -., Учч»н описываются словами некоторого алфавита. Добавим к последнему разделители ', ' и '; '. Тогда вариант данной массовой задачи можно описать словом пь Хь Хм-, Хэыо состоящим из подслов, описывающих переменные, н разделителей, Произведение длины этого слова на двоичный логарифм количества ( символов употребляемого алфавита (в их число входят разделители) мы назвали раньше размерностью варианта данной задачи. В отличие от семантической размерности ее можно назвать информационной размерностью. Аналогично конструируется слово пь Уь ..., Уэмн — гипотетический или настоящий ответ. Комбинаторные задачи перебора.
Будем рассматривать такие комбннаторные задачи, у которых для любого описания варианта длина описаний (т.е. размерность) возмож'- ных ответов ограничена значением 5(п„п2), где 5 — это рекурсивная функция. Можно считать, что длйны описания варианта и ответа ограничены одним и тем же числом 5. Если ( — мощность алфавита, то этому ограничению удови+' — 1 летворяет не более чем (+Р+...+(з= возможных ~ — 1 ответов, В этом случае при заданном варианте ответы У можно перебирать по очереди и для каждого из них выяснять, нстинен ли предикат Р',""" (Х, У).
Задача называется задачей перебора, если для любого ее варианта размерность ответа ограничена н предикат Р',""* (Х, У) разрешим. Очевидно, что задача перебора всегда разрешима, хотя, быть может, н с очень высокой сложностью. Комбинаторная проблема Поста (5 6.4) не является задачей перебора: ее предикат Р",'"* разрешим, но размерность ответа не ограничена. Для проблемы остановки ответ можно понимать по-разному: как двоичную переменную («да» или «нет») или как протокол (последовательность конфигураций) работы машины. В первом случае предикат Р"„'"* неразрешим; во втором случае он разрешим, но не ограничена размерность ответа. 376 Займемся приведением массовых задач перебора к не.
которому стандартному виду. Пусть 5 фиксировано„Можно уравнять длины описаний вариантов и ответов, добавив к алфавиту пустой символ ° и поставив в начале слишком коротких слов недостающее количество таких символов. Затем мы перейдем к двухсимвольному алфавиту 0,1 способом, который уже не раз рассматривался в этой книге. Информационная размерность почти не изменится: вместо 3 1онз1 она станет равной гл=Ы ' 1он2(1+1)], где ] и ]— наименьшее целое число, удовлетворяющее неравенству ( и ] )и, Таким образом, допустимые варианты и гипотетические ответы можно считать последовательностями т двоичных переменных — соответственно х (хь ..., х ) н у(уь...,д ) можно рассматривать только массовые задачи перебора, определяемые предикатами Р (хь хь ..., х, уь ум ..., у ), зависящими от двоичных переменных. Примеры.
Один пример — задача РЕЕТ вЂ” уже был рассмотрен, Другой пример — определение натурального числа в+1, следующеге за данным числом и. Если число и изображено числом единиц: 1 — один, 11 — два, 111 — три и т. д„ то к такой последовательности надо прибавить 1. Однако размерность задачи при таком способе изображения переменных слишком велика. Обычно ее рассматривают для чисел п, изображенных в двоичной позиционной системе.
Предикаты массовой задачи перебора Ю (хь хь -,, х, уь ум .., у,), где двоичные переменные х1, хз,..., х представляют данное и-разрядное число л, а двоичные переменные уь дм ...„ у — искомое число а+ 1, можно определить ийдуктивно вместе с предикатами тождества Е (х„ х , ... , л , у , у,„ ... , д ): Е'(хм дг)=(хдйд1) >/( ]х а ]у)', №(хм дД= ~х1йд~; Е (х„х„..., х, у„у„..., у ) = »> — 1 =Е (х„х„..., х,> — 1> у> уз, ...
> ут — ~)й й((х йу )~/( ~х й,у )); л1 (х,,х,,...,х,у„у.„...,у) ~хщйд йЕ"' '(х„х,,...,хп, 1,дму„ .„, у„1)) ~/(х,„й ]у,„йй '(х„х,, „.,х н у„у„... ..., у 1)) (т=2, 3, ...). 377 То, что в этих формулах по существу использовано понятие следующего натурального числа (за т — 1 следует т), не создает порочного круга: при т=2,3 можно выписать явные формулы, а т~4 изображаются числами более короткой длины ( !ояз т ~, для которых понятие следующего натурального числа было ранее определено.
Отметим еще, что при заданных хь хм ..., х существуют единственные значения уь ум ..., у — ответ рассматриваемой массовой задачи, кроме случая, когда х,=х»=...=х =1. Увеличив размерность задачи на 1 и произведя стандартное отображение варианта в вариант большей размерности: х1=0; х~=х;, (1=2, 3, ..., т+1), можно решить задачу и в этом случае. Следующие примеры будем рассматривать на «содержательном» уровне, не увлекаясь излишней формализацией. Задача о камнях, Даны п камней с целыми весами хь хь..., х . Можно ли выбрать некоторое количество из них так, чтобы сумма их весов была равна данному числу М? Введем двоичные переменные уь ум ..., у„. Наша задача — это уравнение х,у, +х,у,+ ... +х„у, =М Таким образом, Р,(х„х,„..., х„, М, у„у», ..., у4 = = (х, у, + х, у, + ...
+ х„у„= М). У варианта задачи о камнях либо нет решения, либо размерность решения меньше размерности описания варианта. Многомерная задача о камнях, Пусть камни имеют несколько параметров: веса .т,', х,', ..., х„', объемы х~и х~, ..., х~ и цены в разных валютах нлп в разные времена х',', х,',.„, х' (1=3,„., й). Требуется найти значения двоичных переменных уь уь ..., у, чтобы выполнялись равенства х~у»+хну~+ ... +Х»у» =М~(1= 1, 2„..., Й). Значения х; и М~ — целые числа, обычно неотрицательные. Часто рассматривают задачу с неравенствами » х(Ут~<Мг (1ЕР С:(1 2 - 1))1 / 1 378 л ~~~ х/у!)~М/(Е/-.-"Р = (1, 2, ..., Е)",Р ) /=! (если не требовать неотрицательности х;, то все условия можно привести к виду ~', х/у!'сМ/).
Увеличив размер/=.! ность задачи (можно показать, что полнномиальным образом), ее можно свести к задаче с равенствами. Добавим двоичные переменные ои(/=1, 2,..., Е, 1=и+1,..., а+ +ЕЛ 1оисМ; )) и для 1=а+! положим х/=2' Тогда наша система с неравенствами эквивалентна задаче л +с.! !ое„м ~~~ х/!ус + ~~~~ хс'ус/ = М, (Е Е: Р~)/ /=-! /=л+! л л+л~ !ос,м ! л+/.!. !осьм.с ~хсу/+ ~ х о! — — М + ~~~ х/(Е/---Р~). с=! /=~с+! /=л+! Действительно, из неравенства ~,' х/у/~М/ следует, что /=! л ~ч~х/у/=М вЂ” сес, где Яс — неотрицательное число, не пре/=-! восходящее Мс. Пусть ес,с!оглмс, ес.сме,м -!,:., ем е!— представление Яс в двоичной позиционной системе. Это значит, что / !оа,м, ! †! (сс =ец+2ем+2'е„+ ...
+2 ' еь/ „е,м,, (с с: Рм). Положим оп=ел/ !, х/ =2' " (/с<Е~п+1 !о~с Мс) ). Тогда будут выполняться соответствующие равенства. Для л л остальных неравенств ~х/у/=Мс+Яс, причем Яс ~ х,' ! 1 / ! (предполагаем, что Мсьб). Рассмотрим аналогичное представление числа Яс и положим оп=1 — ец/ !(Е'=и+1, ... л ..., и-(- 1оне~ч~ х,' . Тогда будут выполняться оставшиеся /=1 равенства. Тот факт, что из выполнения этих равенств следует выполнение исходных неравенств, доказывается без труда.
Задача о покрытии множества подмножествами. Пусть 379 дано конечное множество )!(и!, пм ..., и„) и система его подмножеств йг!=(оь!,о!,;!,..., о д „,)(!=1, 2, ..., 1). Эту систему можно задать матрнцей !!х!!~~,='!,;=!, где 1 если и!6:)Р! х,,= О, если птбсК!. Требуется выяснить, существуют ли я подмножеств йг!, покрывающих все множество )!.
Введем двоичные перемен- ные у!(!=1, 2, ..., Е). Значение у!=1 соответствует выбору подмножества )Р! в состав покрытия. Рассматриваемая задача эквивалентна системе условий ! ! ~~хмрл) 1(1 = 1, 2, ..., и); «~У! = л. !=! ю=! Выполнимость конъюнктивной нормальной формы. Пусть х!, хм ..., х„— двоичные переменные, ! Ф(х хь» х ) й (Б! '/ Бгз ~/ / ь! (о) !=1 где каждое $!! — это одна из переменных хь или ее отрица- ние 1хл(1<6(п). Требуется найти значения переменных хь хм, х„, для которых Ф(х!, хм ..
х„) =1, или доказать, что данная конъюнктнвная нормальная форма Ф(х!, хь ... ...,х„) тождественно равна О, В крайнем случае достаточно только узнать, существуют ли такие значения х!, хм ..., х , что Ф(х!, хь ..., х„) =1, а самих значений не указывать. Если задача об определении значения предиката Ф имеет полиномиальную трудоемкость, то трудоемкость за- дачи о выполнимости конъюнктивной нормальной формы тоже полиномиальна, Действительно, пусть последняя за- дача имеет трудоемкость 1 (она разрешима, как всякая массовая задача перебора).
Положим х,=1. Если в выра- жении ($!!~/...~/$!по) есть некоторое $!! =х„тотакоевы- ражение будет равно 1; если в нем есть $!!= 1х, то оно равно дизъюнкции Яп, ~/...~/$!л-!~/$!д+!~/...~/$!и !), в ко- торой ~!! исключена. Таким образом, при х! — — 1 Ф(х!,хз, ... ..., х„) будет равна конъюнктивной нормальной форме Ф'(хэ,...,х„). Решим задачу для нее, Если существуют зна- чения хь."~хл, для которых Ф (хм -.~ х!!) — 1! то можно вы брать х!=1.
Если же таких значений нет, то, так как Ф(х!, хь ..., х„) может быть равно 1, х! нужно положить равным О и рассмотреть аналогичную конъюнктивную нормальную форму Фо(хз,..., хь). Таким же образом можно выбрать затем допустимые значения хь ..., х . Понадобится решить и задач о выполнимости конъюнктивных нормальных форм все более низких размерностей. Задача о выполнимости конъюнктивной нормальной формы сводится к многомерной задаче о камнях.
Рассмот- рим 2п двоичных переменных у!, уъ.-, у, уп+!,, узо и систему условий у -1- у, = 1 (! = 1, 2, ..., и); зо ~» хзл ул )~ 1 (! = 1, 2, ..., 1), л=! где при 1(Й<п х„' 1 в том и только в том случае, когда среди $!! есть значение, равное хл, а при М)п — равное )хл . Легко видеть,что сконструированы условия задачи о камнях, и онн выполняются тогда и только тогда, когда выполняется условие Ф(х!, хз, ..., х ) =1, причем у;=х! при з=1, 2,..., п ну!= ~х! при з=п+1, ..., 2п. Классы трудоемкости задач. Задача принадлежит к л а с с у Р, если существует машина Тьюринга, на кото- рой она решается с трудоемкостью, полиномиально завися- щей от параметров ее размерности, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
