неперекрываемости нельзя исключить Sj из рассмотрения, скажем, В блоке /2, если уже покрыто частным решением. Следовательно, Sj должно входить в каждый блок /2, /д, .... С другой стороны, поскольку элемент Vj из Sj согласно последовательной природе поиска покрывается перед ветвлением на множествах блока р (р >7а), то теперь возможно удалить все элементы Xj из Sj перед введением Sj в любой блок р /д. без какого-либо влияния на результат решения задачи. Эта тривиальная операция удаления с вычислительной точки зрения оказывается очень выгодной, поскольку исходная таблица в ЗНП теперь может быть сокращена с помощью правил, указанных в разд. 4.2, до значительно меньших размеров, что возможно осуществить без удаления элементов Xj (/ <; р) из множеств блока р [48].

Здесь следует отметить, что алгоритм из разд. 4.3 является примитивным поисковым алгоритмом, использующим дерево поиска, и лишен каких-либо тонкостей, хотя при тщательном программировании может быть сделан весьма эффективным для ЗНР 127]; это не так для ЗНП, даже при довольно скромных размерах. Далее мы рассмотрим некоторые важные условия и вычисление нижних границ, которые могут быть использованы для ограничения дерева поиска и улучшения эффективности основного алгоритма.

4.4.1. Некоторые важные условия. Прежде чем устанавливать общие результаты, мы проиллюстрируем зти важные условия на примере. Рассмотрим случай, когда блок 1 содержит (среди других) множества S- = {г^, Г4, г^} и S = {г^, Гд, г^} со стоимостями 3 и 4 соответственно, а блок 2 содержит множества = {г^, г^, г^} ш Si = {г2, / 4, Г5}, каждое со стоимостью, равной 2.

В процессе выполнения алгоритма из разд. 4.3 на некотором этапе получим В а = {Si, S3}, Еа = {г^, г^, . . ., г^}, Za = 5; затем ветвление будет продолжаться до тех пор, пока либо мы не найдем решение, которое лучше, чем текущее В, либо не установим, что Si и S3 не могут одновременно появиться в оптимальном решении.

Далее, через много шагов, мы достигнем такой ситуации, когда

Вь = {S S3}, Еь = {г„ . . ., г,}, Zb = 6

Здесь становится ясным, что дальнейшее ветвление делать не нужно, поскольку Еь Еа и Zb > Za- Подобная картина имеет место также при

Вс = {S2, S}, Е, = {Г1, . . ., Гд}, Ze = 6.

Таким образом, возможно, имеет смысл хранить для каждого значения z = 1, 2, . . ., z некоторый (быть может, неполный)

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

Пусть мы сохранили некоторый список L (z,) множеств Е, которые были получены в процессе выполнения алгоритма на некотором уровне с суммарной стоимостью Zj. Предположим, что на данном этапе Е - Е', В = В', z = z и мы заняты исследованием блока к (где к = min {i $ Е'} - см. шаг 2 в алгоритме из разд. 4.3) и выбором множества со стоимостью с] для следующего ветвления. Если z -f cJ <iz, то ветвление в рассматриваемом алгоритме с этого этапа продолжается дальше и

E = E[JS-, S = BU{j} 2 = z + c

независимо от каких-либо других соображений.

Однако можно также гарантировать (на шаге 3), что перед продолжением ветвления

Е' и $ El, iEi L{Zi) и при всех z,

для которых z<;ziz-f с^. (3.16)

Если S] не удовлетворяет приведенному выше условию, то оно отбрасывается и рассматривается следующее множество S]+\ блока к, и т. д. Если S) удовлетворяет условию (3.16), то можно продолжать ветвление дальше с S] так же, как и раньше, но с обновленным списком L (z), полученным добавлением множества Е' \]S] ъЬ (z + с]).

Поскольку, как упоминалось ранее, невозможно практически хранить полные списки L (Zj), то должны быть использованы некоторые эвристические критерии для определения размеров этих списков и способов их обновления в процессе поиска.

(А) Размеры списка. Лучше, очевидно, исключать множества S*l, которые могут оказаться ветвлениями дерева на его начальных уровнях, так как это может привести к отбрасыванию больших частей возможного дерева поиска. Таким образом, интуитивно ясно, что имеет смысл оставлять списки больших размеров L (z,), соответствующие меньшим z,-. Это подтверждается дополнительно

тем, что условие (3.16) выполняется с большей вероятностью тогда, когда множества Т содержат лишь несколько элементов, что имеет место для малых 2г-уровней.

(Б) Обновление списков. На определенном Zj-уровне текущее -множество (пусть это множество Е') является с большей вероятностью подмножеством такого множества Е (из списка L (z,)), которое получено из той же общей части дерева поиска. Это справедливо потому, что Е' и Е имеют общую большую часть цепи от начального узла до соответствующих этим множествам узлов дерева. Итак, кажется более выгодным расположить списки L (zj как стеки и использовать алгоритм FIFO первым пришел-первым ушел , согласно которому в случае переполнения стека отбрасывается множество, находящееся внизу.

4.4.2. Вычисление нижней границы. На некотором этапе поиска, определяемом В', Е', z, и когда блок к является следующим блоком, подлежащим рассмотрению, нижняя граница h для наименьшего значения величины z может быть вычислена и использована для ограничения дерева поиска следующим образом.

Рассмотрим непокрытый элемент Г; g /? - Е', который отсутствует в множествах блоков к, к -\- i - 1, соответствующих элементам, еще не покрытым частным решением. Тогда элемент г,- не может быть покрыт, пока некоторое множество S] блока i не выбрано для добавления к В' на следующем этапе. Итак, для каждого такого элемента строится строка для матрицы £) = = [dqs] и строка для второй матрицы D = [dJ, где d, равно числу элементов в множестве , а dq - стоимость множества Si.

Кроме того, к каждой матрице D и D добавляется дополнительная строка, скажем 9, с ds, = s для всех s = О, 1, ... .. .,М - I £ I и (ife = S min [с]/ \S]\], где минимумом берется по всем множествам S] таким, что rtE. Число элементов в строке qi матрицы D (или D) может быть отлично от числа элементов в другой строке q. Поэтому, добавив в конце строк О (нули) и оо (бесконечности) соответственно для матриц D и D, добьемся того, чтобы число элементов в разных строках стало одинаковым, скажем, равным /, а матрицы стали прямоугольными.

Теперь можно высказать ряд утверждений. Поскольку оптимальное решение текущей подзадачи должно покрывать М - - \ Е' \ элементов, то, выбирая по одному значению из каждой строки матрицы D с таким расчетом, чтобы удовлетворялось условие

(dis +d2s+----de,)M-\E\

и минимизировалась соответствующая стоимость V = {du + ...+(