動態規劃法(Dynamic programming)

文藝復興
高級會員
發表於 2021年3月29日 12:38
點閱數 50

動態規劃法(Dynamic programming)是分治法的變化,將問題細分成一群較簡單的子問題,並以特定順序進行處理進而完成解决。其中一次只解決一個小的子問題,並保存結果供之後使用,避免不必要的重複運算。然後依問題大小漸增順序持續解決所有子問題,將這些小的子問題的結果組成原問題的解法。在許多情況中,如此的運算解法可經證實為已解問題的最佳解法。

動態規劃法時常用於優化的問題處理,其中目的是讓特定的運算達成最大或最小的效果。

基本思路

動態規劃背後的基本思路與分治法非常相似也非常的簡單。大致上,若要解一個給定問題,我們需要了解其不同的部分(即子問題),按順序求解子問題,前一子問題的解,為後一子問題的求解提供了有用的資訊。在求解任一子問題時,列出各種可能的區域性解,通過決策保留那些有可能達到最優的區域性解,丟棄其他區域性解。依次解決各子問題,最後一個子問題就是初始問題的解。

為了減少計算,會將不同階段存放在二維陣列中。

與分治法的不同

適合於用動態規劃法的問題,經分解後得到的子問題往往不是互相獨立的(即下一個子問題的求解是建立在上一個子問題的解的基礎上,進行進一步的求解)。

適用的情況

能用動態規劃法解決的問題通常有以下幾個特質

1. 最佳子結構原理 如果問題的最佳解所包含的子問題的解也是最佳的,我們就稱該問題具有最佳子結構性質(即滿足最佳化原理)。

2. 無後效性 即子問題的解一旦確定,就不再改變,不受在這之後、包含它的更大的問題的求解決策影響。也就是子問題以後的過程不會影響以前的狀態,只與當前狀態有關。

3. 有子問題重疊性質 在用遞迴演算法自頂向下對問題進行求解時,每次產生的子問題並不總是新問題,有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質,對每一個子問題只計算一次,然後將其計算結果儲存在一個表格中,當再次需要計算已經計算過的子問題時,只是在表格中簡單地檢視一下結果,從而獲得較高的效率,降低了時間複雜度。

解題步驟

定義主問題與子問題之間的關係 → 使用陣列儲存子問題的解 → 是否需要找出最佳解路徑

(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)

© 2021 - 耐美知識網