问一个关于树的剪枝算法。

zhaojys
Tony 2011-01-01 字数 414

最近遇到一个关于树的剪枝问题。

具体是这样的,现有一颗全网的报文分发树,节点很多。

每个节点会标记自己是某一个或是多个组播地址的接受者。

如果根节点收到一个组播地址的报文,实际不需要想全网的所有节点发送,因为有的节点

可能不是这个地址的接受者。

如果全发,就是全网广播了。

现在就是根据这个组播地址,对这个树进行剪枝,生成一个子树。

这样树根收到这个地址的组播报文,只需要向这个子树发送即可。

谁有什么好的方法,共享一下,谢谢!!

Algorithm 算法
10 个回复
wxstorm
企鹅 2011-01-01

你需要把问题抽象成模型啊。。。这样不是这个领域的谁看的懂啊。。

【 在 zhaojys (Tony) 的大作中提到: 】

: 最近遇到一个关于树的剪枝问题。

: 具体是这样的,现有一颗全网的报文分发树,节点很多。

: 每个节点会标记自己是某一个或是多个组播地址的接受者。

: ...................

weird
打倒户部 2011-01-01

树根接受的地址最多,

父节点包含各子节点的接受地址吗?

【 在 zhaojys (Tony) 的大作中提到: 】

: 最近遇到一个关于树的剪枝问题。

: 具体是这样的,现有一颗全网的报文分发树,节点很多。

: 每个节点会标记自己是某一个或是多个组播地址的接受者。

: ...................

JetApple
千里一醉 2011-01-01

每个子节点向根节点通知一次自己感兴趣的组播地址,然后由根节点处理收集到的所有信息,把感兴趣的组播地址相同的节点划分到一个小组里,小组内部按照某种方法形成子树,把子树的根节点返回给全网根节点,由后者维护一个“组播地址-子树根节点”的键值对,以后负责分发相应的报文。

好吧,我承认这个是最土鳖的方法。。。

【 在 zhaojys (Tony) 的大作中提到: 】

: 最近遇到一个关于树的剪枝问题。

: 具体是这样的,现有一颗全网的报文分发树,节点很多。

: 每个节点会标记自己是某一个或是多个组播地址的接受者。

: ...................

zhaojys
Tony 2011-01-02

每个节点都是独立标示,父节点也不一定有子节点的地址。

但是如果父节点没有这个地址的标示,子节点有,在剪枝的话,需要保留这个父节点。

否则父节点剪掉了,报文是无法发送到这个子节点的。

【 在 weird (打倒户部) 的大作中提到: 】

: 树根接受的地址最多,

: 父节点包含各子节点的接受地址吗?

weird
打倒户部 2011-01-02

虽然可以用,不过这不是剪枝吧

【 在 JetApple (GTX460预备党员) 的大作中提到: 】

: 每个子节点向根节点通知一次自己感兴趣的组播地址,然后由根节点处理收集到的所有信息,把感兴趣的组播地址相同的节点划分到一个小组里,小组内部按照某种方法形成子树,把子树的根节点返回给全网根节点,由后者维护一个“组播地址-子树根节点”的键值对,以后负责分发�

: 好吧,我承认这个是最土鳖的方法。。。

weird
打倒户部 2011-01-02

要计算某个组播地址的转发生成树的话

后序遍历,把没有子节点,自身也不接受这个组播的节点剪掉

【 在 zhaojys (Tony) 的大作中提到: 】

: 每个节点都是独立标示,父节点也不一定有子节点的地址。

: 但是如果父节点没有这个地址的标示,子节点有,在剪枝的话,需要保留这个父节点。

: 否则父节点剪掉了,报文是无法发送到这个子节点的。

: ...................

JetApple
千里一醉 2011-01-02

老实说我没看出来lz的问题为啥要剪枝啊。。。

【 在 weird (打倒户部) 的大作中提到: 】

: 虽然可以用,不过这不是剪枝吧

weird
打倒户部 2011-01-02

感觉原来的报文分发树是和网络拓扑对应的,报文只能按照树的结构转发吧

【 在 JetApple (GTX460预备党员) 的大作中提到: 】

: 老实说我没看出来lz的问题为啥要剪枝啊。。。

zhaojys
Tony 2011-01-02

是的,那棵树就是全网拓扑,报文只能按照树分发。

所以当一个节点不是某个组播地址的接受者时,如果它下面的子节点是这个地址的接受

者,剪枝的时候这个节点要保留,否则报文无法到达子节点了。

【 在 weird (打倒户部) 的大作中提到: 】

: 感觉原来的报文分发树是和网络拓扑对应的,报文只能按照树的结构转发吧

shimo
shimo 2011-01-03

扫描一遍全网分析树,生成根节点维护一个<地址,接受者1,接受者2...>的倒排。

根节点有分发时,直接发到地址的接受者列表里面;新出现的地址则更新倒排。

【 在 zhaojys (Tony) 的大作中提到: 】

: 是的,那棵树就是全网拓扑,报文只能按照树分发。

: 所以当一个节点不是某个组播地址的接受者时,如果它下面的子节点是这个地址的接受

: 者,剪枝的时候这个节点要保留,否则报文无法到达子节点了。