计算文件传输的最小树

如果你想象一个给定节点的第二个子节点和随后的子节点实际上是第一个子节点的子节点链,那么答案更容易得到,例如。

     O
    /|\
   / | \
  /  |  \
 O   O   O

实际上表示为

     O
    /
   /
  /
 O===O===O

=== )在这个新的表示中,除了根节点之外,每个节点最多可以有两个子节点:一个是其实际的第一个子节点,另一个是其右侧的第一个同级节点。(根目录不能有兄弟目录,因此它最多只能有一个子目录。)例如,OP的post中的第二棵树,

         O
        / \
       /   \
      /     \
     O       O
    / \
   /   \
  /     \
 O       O

可以在“同级边缘”表示中表示为

         O
        /
       /
      /
     O=======O
    /
   /
  /
 O=======O

诀窍是同时传输到节点的两个子节点。这使我们可以直观地排列树,以便同时传输到的所有节点都显示在相同的垂直位置。我们现在得到:

0            O
            /
           /
          /
1        O
        / \\
       /   \\
      /     \\
2    O       O
      \\
       \\
        \\
3        O

最大限度 t ,我们需要在上面的布局中有一棵树( t型 m(t) . 为了 t型 >1,我们可以通过获取 t-1 米(吨) 给我们:

t      Total        Rightmost
       nodes        nodes

0      1            1
1      1+1*1=2      1 (only multiply by 1 because the root can't have siblings)
2      2+1*2=4      2
3      4+2*2=8      4
4      8+4*2=16     8

m(t) = 2^(t-1) ,这是有意义的,因为这个最优树只是一个完整的二叉树,顶部有一个小“茎”作为根节点。

n 是2的幂,是 n = 2^t 节点需要 t+1 时间,如果不是的话,它需要比下一个更小的2次方多1个时间单位。所以需要发送到 n个 roundup(log2(n)) + 1 .

要实现实际的通信树,现在可以将“同级”边转换回左节点的父节点和右节点之间的边。这表明,对于2次方节点计数,离开根节点的边数将与所需的总时间相同( ). 离开任何节点的第一个子节点的边数始终比其父节点少一条,离开每个第二子节点和后续子节点的边数始终比其左同级节点少一条。

我相信最佳算法(在史蒂夫指出的不同时发送和接收的约束下)应该是从 log2(n) 根下的节点。然后,对于每个节点,它应该有其父节点的子节点数量减去其直接兄弟节点之间从左到右的顺序(即不查看其父节点兄弟节点的子节点)。

关于Steve Jessops的评论:为什么不使用BitTorrent之类的工具呢?(即,一个经过良好测试、部署良好的基础设施,构建在一个已知的良好框架上,而这几乎不需要您的工作?)

编辑: 用户的回答是好的; log2(n) 可能是最佳的客户数量; .

对数2(n) 在任何给定时间接收的最大客户端数。如果你的烟斗是 n 编辑:

想象一只兔子生下另一只兔子。这两只又生了两只兔子,那四只又生了四只兔子。。。现在,边缘代表亲子关系的兔树有点奇特。根节点的阶数D=log2(n)。根的后代(其中D个)的度数从0到D-1。事实上,每一个X阶节点都有X个从0到X阶的子节点。

你可能会说这是一个“分形树”,完美的“不平衡”。

所有这些都假设每个节点的上传速度等于每个节点的下载速度。在现实世界中,情况并非如此,因此您实际上需要重新检查(再次)您的初始问题:-)