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

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

Можно доказать, что й(л) пе убывает при возрастании л. Оценим й(л). Пусть мы спрашиваем о множестве Мь содержащем л, шариков, л,<л. Если зиачспие оценочной функции т(М~) =1, то ва выделение радиоактивного шарика из л, шариков требуется й(л,) вопросов, при т(М,) =6 требу ется я(л — л,) вопросов да один вопрос (о подмножестве М,) уже за.

дан. Поэтому (9 А) й (л) = ппп шах ) 1 + л (л ); 1 + А (л — л,)), э,<л Из (9.4) следует, что минимальное число проб получается, если каждый раз задавать вопрос о половине рассматриваемых шариков, л — 1 т. е, когда л, ) +1, л,=л — л,=~ л/2 2 Методом индукции лля й(л) получаем оценки (з — 1) < я (л) ~з, (9, 5) где 2'-'<л<2". Отсюда Г !она л 1 К л (л) < (1оиз (л — 1)) -(- ! . бнб) Действительно, непосредственно убеждаемся в том, что (9.5), (9.6) верно для л=2 и л 3.

Далее из предположения, что (9.5), (9.6) верно при 2'-а<и<2'-', и учитывая значения л, и лз, получаем, что вти оценки верны и при 24-'<л<2', Из (9.6) следует, что минимальное число й проб, достаточное для выделения из л шариков одного радиоактивного, меньше числа проб прн полном переборе. Это уменьшение получается с помощью оценочной функции; как было указано ранее, подмножества шариков, на ко. торых она равна нулю, иаждый раз отсекаются. Значение оценочной функции дли данного множества М! назовем его оценкой и обозначим оцМг=лть Она может не быть точной границей значений вариантов из Мь Чем ближе оценка к точной границе, тем эффективнее применение метода ветвей и границ, ибо число отсекаемых вершин де- 404 рева полного перебора зависит, в частности, от силы оценки.

Действительно, пусть в задаче отыскивается минимум и на некоторых подмножествах определены две нижние оценочные функции лт; и т;, причем т; — более точная, т. е, т,)ть Пусть найдено значение Га для некоторого варианта. Если для какой-то вершины Мь имеем т(Мь))Ро, то и и'(Мь))Ра и множество Мь не следует далее рассматривать, так как оно не содержит оптимального варианта. Но при т(Мь) (Г, может оказаться гп'(Мь))Р,.

Тогда при использовании оценочной функции т~ множество М,. нужно изучать дальше, а при использовании т,' этого делать не следует. К сожалению, обычно чем точнее оценка, тем больших по объему вычислений требует ее отыскание. Так как точность оценки зависит, в частности, от того, насколько целесообразен принятый принцип разбиения на части рассматриваемого множества вариантов, то при выборе способа разбиения из нескольких возможных следует отдать предпочтение тому иа них, при котором оценки полученных подмножеств более точные. Не менее важно, насколько сильно на этих подмножествах различаются между собой значения оценочной функции.

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

Отсечение по сравнению двух оценок. Его можно производить, когда для М~ строятся оценка снизу (ноцМ;) и оценка сверху (воцМ;). Если при этом для некоторых М~ и Му оказывается, что ноцМ~)воцМп то при отыскании минимума Е ветвление из вершины М; прекращается. В. Ветвление в данной вершине прекращается, если из,вестно, что соответствующее ей подмножество не содержит оптимального варианта или известен оптимальный среди принадлежащих ему вариантов. Порядок продолжения ветвления может быть выбран различными способами. Укажем основные из них.

1. Ветвление по минимальной нижней границе (при отыскании минимума Р). Сначала строятся (все или некоторые) ребра, выходящие из корня. Затем в каждый момент ветвление производится в вершине с минимальной из уже найденных оценок снизу. Для всех вершин, в которых производится ветвление, можно строить все ребра, выходящие из них в дереве полного перебора, либо только часть этих ребер. 2. Развитие дерева по ветвям (последовательное построение ветвей). Сначала строим один маршрут, включая его конечную вершину.

При этом получаем некоторое значение г",, которым можно пользоваться при отсечении множества вариантов. Пусть М~ — первая от конца этого маршрута вершина, такая, что еще не построено выходящее из нее ребро (Мь М;) и при этом оцМ~(Рм т. е. множество М; не отсекается (отыскивается минимум), Строим ребро (Мм М;) и достраиваем какой-нибудь из проходящих через нее маршрутов до конца либо до вершины, в которой происходит отсечение. Далее строим ребро (Мь М;) в первой от конца этого маршрута (от конца построенной его части) вершине Мь такой, что выходящее из нее ребро (Мь М~) еще не построено и при этом множество М~ не отсекается и т.

д. При таком способе продолжения ветвления в построенном дереве обычно больше вершин, чем при ветвлении по минимальной нижней границе, но запоминать приходится данные о меньшем количестве построенных вершин. Никаких точных оценок числа отсечений при различных способах продолжения ветвления указать нельзя, все соображения здесь носят эвристический характер. Пример 9.6. Используя оценку типа (9.3), найти путь максимальной длины из р~ в рз в графе рис.

