24.下列何種演算法屬於動態規劃法(DynamicProgramming)? ..-阿摩線上測驗
檢舉 | |||
瑩-113台電/中華雙榜 國三下 (2024/10/19): 動態規劃(Dynamic Programming,簡稱 DP)是一種通過將問題分解成子問題並重複利用子問題的解來解決複雜問題的技術。動態規劃演算法的分類主要是根據解決問題的方式、子問題的性質和應用場景來劃分的。
Fibonacci 數列或一些遞迴問題就是很經典的動態規劃
而 Dijkstra 是Greedy Algorithm,就如果A/B一樣,但它在更新最短路徑的過程中,實際上也有一種基於先前狀態去計算下一個答案的意味,跟遞歸有點類似。
舉例來說,Dijkstra到最後的算式大概如下
先算 A -> C 再算 A -> C -> E
先算 A -> B 再算 A -> B -> F
雖然覺得沒有Dynamic Programming,但相較有啦 | 檢舉 | ||
考試客 大四上 (2024/10/20): (A) Prim演算法:
是用於尋找最小生成樹的貪心演算法,並不屬於動態規劃法。
(B) Kruskal演算法: 也是一種用於尋找最小生成樹的貪心演算法,並不屬於動態規劃法。
(C) Dijkstra演算法: 屬於動態規劃法,專門用於計算加權圖中從單一源點到其他所有點的最短路徑,使用了子問題的最優解來構建全局最優解。
(D) 快速排序: 是一種排序演算法,屬於分治法(Divide and Conquer),並不屬於動態規劃法。
| 檢舉 |
|
|