Обмен ближайшими соседями и относительные расстояния: различия между версиями

Расстояние переноса поддеревьев между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальное количество поддеревьев, необходимое для преобразования <math>T_1 \;</math> в <math>T_2 \;</math> [5, 6, 7]. Иногда на практике бывает необходимо проводить различие между разными операциями переноса поддеревьев, поскольку они встречаются с разной частотой. В таком случае можно назначить каждой операции переноса поддерева стоимость, равную расстоянию (в числе пройденных вершин), на которое поддерево перенесено в текущем дереве. Расстояние переноса поддеревьев с линейной стоимостью, <math>D_{lcst}(T_1, T_2) \;</math>, между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальная стоимость, затрачиваемая на преобразование <math>T_1 \;</math> в <math>T_2 \;</math> при помощи операций переноса поддеревьев [1, 2].