9.2, На рис. 9.6 приведено решение при ветвлении по максимальной верхней границе, на рис. 9.7, а и 6 — при развитии дерева по ветвям. Количество построенных при этом вершин дерева зависит от очередности развития ветвей. На рисунках слева от вершин проставлены оценки, найденные по формулам типа (9.3), справа — номера вершин в порядке появления при построении дерева. 3. Еще один способ продолжения ветвления сочетает принципы рассмотренных ранее двух способов. Зададим некоторое число 6)0.

Пусть М~ — вершина, в которую мы 406 попали при очередном шаге ветвлений. Если оцМ~ превосходит минимальную из ранее найденных оценок не более чем на бгь где т~ — ранг рассматриваемой вершины, то ветвление продолжаем из этой вершины. В противном слу- Рис. д.б Рис. з.т чае производим ветвление в вершине с минимальной нижней границей. Отметим, наконец, что могут возникнуть дополнительные отсечения, если отыскивается не минимум функции Р, а лишь выясняется, существует ли значение Р, удовлетворяющее условию Р(М;))С. Задача об очередности выполнения работ. Постановка задачи. Пусть сеть комплекса работ задана рис. 9.8, где каждому ребру соответствует работа. Заданы постоянные продолжительности А всех работ сети (табл.

9.1). Рис. 9.8 Таблица 8.1 1 Номе Т 10зз 5 3 Продолжительность А 1О 4 6 Имеется нескладируемый ресурс в количестве 1 (например, башенный кран), который необходим при выполнении работ № 2„5, 8, 11. Для остальных работ он не нужен; потребность в других видах ресурса не учитывается (считается, что их всегда достаточно). Требуется указать такой порядок выполнения работ № 2, 5, 8, 11 (впредь будем их называть ресурсными), чтобы задержка выполнения комплекса работ по сравнению с критическим временем Т„а= 38 был минимальной. Обозначим: 1Р— ранний срок начала (-й работы (т. е.

момент, раньше которого опа пе может начаться), 1," — время начала 1-й работы, Р. — время окончания (-й работы; т,=Ад. Учитывая вид сети, для 1-й ресурсной работы имеем 1т =А-ь Ветвление. Всего имеется 24 варианта последовательности выполнения ресурсных работ (41=24). Разобьем их на подмножества вариантов, в которых первой выполняется одна и та же ресурсная работа.

Ее будем считать фиксированной. Это варианты с одинаковым началом. Таких подмножеств четыре (по шесть вариантов в каждом). 408 !! =1+ ~~~~ в(! 1 1Е)т! в!<ту 1Т+г(! !с=141 если в этом плане для всех 1 выполнено неравенство 1,". ~1вв, то он минимизирует величину гпах (1",+А+т; — 1). нил При решении задачи время 1 принимается равным сроку окончания последней из ресурсных работ, фиксированных в данной группе вариантов. Вычисления производятся с помощью таблиц такого типа, как табл, 9.2: 1," — срок начала Таблина 9.2 вн Т = 1"в + Ы + тв 1О 12 28 23 2 $ 8 1! 3 1О 6 !О 16 22 26 !8 32 32 36 Т .,=36 1-й ресурсной работы прн соответствующем в таблице порядке выполнения ресурсных работ; Т~ — длина пути (т.е.

суммарная продолжительность) от началыюй вершины к конечной, проходящего через 1-ю ресурсную работу. В табл. 9.2 приведены значения Т; для подмножества вариантов, в которых зафиксировано положение одной ресурсной работы — работы № 2. Имеем !а =10=!в! 2 =!в+в!в=10+5=15, 1в =14+в(в=15+ у=22; гй =!в+ввлв= =22+4=26, причем 1" =22(28=!вв. Из таблицы йолучаем нижнюю границу Т=тах(Тв! Тв! Тв! Тп)=36 продолжительности для всех вариантов рассматриваемого подмножества.

В первой строке табл. 9.2 выписаны данные для ресурс- 469 Далее полученные подмножества разбиваем на части, в которых фиксирован порядок выполнения уже двух ресурсных работ и т. д. Отсе ч е н и е. При отыскании оценок снизу будем опираться на следующий факт: пусть задан некоторый момент времени 1 и календарный план выполнения ресурсных работ нз некоторого их множества в( найден с помощью формул 8 5 2 11 28 12 !О 23 6 1О з 3 38 49 47 52 28 32 39 44 т„„„= 52 Поскольку здесь все 1;)гг, число Т=гпах Т,=82 равно минимальной продолжительности комплекса работ для множества вариантов, в которых первой из ресурсных работ выполняется работа № 8. Это время достигается при следующем порядке выполнения ресурсных работ: № 8, б, 2, 11.