逆霍夫曼算法？
Reverse Huffman's algorithm?
我有一个类似于哈夫曼编码的问题，我不确定它究竟是如何解决的，或者它是否是一个反向霍夫曼编码。但是肯定可以用贪心的方法解决。
考虑一组长度，每个长度与一个概率相关联。即
X={a1=(100,1/4),a2=(500,1/4),a3=(200,1/2)}
显然，所有概率之和=1。
从一个起点开始一个接一个地排列在一条线上。
例如：{a2,a1,a3}从头到尾的顺序。
定义元素的成本a_i为其从起始行到该元素结尾的总长度乘以它的概率。
所以从之前的安排来看：
cost(a2) = (500)*(1/4)
cost(a1) = (500+100)*(1/4)
cost(a3) = (500+100+200)*(1/2)
将总成本定义为所有成本的总和。例如cost(X) = cost(a2) + cost(a1) + cost(a3)。给出一个算法，找到一个最小化 cost(X)
的排列
我试过形成一些替代的霍夫曼树，但它不起作用。
按概率排序会失败（考虑 X={(100,0.4),(300,0.6)}）。
按长度排序也会失败（考虑 X={(100,0.1),(300,0.9)}）。
如果有人可以帮助或暗示最优解算法，那就太好了。
考虑如果交换两个相邻元素会发生什么。两个元素前后的计算是一样的，所以只看两个元素。
单独考虑两个元素，成本为 P1L1 + P2(L1 + L2) 和 P2L2 + P1(L1 + L2)。如果你减去这个并简化，如果我有正确的代数，你想在 L1/P1 < L2/P2 时将 1 交换到第一个。检查 - 这至少在 L1 = 0 时得到正确答案。
所以我认为您想将元素排序为 Li/Pi 的递增顺序，因为如果不是这种情况，您可以通过交换相邻元素来改进答案。
我有一个类似于哈夫曼编码的问题，我不确定它究竟是如何解决的，或者它是否是一个反向霍夫曼编码。但是肯定可以用贪心的方法解决。
考虑一组长度，每个长度与一个概率相关联。即
X={a1=(100,1/4),a2=(500,1/4),a3=(200,1/2)}
显然，所有概率之和=1。
从一个起点开始一个接一个地排列在一条线上。
例如：{a2,a1,a3}从头到尾的顺序。
定义元素的成本a_i为其从起始行到该元素结尾的总长度乘以它的概率。
所以从之前的安排来看：
cost(a2) = (500)*(1/4)
cost(a1) = (500+100)*(1/4)
cost(a3) = (500+100+200)*(1/2)
将总成本定义为所有成本的总和。例如cost(X) = cost(a2) + cost(a1) + cost(a3)。给出一个算法，找到一个最小化 cost(X)
我试过形成一些替代的霍夫曼树，但它不起作用。
按概率排序会失败（考虑 X={(100,0.4),(300,0.6)}）。
按长度排序也会失败（考虑 X={(100,0.1),(300,0.9)}）。
如果有人可以帮助或暗示最优解算法，那就太好了。
考虑如果交换两个相邻元素会发生什么。两个元素前后的计算是一样的，所以只看两个元素。
单独考虑两个元素，成本为 P1L1 + P2(L1 + L2) 和 P2L2 + P1(L1 + L2)。如果你减去这个并简化，如果我有正确的代数，你想在 L1/P1 < L2/P2 时将 1 交换到第一个。检查 - 这至少在 L1 = 0 时得到正确答案。
所以我认为您想将元素排序为 Li/Pi 的递增顺序，因为如果不是这种情况，您可以通过交换相邻元素来改进答案。