如何實現狀態空間樹？

Question

我試圖從MIT OCW解決像揹包一樣的問題。 其問題集5.

我需要使用分支定界算法來尋找最佳狀態。 所以我需要實現一個狀態空間樹。 我理解這個算法的思想，但是我覺得實現起來並不那麼容易。

如果我發現預算不夠的節點，我應該停下來。 我應該爲每個樹節點添加一個屬性嗎？

當我添加一個節點時，我應該從具有最大上限的節點開始。 我怎樣才能找到這樣一個節點？在添加每個節點之前，是否需要遍歷所有節點？或者我可以保存一些變種來幫助嗎？

你有什麼想法嗎？你能用python實現嗎？

Answer 1

我希望我理解正確的問題，如果沒有請告訴我:)
（對不起，從「國家」的兩種不同的含義所產生的混亂）

當然你可以在添加屬性節點（它是狀態的一部分！），因爲它是非常少量的數據。請注意，雖然它不是強制性的，但它隱含在州內其他地方（鑑於你已經選擇的州，你可以計算它）。就我個人而言，我會添加該屬性，因爲多次計算沒有意義。

關於第二個問題：IIRC，當你添加節點時，你不必遍歷所有的樹，而只需要邊緣（也就是沒有後代的節點集合 - 不要被混淆）樹的最深層次）。 既然你正在尋找一個上限，（既然你只使用正面的費用），還有當你正在尋找具有最高值的節點三種情況：

• 的最後一步，你附加到具有最高值的節點，因此您剛剛添加的節點現在具有最高值
• 最後一步添加您超出了預算，因此您必須排除該選項。嘗試添加另一個狀態
• 沒有更多的狀態嘗試添加以構建新節點。這個分支不能走得更遠。看看其他節點中最高價值的邊緣