如何证明这种贪婪算法为最优:杆连接
以下是问题所在：
给定一个数组表示表上杆的长度。每次选两根杆，把它们连接起来，得到一根新的棒子。这样做，直到只有一根棒在桌子上。连接的成本是两杆长度之和，例如，连接2与3将得到5杆和成本5。最小成本连接策略是什么？
贪婪:每次挑出最短的两根，把连接好的新棒放回桌子上。
示例：
1,2,3,4,5，pick 1和2花费3,3,4,5，pick 3和3花费6，4,5,6，pick 4和5花费9，6,9，pick 6和9花费15，因此总成本为33。
我们不能简单地说，连接的总次数是相同的n-1，所以每次选择最小的两次都会给出最后的最小成本。因为每一次采摘都会改变未来，比如选择1+2和2+4会在下一步产生两组不同的棒。
我怎样才能证明这个贪婪的人能得到最小的成本？
回答 1
Stack Overflow用户
发布于 2017-05-01 08:28:33
这个证明类似于证明Huffman'c码是最优的。
每种策略都有对应的二叉树。它在叶子中包含所有初始杆，内部顶点对应于连接操作。
可以看出，固定树的连杆连接成本是a[v] * depth[v]对所有叶子的v之和，其中a[v]是初始杆的长度，depth[v]是叶的深度。情况是这样的，因为每根杆子都参与一个连接，正好是depth[v]时间。
我们需要证明存在一个最优策略，使得它的树有两个最短的杆作为兄弟。
假设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])。因此，成本变化是负的或零的。
因此，存在一个最优树，其中两个最短的杆是兄弟姐妹。这意味着，在我们做任何其他事情之前，我们都有一个连接这两根棒的最佳策略。
https://stackoverflow.com/questions/43715207
复制相似问题
腾讯云开发者
