4.5. Локальные операции на деревьях

Основная цель приближения к S заключается в том, чтобы найти такие деревья , которые обращают в минимум. Однако всегда существует такое дерево что . Поэтому целью является отыскание семейства деревьев таких, что дает минимум для каждого . Единственный существующий метод отыскания оптимального семейства состоит в полном переборе всех возможных деревьев на В и вычислении для каждого дерева соответствующего значения . Однако этот метод практически неосуществим из-за того, что число деревьев очень быстро растет с ростом . Таким образом, мы приходим к понятию «локально оптимального» семейства. Процедура начинается с семейства над которым производятся некоторые итеративные преобразования, которые составляют так называемое множество «локальных операций» L. Локальной операцией называется любая операция, которая изменяет дерево и в результате которой получается другое дерево . Семейство деревьев называется -оптимальным, если для каждого , где обозначает число узлов в Это означает, что семейство не может быть улучшено с помощью операций L. При оперировании на деревьях семейство итеративно преобразуется в -оптимальное семейство. Семейство деревьев назовем локально оптимальным на множестве локальных операций L, если это семейство

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

Можно показать, что если коэффициенты сходства узлов приближения, вычисленных по формуле (4.8), не удовлетворяют неравенству для любых , то можно найти дерево с количеством узлов, меньших на единицу, и которое приближает S так же хорошо, т. е. оба дерева приводят к одному и тому же значению . Это означает, что поиск локально оптимальных Деревьев можно ограничить классом деревьев сходства. Аргументацию этого предложения читатель найдет в работе Хартигена [162, параграф 5].

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

После того как локальная операция выполнена, основная корректировка заключается в изменении некоторых значений расширенных матриц W, S. Все другие величины, связанные с деревом, должны быть изменены одинаковым образом. Процедура заключается в том, чтобы оценить данную серию операций на дереве и выполнить ту, которая приводит к наибольшему уменьшению . Результат локальной операции L, расстояние сравнивается с или где оптимальное дерево с узлами, S — соответствующая матрица сходства. Следующей вычислительной задачей является определение матрицы сходства S с точной структурой дерева , для которой минимально.

Три локальные операции, выполняемые на деревьях:

1) операция разветвления. Операция разветвления из а в b обозначается это операция, которая соединяет некоторый узел а из семейства и некоторый другой узел дерева b, причем . Функция

изменяется на функцию так, что для Операция разветвления не меняет числа узлов дерева;

2) операция исключения исключает узел из дерева и переводит семейство в . Эта операция определена для любых узлов за исключением корня и начальных узлов. В терминах отображения это означает для для

3) операция включения включает новый узел а в дерево между а и . Если а — корень, то а — новый корень. В терминах Т имеем: .

Операция включения и исключения изменяет число узлов дерева .

Иллюстрации этих операций читатель найдет в статье Хартигена. Он также дает примеры применения этой процедуры для отыскания локально оптимального дерева и показывает, как - критерий может быть использован для определения приемлемого размера дерева. Там же рассматриваются другие определения точной структуры дерева и другие, отличные от деревьев, структуры сходства.