動態編程幫助：二叉樹成本邊緣

給定一個具有n個葉子和一組C顏色的二叉樹。樹中的每個葉節點都從集合C獲得唯一的顏色。因此，沒有葉節點具有相同的顏色。樹的內部節點是無色的。 C組中的每一對顏色都有相關的成本。因此，如果樹邊緣連接顏色A和B的兩個節點，則邊緣成本是該對（A，B）的成本。我們的目標是爲樹的內部節點提供顏色，從而最小化樹的總邊緣成本。動態編程幫助：二叉樹成本邊緣

我已經在這個問題上工作了好幾個小時了，而且還沒有真正想出一個可行的解決方案。任何提示將不勝感激。

來源

2012-02-17 Catie

我可以問哪裏取自這個問題的一個列表？它來自任何活躍的算法競爭嗎？ – 2012-02-17 09:34:47

不，不適用於任何競爭。 – Catie 2012-02-17 09:37:15

好吧，那麼我很樂意嘗試幫助你。你能否對任務的限制提出任何意見？你有多少種顏色可供選擇？樹中有多少個節點。 – 2012-02-17 09:39:30

我要解決僞問題，因爲我試着寫的解釋和它即使對我來說也完全不可理解。希望代碼能夠做到這一點。我的解決方案的複雜性不是很好 - 記憶O（C^2 * N）中的醉人時間。

我需要對數組我會用動態的方法來你的任務：
dp [N][C][C] - >dp[i][j][k]您可以在節點i根的樹得到的，如果你在顏色j及其繪製它的最高價格家長在顏色的彩色k
maxPrice[N][C] - >maxPrice[i][j]你可以從根植於節點i樹得到，如果它的父顏色j
color[leaf]有色的最高價格 - >葉的顏色leaf
price[C][C] - >price[i][j]如果你有顏色i對相鄰節點和j chosenColor[N][C]你得到的價格 - >chosenColor[i][j]應該選擇節點i顏色來獲得maxPrice[i][j]

讓我們假設該節點使用topological sorting有序的，即我們將處理第一片葉子。拓撲排序在樹上很容易實現。讓分揀給內部節點inner_nodes

for leaf in leaves: 
    for i in 0..MAX_C, j in 0..MAX_C 
     dp[leaf][i][j] = (i != color[leaf]) ? 0 : price[i][j] 
    for i in 0..MAX_C, 
     maxPrice[leaf][i] = price[color[leaf]][i] 
     chosenColor[leaf][i] = color[leaf] 
for node in inner_nodes 
    for i in 0..MAX_C, j in 0..MAX_C 
     dp[node][i][j] = (i != root) ? price[i][j] : 0 
     for descendant in node.descendants 
      dp[node][i][j] += maxPrice[descendant][i] 
    for i in 0...MAX_C 
     for j in 0...MAX_C 
     if maxPrice[node][i] < dp[node][j][i] 
      maxPrice[node][i] = dp[node][j][i] 
      chosenColor[node][i] = j 

for node in inner_nodes (reversed) 
    color[node] = (node == root) ? chosenColor[node][0] : chosenColor[node][color[parent[node]]

來源

2012-02-17 10:19:12

以此爲起點，您可以使用一個貪婪的解決方案，它爲您提供了總成本的上限：

while the root is not colored 
    pick an uncolored node having colored descendants only 
     choose the color that minimizes the total cost to its descendants

來源

2012-02-17 10:12:48

動態編程幫助：二叉樹成本邊緣

回答

相關問題