重返動態(tài)規(guī)劃

如果你搜索動態(tài)規(guī)劃饮潦，那么你能找到的絕大多數(shù)資料都會告訴你爆袍，動態(tài)規(guī)劃，是一種把問題拆解為子問題践宴，然后再利用子問題之間的關(guān)系列出狀態(tài)轉(zhuǎn)移方程，最后求把問題變成一個動態(tài)決策求最優(yōu)解的方法爷怀。但是這種說法實在是過于抽象了阻肩，這個描述離實際我們編寫code的距離實在是太遙遠(yuǎn)了，你一旦去看那些文章那些使用c語言寫的代碼霉撵，你就會發(fā)現(xiàn)他們一般都有一個莫名其妙的數(shù)組，再加上或多或少的幾個莫名其妙的循環(huán)嵌套洪囤，整個代碼和上面算法的描述簡直和動態(tài)決策簡直是風(fēng)馬牛不相及徒坡。最后給新人的感覺反而是這個算法很難懂。

問題出在哪呢瘤缩？ c語言是無法表達(dá)這個算法的喇完。因為c語言根本不能去描述子問題之間的關(guān)系(Relation)。而專門解決關(guān)系的語言是存在的剥啤，就是邏輯式編程锦溪。不過在邏輯式編程中，也存在大量不同的語言府怯，我們應(yīng)該如何去選擇語言呢刻诊。首先我們可以嘗試先從不同角度來看動態(tài)規(guī)劃。

另一個角度：圖

如果你上過算法課牺丙，你的老師肯定會告訴你则涯，解決DP問題(當(dāng)然，在不考慮使用語言的情況下)冲簿，是有通用的模板的：所有動態(tài)規(guī)劃問題都可以歸化為一個在有向無環(huán)圖（DAG）中求解最短/最長路徑的問題粟判，你一定可以找到一種映射關(guān)系，把原問題中的對象映射到圖上的節(jié)點和邊峦剔。這種描述聽起來不是那么直觀档礁，為什么一定可以？
回到DP問題的定義吝沫，在DP問題中呻澜，當(dāng)我們定義了子問題之后，這些子問題（可以把子問題看成函數(shù)/關(guān)系惨险，如果你不會Logic Programming的話易迹，就理解成函數(shù)把）在區(qū)不同值的時候是有一定的關(guān)系的，本質(zhì)他們形成了一個決策狀態(tài)機平道，狀態(tài)機顯然是一個圖睹欲。所以這種映射總是存在的。

既然動態(tài)規(guī)劃問題可以看成圖，那為什么一定是DAG呢窘疮，其實也很好理解袋哼，如果我們的算法要成立（sound），他一定能找到這個問題的解闸衫。如果圖上出現(xiàn)環(huán)涛贯，那么最長路徑是不存在的，我們只能求解某些特定的最短路問題蔚出，這已經(jīng)和LP定義中的最優(yōu)解矛盾了弟翘，因為我們必找不到最大解。從狀態(tài)轉(zhuǎn)移的角度來說骄酗，也就是我們會面對不停在一些狀態(tài)打轉(zhuǎn)的問題稀余，我們的決策可能無法在有限步數(shù)內(nèi)結(jié)束，算法不收斂趋翻。

從上面的分析我們可以看出睛琳，動態(tài)規(guī)劃不但是一個分解子問題后的決策問題，它還蘊含了一個條件踏烙，我們的子問題關(guān)系必須是單調(diào)的师骗。這一點如果我們需要證明我們的問題使用動態(tài)規(guī)劃后成立，必須要利用好讨惩，這也是這兩天重新翻算法導(dǎo)論我才意識到的辟癌。

另一個角度：格(Lattice)

