3.3. Задача о ближайшем соседе

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

Пусть объект представлен отрезком [0,M] и точки разбиения XkÎ[0,M] могут принимать только целые значения. Введем функцию F(X,Y)³ 0, 0£ X£ Y£ M, которая равна затратам, связанным с обслуживанием отрезка [X,Y]Í[0,M]. Запишем математическую модель задачи в случае фиксированного количества участков разбиения N.

Sn(M)=	(3.13)
.	(3.14)

Наряду с (3.13)-(3.14), рассмотрим семейство задач {(P(K,Y)), K=1,…,N, Y=1,…,M)}, где

(P(K,Y))

Представим, что задан отрезок [0,Y], YÎ[0,M], и известно оптимальное разбиение любого отрезока [0,X], X£ Y на K-1 часть. Тогда Sk(Y)=. Следовательно, рекуррентные соотношения для задачи (3.13)-(3.14) имеют вид:

Sk(Y) =

Таким образом, трудоемкость построения решения задачи (3.13)-(3.14) равна O(NM2), а память – O(NM).

В ЗБС количество отрезков разбиения может быть искомой величиной N>0. Если функция F(X,Y) неотрицательна, при любых допустимых аргументах, задача может быть записана в виде

	(3.15)
,	(3.16)

Со Строгими неравенствами (3.16). Конечно, эта задача может быть сведена к серии задач с фиксированным N=1,…,M. Однако ее решение может быть построено на основе простых соотношений:

(0) = 0; (Y) = {(X) + F(X,Y)}, Y = 1,…,M.

Действительно, если рассматривается отрезок [0,Y], YÎ[0,M], и известно оптимальное разбиение любого меньшего отрезока [0,X], X<Y на Оптимальное количество частей, тогда (Y) = .

Таким образом, решения задачи (3.15)-(3.16) находится с трудоемкостью – O(M2), и памятью – O(M).

Замечание 3.1. Говорят, что функция F удовлетворяет условию g, если для любых точек X1 £ Y1 £ Y2 £ X2 Î [0,M] выполняется неравенство

F(x1, x2) + f(y1, y2) ³ f(x1, y2) + f(y1, x2).

В [GimGleb1] подробно рассмотрены свойсва ЗБС в случае, когда функция затрат обладает свойством g. Показано, что в этом случае трудоемкость построения решения может быть уменьшена.

Замечание 3.2. Кроме приведенных выше постановок ЗБС, на практике встречаются случаи, когда количество отрезков разбиения должно принадлежать отрезку NÎ[K,K], где K и K заданные целые числа. Процесс решения таких задач описан в [Zadachnik].

Замечание 3.3. При решении задачи методом ДП во время прямого хода, при вычислении оптимальных значений целевых функций задач семейства, скажем Sk(Y), используются только значения Sk-1(Y), найденные на предыдущем шаге. Если не хранить всю таблицу значений Sk(Y), Y=0,…,Y, K=1,…,N, а также не запоминать условно-оптимальные решения, то можно сократить необходимую для реализации алгоритма память в N раз. Такой вариант ДП называется Релаксационным и состоит из (N-1)-го прямого хода. Сначала находятся Sn(Y) и оптимальное значение последней переменной X. Затем решается задача размерности N-1 с соответствующим значением Yn-1 (например, если решается задача о ранце, то Yn-1=Y-Anx). Получаем X и Yn-2. Повторяем прямой ход ДП для задач размерности N-2,…,2. Как видно, трудоемкость такого варианта ДП в N раз выше, чем у обычной схемы и вариант, который следует применять в каждом конкретном случае, определяется на основе сравнения критичности параметров трудоемкости и памяти.

< Предыдущая		Следующая >