Hi

Каким образом можно получить всевозможные структуры поддеревьев для данного дерева. Исходное дерево очень большое (от 1000 узлов).

Спасибо.

Здравствуйте, csharper, Вы писали:

C>Каким образом можно получить всевозможные структуры поддеревьев для данного дерева. Исходное дерево очень большое (от 1000 узлов).

Можно предположить, что общее количество поддеревьев — это что-то экспоненциальное от 1000.
Так что перебор — хотя теоретически и можно придумать структуры и алгоритмы для итерирования — практически неприменим.

А зачем тебе это? Может быть, проще решить надзадачу?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, csharper, Вы писали:

C>>Каким образом можно получить всевозможные структуры поддеревьев для данного дерева. Исходное дерево очень большое (от 1000 узлов).

К>Можно предположить, что общее количество поддеревьев — это что-то экспоненциальное от 1000.
К>Так что перебор — хотя теоретически и можно придумать структуры и алгоритмы для итерирования — практически неприменим.

К>А зачем тебе это? Может быть, проще решить надзадачу?

Вобще, нужно найти форму поддерева, повторяющуюся в дереве наибольшее количество раз.

Здравствуйте, csharper, Вы писали:

C>Вобще, нужно найти форму поддерева, повторяющуюся в дереве наибольшее количество раз.

Как-то не совсем понятно... Форма поддерева, повторяющаяся наибольшее число раз — это вырожденное дерево из одной вершины
Так что надо бы сформулировать дополнительные критерии. Что лучше: поддерево из 5 вершин, повторенное 10 раз, или поддерево из 10 вершин, повторенное 5 раз?

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, csharper, Вы писали:

C>>Вобще, нужно найти форму поддерева, повторяющуюся в дереве наибольшее количество раз.

C>Как-то не совсем понятно... Форма поддерева, повторяющаяся наибольшее число раз — это вырожденное дерево из одной вершины

Не совсем. Возьмем дерево из n+1 вершины, где у корневой вершины будет n непосредственых дочерних вершин.
Тогда поддеревьев из одной вершины — n+1.
А одинаковых по форме поддеревьев из трех вершин n*(n-1)/2.

Здравствуйте, csharper, Вы писали:

C>Вобще, нужно найти форму поддерева, повторяющуюся в дереве наибольшее количество раз.

1) Узлы между собой как-то различаются?
2) Поддерево можно получать, отбрасывая дочерние узлы — или только отбрасывая родительские?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, csharper, Вы писали:

C>>Вобще, нужно найти форму поддерева, повторяющуюся в дереве наибольшее количество раз.

К>1) Узлы между собой как-то различаются?
К>2) Поддерево можно получать, отбрасывая дочерние узлы — или только отбрасывая родительские?

Узлы никак не различаются. Вобще, хорошо было бы найти все формы поддеревьев, повторяющихся более одного раза. И уже по данным узлов конкретного поддерева я могу решить какое лучше (каждый узел имеет набор определенных метаданных). Поддерево тоже может быть любой формы.

Я думал как вариант перевести дерево в скобочную запись, т.е. в специального вида "строку" и применить алгоритм нахождения наибольшей повторяющейся подстроки с помощью суффиксных деревьев, но не уверен что это будет работать, и сколько оперативной памяти потребуется на дерево с примерно 1 тыс. узлов. Разбирать нужно очень быстро. Наверное, не любая подстрока скобочного представления будет непрерывным поддеревом. Или я неправ?

Спасибо за любые подсказки.

Здравствуйте, csharper, Вы писали:

C>Hi

C>Каким образом можно получить всевозможные структуры поддеревьев для данного дерева. Исходное дерево очень большое (от 1000 узлов).

C>Спасибо.

кажется есть такая вещь — "случайные двоичные деревья". там вероятностный анализ используется. что-то мне кажется, тебе это надо почитать.