|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eduard Vatutin 2:5035/43.25 30 Oct 2002 13:12:58
To : Serge Nozhenko
Subject : Re: Обработка деревьев
--------------------------------------------------------------------------------
30.10.02 в 02:02, Serge Nozhenko ъ-ДДДНН> Eduard Vatutin:
EV>> Возникла необходимость реализовать сабж. Деревья произвольной
EV>> арности, вершины дерева могут быть только 2 типов, листья в общем
EV>> случае N типов. Порядок следования ветвей от каждой вершины *не
EV>> важен*. Hеобходимо проверить, является ли одно дерево поддеревом
EV>> другого.
SN> Представить деревья каким-нибудь одномерным способом, сортируя
SN> вершины с общим предком в определенном порядке. Далее все сводится к
SN> поиску подстроки в строке, для которого есть готовые алгоритмы на
SN> любой вкус.
Такой вариант у меня был. Только я до конца не решил, когда сортировать: то ли
при построении дерева, то ли перед поиском поддерева. Что одно, что другое
достаточно труднореализуемо (в смысле ресурсоемко ;), а операций таких надо
будет проводить достаточно много (к примеру, среди 50 деревьев найти такую пару,
в которой одно дерево является поддеревом другого, модифицировать набор деревьев
(их станет на одно меньше) и опять то же самое, пока будут находиться
поддеревья).
Может есть еще какие задумки?
--- _/Пока, Serge/_
* Origin: Если долго мучаться - чего-нибудь да получится (2:5035/43.25)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
