 |
|
|
 
|
|
оценка густоты дерева, не для садовников 
| DoberZ |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 20 Регистрация: 25.6.2007 Репутация: нет Всего: нет |
есть несколько деревьев. хранятся в реляционной таблице, если это важно. предложите формальный алгоритм, чтобы оценить одим показателем (числом) "густоту" каждого дерева... то есть, скажем, если у него всего одна длинная ветка, на которой последовательно расположены все узлы - то "густота"=0, а если все узлы, кроме корневого, не имеют потомков - то густота=100, например
|
|||
|
||||
Загрузка ...
| esperant0 |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
если у него всего одна длинная ветка, на которой последовательно расположены все узлы - то "густота"=0, а если все узлы, кроме корневого, не имеют потомков - то густота=100, инча густота = 50.
-------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
| DoberZ |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 20 Регистрация: 25.6.2007 Репутация: нет Всего: нет |
собственно, придумал... стоило только сформулировать - и решение назрело. густота=Б/N , где Б-число бездетных узлом, N-число узлов
|
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
хм... ну можно, например, рассмотреть соотношение глубины (можно средней) дерева и количества узов
при одной длинной ветке они будут практически одинаковы при равномерно раскиданных по дереву узлах - глубина будет чем-то вроде логарифма от количества узлов -------------------- qqq |
|||
|
||||
| _Y_ |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
Я, по простоте душевной, просто посчитал бы среднее число потомков у предка, учитывая при этом только узлы имеющие хоть одного потомка.
-------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0697 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |