|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 17 Apr 2002 15:15:48
To : Alex Astafiev
Subject : Trees Comparison
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Alex! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Alex Astafiev и Elvira Svirshchova! Что за "Trees Comparison", а
где же яйца?!
AA>>> они различаются только немножко, причем где-то в глубине.
AA>>> глубина иерархии может достигать 200-300 и впринципе,
AA>>> неограничена. количество узлов во всей иерархии может достигать
AA>>> 200-300 тыс элементов. интересен оптимальный алгоритм поиска
AA>>> различий.
ES>>
ES>> Вопрос по постановке задачи: Следует ли считать изоморфные
ES>> деревья одинаковыми? Похоже, что Ваш алгоритм воспримет их как
ES>> различные.
AA> нет не следует, любое отличие должно восприниматься как отличие.
AA> хе-хе, что сложная задача?
Что нам - пермякам?! :)
Возможно, когда письмо дойдет до народа, тема будет практически закрыта (у меня
временно траблы с момедом), но на всякий случай кидаю идею на сравнение
изоморфных графов. С последующим преобразованием она может чему и поможет:
При первом проходе, идя в глубину, при каждом возвращении записываем для каждой
вершины количество ее потомков (и прямых и косвенных). В определенном порядке
записываем эти числа для одного и для другого дерева. Если одну из полученных
последовательностей можно представить переставлением чисел другой - деревья
одинаковы.
Для данной задачи (когда изоморфизм считать отличием), для каждого узла (при
первом проходе) записывать код, описывающий потомков (например, по рекурсивному
принципу "сначала правый потомок, потом левый"). При втором проходе сравнивать
эти описания, из чего делать вывод об отличиях.
Good bye, mister Astafiev _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Все в Голом Деде пишут послания, Winamp поставлен на паузу... (с)~Сплин
--- А у твоего ГолДеда стоит... фильтрация мессаг???
* Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
