作者DJWS (...)
站內Prob_Solve
標題Re: [問題] 如何解 池塘邊的木頭 問題
時間Fri Nov 7 17:55:46 2008
※ 引述《chrisdar (克里斯)》之銘言:
: 我想問還有沒有其他的演算法或想法能支援這個問題,如果化成動態規畫呢?
: 我對於動態規畫的模型僅只於背包問題 XD 謝謝各位。
先將所有木材進行排序,依照木材的左端位置。
然後設定狀態空間為: (湖的寬度, 木材數目, 有放進湖裡的木材數目)。
其中第二項的木材樹目,是指所有木材排序後,僅使用第一根到第N根的木材。
有版友說可以用A*,其實還不用這麼麻煩。
用狀態空間樹的話,
只要用記憶體把重複出現的狀態記錄下來就可以了。
記錄方式誠如上一段所說那樣。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.83.198
※ 編輯: DJWS 來自: 220.137.83.198 (11/07 18:04)
推 chrisdar:我先去搜尋相關資料 謝謝 關鍵字應該是 狀態空間樹 吧 11/07 18:15
→ DJWS:恩...我講的是動態規劃法 XD 11/07 18:24
→ DJWS:不過我沒有實際寫出來 所以不敢保證我的想法對不對 11/07 18:25
推 Fenikso:排序後不一定能找到最佳解 11/07 18:32