5.2. Алгоритм направленного древовидного поиска

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

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

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

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

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

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

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

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

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

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

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

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

Если, однако, то для получения всех медианных вершин надо заменить по крайней мере лучших назначений на вторые лучшие или худшие. Тогда наименьшая дополнительная стоимость распределения является суммой наименьших разностей

по всем вершинам

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

суммы наименьших разностей, задаваемых выражением (6.20).

Может случиться, что меньше Тогда наилучшее пополнение текущего частного решения дает медианных вершин меньше

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