Есть два дерева, каждая из вершин может быть некоторого типа и имеет имя. При сравнении две вершины с одинаковыми типами и одинаковыми именами считаются равными. Осуществляю сравнение деревьев обычным сравнением вершин. Встала задача не просто проверить на равенство, а получить некоторое число (от 0.0 до 1.0) которое отражает степень схожести деревьев. Причем требуется учитывать не только удаление\добавление вершин, но их перемещение на более нижний\верхний уровень дерева, т.е. смену родителя некоторого поддерева. Деревья довольно большие - до нескольких тысяч узлов в глубину\ширину.
Ума не приложу как быть. Может есть специальные алгоритмы? |