Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 82

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

примеры таких задач в (22~), то это свойство также инвариантно. 398 Второе важное понятие, до конца еще не исследованное, — это понятие полиномиальной трудоемкости проверки и связанный с ним класс РС. Если верно, что Р-ь РС, то это означает существование обширного класса задач, для которых проверить правильность предъявленного ответа существенно проще, чем найти ответ. И наконец, понятие УР-полноты выделяет обширный класс задач (среди которых много известных комбинаторных задач), которые в инвариантных терминах эквивалентны по трудоемкости и являются самыми трудоемкими среди задач классов РС и ИР. Можно доказать, что либо Р= РС =ЯР, либо Рс:.РСс:(УР, где оба включеиия— строгие, В.З.

МЕТОД ВЕТВЕИ И ГРАНИЦ Исследование проблем перебора в $9.1 показывает, что среди разрешимых задач могут быть хорошо н плохо реализуемые. Однако подобно тому, как в неразрешимой задаче возможны разрешимые частные случаи, так и в «плохой» задаче возможны «хорошие» частные случаи. Как правило, это объясняется тем, что при некоторых конкретных значениях исходных данных задачи удается полный перебор заменить перебором с отсечениями; иначе говоря, найти такие «хорошо» вычислимые условия, которые позволяют отбрасывать некоторые подмножества вариантов, удовлетворяющие этим условиям (т. е.

не выполнять для них перебор). Наиболее типичным вычислительным методом сокращения перебора является метод ветвей и границ, к рассмотрению которого мы переходим, Этот метод нельзя назвать алгоритмом, поскольку его основные блоки (и прежде всего, вычисление условий отсечения) зависят от конкретной задачи; скорее, это вычислительная схема.

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

Требуется среди вариантов найти оптимальный, т. е. такой, на котором функция Р принимает минимальное значение (или максимальное в зависимости от условия задачи). Метод ветвей и границ отыскания оптимального варианта состоит из ветвления и отсечений, Рассмотрим сначала ветвление. Принимаем какой-либо принцип разбиения множества М на подмножества Мг такие, что ()Мг=М, М1ПМ1= О, 1'чь)'. Затем, пользуясь этим же принципом, разбиваем полученные множества на части и т.

д. После некоторого шага разбиения каждое множество содержит по одному варианту. На каждом шаге вариант, оптимальный для всего множества М, принадлежит одному из М; и является для него оптимальным. Поэтому его достаточно искать среди оптимальных вариантов для подмножеств М„составляющих множество М. Этим самым решение задачи для всего множества М сводится к решению задач для составляющих его множеств М; и последующему отысканию оптимальных среди найденных для ннх решений.

Процесс разбиения множества М на подмножества становится наглядным, если его изобразить с помощью ориентированного графа следующим образом. Каждому множеству Мь полученному при последовательном разбиении множества М на части, ставится в соответствие вершина графа. Обозначим вершины графа так же, как и множества, которым они соответствуют, т. е. Мь От вершины М1 к вершине М; проводим направленное ребро, если множество М; получено непосредственным разбиением на части множества Мь Полученный граф является деревом, поскольку в каждую его вершину входит единственное ребро и граф имеет одну начальную вершину '. Построение дерева с помощью разбиения множества вариантов на подмножества называется ветвлением.

Построенное указанным ранее способом дерево имеет число конечных вершин, равное числу элементов (вариантов) в множестве М: для каждого варианта одна конечная вершина, Такое дерево назовем деревом полного перебора. Пример 9.1. Построить дерево путей из о, в ое в графе рис. В.4.

Р е ш е н и е. Таких путей н рассматр))ваемом графе шесть: 41 (о1~ оз о6) ~ ь'2 (о1 о4 оз) ~з (11 оз 14 о6)ю ' В более общем случае может быть рассмотрено разделение множества на пересекающиеся подмножества. Кроме того, в некоторых задачах производится разбиение одного и того же множества на части несколько раз различными (независямыми) способами.