問題是單調(diào)的！荐捻！
也就是說從抽象代數(shù)的角度上來說我們可以把子問題取不同值時候的狀態(tài)放到一個格上愿待，如果我們的問題可以用DP解決那么也就是說我們的lattice 必須是有限高度的。在計算機科學(xué)說靴患，說到格我們會很自然的聯(lián)想到求解不動點的證明也是放在格里去證明的仍侥。這也暗示著我們，如果我們的編程語言語義適合求解不動點鸳君，那么也將非常適合描述動態(tài)規(guī)劃問題农渊。 Datalog正好就擁有這種語義。

例子：使用datalog（souffle language）求解DP問題

You have a sequence of n buckets. Each bucket Bi contains three items, where each item has some value and belongs to some category. Multiple items may belong to the same category. Your job is to select exactly one item from each bucket so that the total value of the selected tems is maximized, but such that no two items selected from adjacent buckets belong to the same category. Design an algorithm to determine which item should be selected from each bucket to maximize the total value. If there is no solution, your algorithm should state this.

這是一個典型的DP問題或颊。問題中bucket是自然有序的砸紊，因為我們的限制條件是不能從相鄰的位置取，那么所有的桶一定可以被使用自然數(shù)編號囱挑。所以我們可以使用如下代碼描述輸入醉顽。

// item has category ... and weight ... is in bucket ...
.type bucket <: number
.decl InBucket(category: symbol, weight: number, bk: bucket)
InBucket("c1", 200, 1).
InBucket("c1", 300, 1).
InBucket("c3", 150, 1).
InBucket("c1", 300, 2).
InBucket("c2", 200, 2).
InBucket("c3", 200, 2).
InBucket("c1", 500, 3).
InBucket("c3", 400, 3).
InBucket("c3", 200, 3).
InBucket("c2", 400, 4).
InBucket("c1", 200, 4).
InBucket("c1", 500, 4).
InBucket("c3", 200, 5).
InBucket("c1", 300, 5).
InBucket("c2", 400, 5).

桶的順序已經(jīng)形成了一個天然的拓?fù)漤樞颍簿褪钦f我們的node只要是一個桶的平挑，拓?fù)漤樞蚓拖嗤翁恚谶@里我們不妨令圖中的節(jié)點代表桶+當(dāng)前桶中我們選擇的物品的類型和重量系草。也就是Node的類型是一個元組 $<bucket, category ，weight>$ .
用一下souffle中的類型

.type node = [
    bucket : bucket,
    category : symbol,
    weight: number
]
.decl Node(n: node)
// if same category, we always pick the heaviest
Node([bucket, category, max_weight]) :-
    InBucket(category, _, bucket),
    max_weight = max w : {InBucket(category, w, bucket)}.

接著我們需要用題目中的限制條件唆涝，不能有相鄰?fù)暗念愋拖嗤叶迹瑏礞溄铀锌赡艿膎ode

.decl Edge(from: node, to: node)
Edge([b, c1, w1], [b+1, c2, w2]) :-
    Node([b, c1, w1]),
    Node([b+1, c2, w2]),
    c1 != c2.
Edge([1, c, w], [1, c, w]) :- Node([1, c, w]).

接下來，datalog最擅長的廊酣，求解DAG能耻！
這里是最長路徑

.decl PathLen(from: node, to: node, len: number)
PathLen(f, t, w) :- Edge(f, t), f = t, f = [b, c, w].
PathLen(f, t, w1+w2) :- 
    Edge(f, t), f != t, 
    f = [b1, c1, w1], t = [b2, c2, w2].
PathLen(f, t, l1+l2-w) :- 
    PathLen(f, mid, l1), 
    PathLen(mid, t, l2),
    mid = [b, c, w].
    
.decl LongestPath(n: number)
.output LongestPath
LongestPath(n) :- n = max l : PathLen(_, _, l).

總共40多行，無比清晰亡驰。晓猛。。凡辱。戒职。。

重返動態(tài)規(guī)劃

另一個角度： 圖

另一個角度： 格(Lattice)

例子：使用datalog（souffle language）求解DP問題

另一個角度：圖

另一個角度：格(Lattice)