Аннотация:
В статье предложен новый точный квадратичный по сложности алгоритм, который решает задачу кратчайшего преобразования (“выравнивания”) одного нагруженного дерева в другое с учетом произвольных цен операций над деревьями. Предложен набор из трех операций: добавление вершин-делеций к ребру или корню дерева и сдвиг поддерева с делециями.
Ключевые слова:
дискретная оптимизация, кратчайшее преобразование дерева, операции над деревом, цена операции, точный алгоритм, квадратичной сложности алгоритм, выравнивание деревьев.
УДК:519.178
Статья представлена к публикации:А. Л. Семёнов Поступило: 24.01.2024 После доработки: 01.08.2024 Принято к публикации: 01.08.2024