В общих случаях граф, изображающий процесс разбиения, не является деревом. ~'4 (см пм г~э ом ов) ~$ г~м г~э г» о6) ~в = ("1 "и оа ."а). Ветвление производим по принципу; множество М; путей, проходящих через вершину оь разбиваем на непересекающиеся подмножества М; путей, содержащих ребра (оь о~). На рис. 9.5 изображено дерево всех путей (полного 2 5 перебора).

В вершинах римскими цифрами указаны номера путей, образующих соответствующие множества. Пусть маршрут — это ч путь в дереве от его корня к какой-нибудь конечной вершине. Функция г" определена на конечных вершинах дерева полного перебора. Каждой конечной вершине такого дерева соответствует один и только один маршрут с концом в этой вершине. Поэтому функция г' — это функция от маршрута. Оценочные функции. Оценки.

Разбиение множества на подмножества и независимое их рассмотрение приобретает смысл лишь в случае, если иа некоторых этапах построе- 26 — 760 Риа 9.5 ния дерева полного перебора удается установить, что в каком-то подмножестве нет варианта, оптимального для всего множества. Дальнейшее ветвлзнив в этой вершине не происходит. От дерева полного перебора отсекаются ветви с корнем в ней (отсекаются вершины и ребра, следующие за ней), Исключение множеств вариантов из рассмотрения производится с помощью оценочных функций.

Оценочная функция — это функция лг(М;) =лть заданная на вершинах дерева полного перебора, возможно, исключая корень, и равная в его конечных вершинах соответствующим значениям функции г, а в остальных вершинах М, дающая нижнюю или верхнюю границу значений функции Г для вариантов, входящих в множество Мь Оценочная функция, дающая нижнюю границу, в процессе разбиения множества иа части пе убывает, а дающая верхнюю границу — не возрастает. Действительно, пусть лг(М;)= т~ — оценочная функция, дающая нижнюю границу. Это значит, что все значения вариантов из множества М; не меньше числа ть Тогда для любого подмножества М~ нижняя граница значений вошедших в него вариантов не может быть меньше ть Поэтому если для некоторой части М, не находится значение оценочной функции, большее ть считаем его равным т,.

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

Поэтому дерево полного перебора зависит, вообще говоря, от выбора оценочной функции. Рассмотрим несколько примеров оценочных функций. Пример 9.2. Пусть каждому ребру (М„М~) дерева полного перебора поставлено в соответствие некоторое число А~- О. Требуется среди маршрутов С найти такой, для которого величина г" (Е) = ~ г(ы принимает минималь(мюмо сь ное значение. с Функция т;=~я',Ни, где суммирование производится 1 лишь по ребрам, входящим в путь от корня до вершины Мь за является оценочной функцией, дающей нижнюю границу. Пример 9.3. Если в дереве полного перебора примера 9.2 все конечные вершины имеют ранг и, то оценочной функ.

цией, дающей нижнюю границу, является н функция л т! = ~~~~ Йаг+ ~~)' гп(ос(аг, (9. 1) ! !+! где минимумы ищутся среди значений с(е! для ребер Мг-ветл ви, начала которой имеют одинаковый ранг, знак '~ ознаг+1 чает суммирование по рангам начал этой ветви (отсчитываемым от М;). Аналогично функция а и, = '«' г(а! + ~' !пах г(ц (9,2) г, г+! является оценочной функцией, дающей верхнюю границу. Пример 9.4. Если конечные вершины дерева полного перебора имеют неодинаковые ранги, то в примере 9.3 оценочные функции т! и и; принимают вид: 5 т! = ~~~~~Нц + лт',пппс(а!, и! = '«~~На!+ ~тахдаг, (93) ! г+! ! г~~~ где знак ч~~~ означает суммирование по рангам начал Мс-ветвь! ви, в которых представлены все пути, выходящие из Мь а знак ч', — суммирование по рангам ребер, в которых имег+! ется хотя бы один путь, выходящий нз Мь В примерах 9.2 — 9.4 для построения оценочной функции были использованы конкретные свойства изучаемых в задаче объектов (неотрицательных слагаемых с(а! и оценка их значений цо рангам).

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