動態規劃
就地價值更新(in-place value updates)
掃描狀態時你面臨一個選擇:用舊值算出所有新值、最後再一次替換掉,或是一算出某個價值就立刻覆寫,讓同一輪掃描中後面的狀態馬上看到這個新數字。後一種做法就是「就地」更新,它通常收斂得更快,因為好的資訊在單一輪掃描內就擴散開來,而不必等下一輪。
就地評估只保有一個陣列,一算出某狀態的價值就立刻寫入,於是後面狀態的回溯會用到新舊混合的值。此時更新順序變得重要——沿著價值流動的方向掃描,可以大幅加快收斂。它也把記憶體用量減半,因為你不再保留兩份表。它是多數實用動態規劃的預設做法,也是非同步方法的基本構件。
另见