教甄◆資訊科技概論專業(電腦科)題庫下載題庫

上一題
14.請問下面哪些問題主要用動態程式規劃(Dynamic Programming)來解決？ 甲、最長共同子序列 乙、最小生成樹 丙、最佳矩陣連乘計算順序 丁、最短路徑問題
(A)甲、乙、丙
(B)甲、丙、丁
(C)乙、丙、丁
(D)甲、乙、丙、丁。

答案：登入後觀看
難度： 困難
1F
william 大三上 (2018/04/22)

最小生成樹->貪婪演算法

動態規劃的關鍵是，每次做選擇前，都會計算所有選項的效果，在此計算的n基礎上選擇能夠達到最佳的選項。因此，動態規劃每次的選擇都是最佳的。問題n是，這種策略在選項很多的情況下，將不堪負荷。例如，下棋時，如果使用動態n規劃策略，則需要先計算每步棋可能走法的影響，然後比較，選取最佳走法。但n5-2n每步棋的走法實在太多，更不用說下一盤棋有不計其數的步驟，這簡直是不可能n的任務。即使是超級電腦也無法勝任。顯然此時，我們需要新的演算法。

在選擇時不做任何計算，而是根據當時的情況，n做出我們認為最好的選擇->貪婪演算法

參考資料：http://epaper.gotop.com.tw/pdf/ACL031300.pdf

2F
盧健瑋 高三下 (2018/04/24)
動態規劃技巧有三個主要部份
1遞迴關係（recurrence relation）
2列表式運算（tabularncomputation）
3路徑迴溯（traceback）

什麼樣的問題適合用動態規劃技巧來解呢
1符合最佳化準則，亦即若將最佳答案解構，解構後的子答案仍為對應子問題的最佳解

2解題過程中，有許多重複的子問題 


14.請問下面哪些問題主要用動態程式規劃(Dynamic Programming..-阿摩線上測驗