重返动态规划

如果你搜索动态规划， 那么你能找到的绝大多数资料都会告诉你，动态规划，是一种把问题拆解为子问题，然后再利用子问题之间的关系列出状态转移方程，最后求把问题变成一个动态决策求最优解的方法。 但是这种说法实在是过于抽象了， 这个描述离实际我们编写code的距离实在是太遥远了， 你一旦去看那些文章那些使用c语言写的代码，你就会发现他们一般都有一个莫名其妙的数组， 再加上或多或少的几个莫名其妙的循环嵌套，整个代码和上面算法的描述简直和动态决策简直是风马牛不相及 。最后给新人的感觉反而是这个算法很难懂。

问题出在哪呢？ c语言是无法表达这个算法的。 因为c语言根本不能去描述子问题之间的关系(Relation)。 而专门解决关系的语言是存在的， 就是逻辑式编程。不过在逻辑式编程中，也存在大量不同的语言，我们应该如何去选择语言呢。 首先我们可以尝试先从不同角度来看动态规划。

另一个角度： 图

如果你上过算法课，你的老师肯定会告诉你，解决DP问题(当然，在不考虑使用语言的 情况下)， 是有通用的模板的：所有动态规划问题都可以归化为一个在有向无环图（DAG）中求解最短/最长路径的问题， 你一定可以找到一种映射关系，把原问题中的对象映射到图上的节点和边。这种描述听起来不是那么直观，为什么一定可以？
回到DP问题的定义，在DP问题中，当我们定义了子问题之后， 这些子问题（可以把子问题看成函数/关系， 如果你不会Logic Programming的话，就理解成函数把）在区不同值的时候是有一定的关系的， 本质他们形成了一个决策状态机，状态机显然是一个图。所以这种映射总是存在的。

既然动态规划问题可以看成图，那为什么一定是DAG呢， 其实也很好理解，如果我们的算法要成立（sound），他一定能找到这个问题的解。如果图上出现环，那么最长路径是不存在的，我们只能求解某些特定的最短路问题，这已经和LP定义中的最优解矛盾了，因为我们必找不到最大解。从状态转移的角度来说，也就是我们会面对不停在一些状态打转的问题，我们的决策可能无法在有限步数内结束，算法不收敛。

从上面的分析我们可以看出，动态规划不但是一个分解子问题后的决策问题，它还蕴含了一个条件，我们的子问题关系必须是单调的。这一点如果我们需要证明我们的问题使用动态规划后成立，必须要利用好，这也是这两天重新翻算法导论我才意识到的。

另一个角度： 格(Lattice)

问题是单调的！！
也就是说从抽象代数的角度上来说我们可以把 子问题取不同值时候的状态放到一个格上， 如果我们的问题可以用DP解决那么也就是说我们的lattice 必须是有限高度的。在计算机科学说，说到格我们会很自然的联想到求解不动点的证明也是放在格里去证明的。 这也暗示着我们，如果我们的编程语言语义适合求解不动点，那么也将非常适合描述动态规划问题。 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是自然有序的，因为我们的限制条件是不能从相邻的位置取， 那么所有的桶一定可以被使用自然数编号。 所以我们可以使用如下代码描述输入。

// 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).

桶的顺序已经形成了一个天然的拓扑顺序，也就是说我们的node只要是一个桶的，拓扑顺序就相同，在这里我们不妨令图中的节点代表桶+当前桶中我们选择的物品的类型和重量。也就是Node的类型是一个元组.
用一下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)}.

接着我们需要用题目中的限制条件，不能有相邻桶的类型相同，来链接所有可能的node

.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多行，无比清晰。。。。。。