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

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

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

Итак, вершина должна быть прикреплена к некоторой вершине множества Наилучшее из этих распределений имеет стоимость

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

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

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

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

таком поиске ветвление производится в узлах дерева, соответствующих наименьшей нижней границе решения. Методы поиска с приоритетом по глубине, аналогичные тем, которые рассматривались в начале настоящего раздела и в которых используются оценки, подобные приведенной в выражении несколько модифицированные, чтобы можно было решать обобщенные -медианные задачи, возникающие на практике при размещении складов (пунктов обслуживания), — встречаются также в работах [29, 30, 15, 7, 28].