) Точнее, с не большей стоимостью.- Прим, ред.

2. Предположим, что вершину Xj прикрепили к вершине mj (которая является, например, вершиной Xj). Пусть вершина Xj будет к-й. ближайшей вершиной к некоторой еще не прикрепленной вершине Х) (; < / п), соответствующей у-му столбцу матрицы М, т. е. т^] = Xj. Тогда, очевидно, все элементы

с 1> к могут быть исключены из дальнейшего рассмотрения (отмечены), поскольку, прикрепив Ху к Xj, мы тем самым причисляем Xi к медианным вершинам и поскольку вершина Xj может быть прикреплена к х,- с меньшей стоимостью ), чем к любой другой вершине при I = к + i, к -\- 2, ... . Ясно также, что если на некотором шаге возвращения процедуры поиска изменится распределение вершины xj относительно Xj, то элементы rriif (неиеключенные из рассмотрения, неотмеченные) должны быть рассмотрены заново.

3. Пусть вершина Xj- прикреплена к вершине т^}-. Тогда можно предположить, что все вершины lUiji, т^у, . . ., mik-Dj не являются медианными вершинами, поскольку в противном случае вершина ху была бы расположена по крайней мере от одной из них не дальше, чем от т^ч' (с меньшей ) результирующей стоимостью). Эти вершины, следовательно, могут быть отмечены (исключены из рассмотрения) во всех столбцах с номерами j > /. Нужно иметь в виду, что вершины эти исключаются временно и их надо восстанавливать всякий раз при изменении распределения вершины Xj относительно mj.

4. Если из рассмотрения исключены t верхних элементов /-го столбца, соответствующего нераспределенной (неприкрепленной) вершине xj, и {t + 1)-й элемент, т. е. m(t+i, } является медианной вершиной, то Xj должна быть прикреплена к вершине m+lj. В этом случае нет необходимости рассматривать какие-либо другие возможности до тех пор, пока некоторые из t верхних элементов не окажутся восстановленными (вследствие изменения в предыдущих распределениях вершин, что отразится на множестве исключенных вершин). Этот вывод является прямым следствием вышеприведенных замечаний 2 и 3.

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

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

Предположим, что выполненные прикрепления (включая прикрепление вершины Xj) дали р' (р' <.р) медианных вершин. Тогда оставшиеся прикрепления должны привести к нахождению остальных р - р' медианных вершин. Пусть J - множество индексов еще не распределенных вершин. В общем случае J есть множество индексов /, для которых <]п, за исключением индексов тех вершин, распределение которых индуцировано распределением первых вершин Xi, х^, . . ., Xj> (в соответствии с замечанием 4).

Пусть тпа^] и тгер; - самый верхний и следующий за ним элементы /-Г0 столбца, которые являются неотмеченными (не исключенными из рассмотрения). Тогда наилучшим распределением вершины Xj будет ее прикрепление к вершине тпар. Если число различных вершин тпа j для j J равно h ж h = р - р', то все эти наилучшие распределения еще не прикрепленных вершин являются осуществимыми (т. е. получается множество, содержащее р медианных вершин). Эти распределения образуют оптимальное пополнение частного решения, полученного при распределении вершин Xj, х^, . . ., Xj-. В таком случае записывается результат и шаг возвращения может быть предпринят с текущего частного решения.

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

v,[d {Xj, .j) - d {Xj, maj)] (6.20)

no всем вершинам Xj, j g /.

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

S Vj d {Xj, m.5)

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

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

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

5.3. Другой алгоритм направленного поиска

Рассмотрение альтернативных распределений, возникающих при выборе конкретных значений для переменных gj;, приводит в процедуре поиска из разд. 5.2 к частным подзадачам. Укажем еще одну процедуру поиска [18]; она состоит в построении бинарного дерева поиска, причем это построение осуществляется путем последовательной проверки условия: является или нет данная вершина медианной вершиной? Процедура поиска в этом случае задается множествами S*, S~ vi F. Первое множество соответствует тем вершинам, которые в текущий момент являются медианными, второе соответствует немедианным вершинам, а третье - вершинам, о которых пока нельзя сказать ничего определенного.

Нижняя граница стоимости оптимального решения, определяемая уже осуществленным распределением некоторых вершин по множествам S* или S~, может быть вычислена [18] способом, аналогичным приведенному в предыдущем разделе.

Итак, вершина Xj S~ должна быть прикреплена к некоторой вершине множества S* \j F. Наилучшее из этих распределений имеет стоимость

Ui=mmJVjd{xj,Xi)] (g 2i)

С другой стороны, вершина Xj F, которая не может стать медианной вершиной, должна обладать стоимостью, равной по крайней мере

uj= min [vjd{xj, Xi)]. (6.22)

Нижняя граница вычисляется по формуле

S и- + и\ (6.23)

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

В работе [18] оценка из выражения (6.23) используется при древовидном поиске специального типа (равностоимостного). При