反向霍夫曼算法？

Question

我有一個類似霍夫曼編碼的問題，我不確定它是如何解決的，或者它是否是霍夫曼逆編碼。但它肯定可以用貪婪的方法解決。

---

考慮一組長度，每個長度都與一個概率相關聯。即

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）}）。

如果任何人都可以幫助或提示最佳解決方案算法，那就太好了。

Answer 1

考慮如果交換兩個相鄰元素會發生什麼情況。兩個元素之前和之後的計算是相同的，所以它只取決於這兩個元素。

將兩個元素隔離開來，成本爲P1L1 + P2（L1 + L2）和P2L2 + P1（L1 + L2）。如果你減去這個並簡化，如果我有代數權利，你想交換1到第一個L1/P1 < L2/P2。檢查 - 當L1 = 0時，至少得到正確的答案。

所以我認爲你想按李/ Pi的升序排列元素，因爲如果不是這種情況，你可以通過交換相鄰元素。