4.4. Алгоритм решения ЗНП, использующий дерево поиска

В алгоритме, описанном выше в разд. 4.3, единственным шагом, характерным для ЗНР, является шаг 3 (i). Если удалить в этом шаге требование «неперекрываемости» то алгоритм может быть использован для ЗНП. Однако в этом случае исходная таблица будет несколько отличаться от табл. 3.2. Итак, положим где Теперь недостаточно включить только в блок поскольку без требования

«неперекрываемости» нельзя исключить из рассмотрения, скажем, в блоке если уже покрыто частным решением. Следовательно, должно входить в каждый блок другой стороны, поскольку элемент из согласно «последовательной природе» поиска покрывается перед ветвлением на множествах блока то теперь возможно удалить все элементы из перед введением в любой блок без какого-либо влияния на результат решения задачи. Эта тривиальная операция удаления с вычислительной точки зрения оказывается очень выгодной, поскольку исходная таблица в ЗНП теперь может быть сокращена с помощью правил, указанных в разд. 4.2, до значительно меньших размеров, что возможно осуществить без удаления элементов из множеств блока

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

4.4.1. Некоторые важные условия.

Прежде чем устанавливать общие результаты, мы проиллюстрируем эти важные условия на примере. Рассмотрим случай, когда блок 1 содержит (среди других) множества со стоимостями 3 и 4 соответственно, а блок 2 содержит множества каждое со стоимостью, равной 2.

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

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

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

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

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

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

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

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

Если не удовлетворяет приведенному выше условию, то оно отбрасывается и рассматривается следующее множество блока к, и т. д. Если удовлетворяет условию (3.16), то можно продолжать ветвление дальше с так же, как и раньше, но с обновленным списком полученным добавлением множества

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

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

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

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

4.4.2. Вычисление нижней границы.

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

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

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

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

и минимизировалась соответствующая стоимость

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

то оставшиеся элементы покрываются наилучшим образом, т. е. с минимальной стоимостью покрытия для каждого дополнительно покрываемого элемента.

Наименьшее значение для

легко может быть получено с помощью следующего алгоритма динамического программирования.

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

где придается начальное значение, равное для всех

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