信息交换

现有一完全的P2P共享协议，每次两个节点通讯后都能获取对方已经获取的全部信息，现在使得系统中每个节点都知道所有节点的文件信息，共17个节点，假设只能通过多次两个对等节点之间通讯的方式，则最少需要几次通讯

分析：

子问题1：每个节点信息不同，使其中一个节点获得全部信息，最少要几次通讯
每个节点相当于图中的点，一次通信相当于图的边，要获取全部信息需要每个点都参与进来，即构成连通图，n个节点的连通图边数大于等于n-1,最少的情况是将这些点构成生成树，需要n-1次。直观的通信方式是顺序通讯

子问题2：一堆不完全的节点，并且节点两两不能互补，先有1个完全节点，要使所有节点获得全部信息，最少要几次通讯
因为每个不完全的节点至少需要通信一次来获取信息，两两不互补使得节点间相互通信一次不能达到完全，选择和完全节点通信是最优策略。有n个不完全节点那么最少需要n次。

案例
设f(n)为n个节点全部变成完全节点所需的最少通信次数
n = 1时完全不需要通信，f(1) = 0
n = 2时,通信一次，f(2) = 1
n = 3时，两两通信一次，平面图形状是三角形，f(3) = 3
n = 4时，直接应用子问题1和2，得出结论是5，然而并不是最优，最优是4次，先两两分组，2次组内通信，2次组间通信，平面图形状是矩形，f(4) = 4

只靠子问题1和2并不是最优，需要考虑分组

分组策略：
n<4时，分组无意义，只有数量大于等于4时才考虑分组

1. 先将n个节点分成k组,每组至少有2个节点
2. 每组内通讯获取组内完全节点
   由子问题1，每个组n_k个节点需要n_k-1次通讯，能产出两个完全节点
3. 组间完全节点通信，一共k组，每组2个，需要最少次数即为2f(k)
4. 传播完全节点，由子问题2，每个组现有n_k-2个不完全节点，每组最少需要n_k-2次

将这些步骤汇总后即为
$$f(n|n>=4) = \sum_{i=1}^k (n_k-1) + 2f(k) + \sum_{i=1}^k (n_k-2)$$
化简后为
$$f(n|n>=4) = 2n + 2f(k) - 3k$$
其中对于一个固定的k值，$g(k) = 2f(k) - 3k$可视为一个常量，即$f(n|n>=4)=2n + m$
当k = 1, f(1) = 0, g(k) = -3
当k = 2, f(2) = 1, g(k) = -4
当k = 3, f(3) = 3, g(k) = -3
当k = 4, f(4) = 4, g(k) = -4
当k >= 4带入得$g(k) = 2f(k) - 3k = k + 2m$为k的单调递增
综上即分为2组或4组时，可以取得最优

即f(n|n >= 4) = 2n - 4, f(17) = 30