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

К сожалению, применение принципа оптимальности и динами­ческого программирования к задаче коммивояжера не уменьшает существенно времени вычисления; оно только реорганизует его. Однако для других задач принцип оптимальности может резко уменьшить объем поиска, и поэтому динамическое программиро­вание может существенно сократить время вычисления. Пример такого сокращения мы увидим в алгоритме построения оптимальных деревьев бинарного поиска, в котором время вычисления уменьшается с величины, пропорцио­нальной 4ⁿ/n^3/2, если пользоваться очевидным исчерпывающим ал­горитмом, до О(n³) при подходе с позиций динамического про­граммирования; улучшение действительно существенное.

Построение оптимальных деревьев бинарного поиска

В качестве примера применения алгоритма динамического программирования рассмотрим Алгоритм построения таблицы Гильберта-Мура при поиске оптимальных деревьев бинарного поиска [http://www.neuroproject.ru/papers.htm].

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

Упорядоченным деревом называется ориентированное дерево, для которого определен порядок сыновей любой вершины дерева. Обычно мы изображаем упорядоченное дерево так, что корень размещается вверху, а сыновья каждой вершины расположены в соответствии с порядком слева направо. Для бинарного упорядоченного дерева поддерево, корень которого является левым сыном вершины v, называется левым поддеревом вершины v. Аналогично определяется правое поддерево вершины v. Пусть A = {a₁, a₂, …, a_n} – множество элементов, упорядоченных следующим образом: a₁<a₂<…<a_n. Бинарным деревом поиска для множества A является упорядоченное бинарное дерево, в котором каждая вершина v так помечена элементом l(v) множества A, что 1) для каждого u в левом поддереве вершины v, l(u)<l(v); 2) для каждого u в правом поддереве вершины v, l(u)>l(v); 3) для каждого элемента x множества A существует точно одна такая вершина v, что l(v)=x. Предположим A является подмножеством универсума S. Тогда пусть B = { b₀, b₁, … b_n } – такое множество, что 1)  

Расширенным деревом бинарного поиска для A называется дерево бинарного поиска для A с n+1 листьями, представляющими элементы множества B. Отметим, что в расширенном дереве бинарного поиска листья появляются слева направо в порядке b₀, b₁, …, b_n. В дальнейшем будем называть расширенное дерево бинарного поиска для множества A просто деревом бинарного поиска для A.

Пусть дано подмножество A универсума S и дерево T бинарного поиска для A. Множество S может быть множеством всех слов над английским алфавитом, а упорядочение может быть лексикографическим порядком. Предположим, что нам необходимо определить, принадлежит ли элемент

Случай  1.         Корень отсутствует (дерево T бинарного поиска пусто). Следовательно, x не принадлежит A, и поиск завершается безуспешно.

Случай              2. x равен элементу, соответствующему корню. Следовательно, поиск завершается успешно.

Случай 3.         x меньше элемента, соответствующего корню. Поиск продолжается ниже в левом поддереве корня.

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

Пусть p₁, p₂, …, p_n – частоты обращения к элементам a₁, a₂, …, a_n соответственно, и пусть q₀, q₁, …, q_n – частоты, с которыми поиск завершается в листьях T, представляющих b₀, b₁, …, b_n соответственно.

Таким образом, даны неотрицательные веса p_i и q_i. Необходимо построить дерево бинарного поиска минимальной стоимости для множества A = {a₁, a₂, …, a_n}, элементы которого упорядочены следующим образом: a₁<a₂<…<a_n. Нам часто будет удобно ссылаться на такое дерево как на оптимальное дерево бинарного поиска для весов q₀, p₁, q₁, p₂, …, q_n-1, p_n, q_n. Алгоритм построения оптимального дерева бинарного поиска, который мы сейчас рассмотрим, основан на следующем свойстве таких деревьев:

Пусть T – оптимальное дерево бинарного поиска для весов q₀, p₁, q₁, p₂, …, q_n-1, p_n, q_n. Если a_k – элемент, соответствующий корню дерева T, то левое поддерево корня дерева T является оптимальным деревом поиска для весов q₀, p₁, q₁, p₂, …, p_k-1, q_k-1, а правое поддерево корня дерева T - оптимальным деревом поиска для весов q_k-1, p_k, q_k, p_k+1, …, q_n-1, p_n, q_n. Пусть T_ij для

Предположим, что a_k – корень дерева T_ij(i<j). Тогда, как мы уже видели, левое поддерево с корнем a_k является деревом T_i,k-1, которое в свою очередь является оптимальным деревом бинарного поиска для множества { q_i, p_i+1, …, p_k-1, q_k-1 }, а правое поддерево с корнем a_k является деревом T_kj, которое в свою очередь является оптимальным деревом бинарного поиска для множества { q_k, p_k+1, …, p_j, q_j }. Так как глубина вершины в дереве T_ij на единицу больше ее глубины в дереве T_i,k-1 или T_kj, то отсюда следует, что

c_ij = c_i,k-1 + w_i,k-1 + c_kj + w_kj + p_k = w_ij + c_i,k-1 + c_kj.

Ясно, что мы можем найти корень r_ij дерева T_ij, определив величину

Вычислив r_ij с помощью данного алгоритма, мы можем легко построить дерево T_0n, используя следующую процедуру:

r_0n – корень дерева T_0n. Если r_0n=a_k, то a_k имеет в качестве левого сына r_0,k-1, а в качестве правого – r_kn.

Рассмотрим внутреннюю вершину a_m. Если r_ij=a_m, то a_m имеет в качестве левого сына r_m,k-1, а в качестве правого – r_mn.