algorithm - 如何证明这个贪心算法是最优的 : rod connection

Question

问题是:

给定一个数组，表示 table 上杆的长度。每次选择两根杆并将它们连接起来并获得一根新杆。这样做直到 table 上只有一根杆。连接的成本是两根杆的长度之和，例如，连接 2 和 3 将得到 5 根杆，成本为 5。什么是最低成本连接策略？

贪心:每次取最短的两根，把连接好的新杆放回 table 上。

例子:

[1,2,3,4,5] ，选择 1 和 2 花费 3 [3,3,4,5]，选择 3 和 3 花费 6 [4,5,6]，选择 4 和 5 花费9[6,9]，挑6，9花费15，所以总花费是33。

我们不能简单的说，总的连接次数是n-1，每次都取最小的两个，最后得到一个最小的cost。因为每一次挑都会改变 future ，像挑1+2和挑2+4都会导致下一步的两套不同的竿。

我如何证明这种贪婪会得到最小的成本？

Answer 1

证明类似于霍夫曼编码最优的证明。

每个策略对应一个二叉树。它包含其叶子中的所有初始杆，内部顶点对应于连接操作。

可以看出，对于一棵固定树，连接杆的成本是所有叶子 v 上的 a[v] * depth[v] 的总和，其中a[v] 是初始杆的长度，depth[v] 是叶的深度。之所以如此，是因为每根杆恰好参与连接 depth[v] 次。

我们需要证明存在一个最优策略，使得它的树有两个最短的杆作为 sibling 。

假设 T 是一棵最优树。让我们按深度对它的叶子进行排序(按非严格递减顺序)。如果最短的两根杆是前两片叶子，我们就完成了。否则，让我们继续将它们与它们的左兄弟(至少与它们一样长)交换，直到它们进入前两个位置。当我们交换 2 个叶子 u 和 v 时，成本变化是 -depth[u] * a[u] - depth[v] * a[v] + depth[u] * a[v] + depth[v] * a[u] = (depth[v] - depth[u]) * (a[u] - a[v] )。第一项是非正的(因为叶子是按高度排序的)，第二项是非负的(因为 a[u] >= a[v])。因此，成本变化为负或零。

因此，存在一棵最优树，其中两个最短的杆是 sibling 。这意味着存在一个最佳策略，即在我们做任何其他事情之前将这两根杆连接起来。