重返动态规划

如果你搜索动态规划, 那么你能找到的绝大多数资料都会告诉你,动态规划,是一种把问题拆解为子问题,然后再利用子问题之间的关系列出状态转移方程,最后求把问题变成一个动态决策求最优解的方法。 但是这种说法实在是过于抽象了, 这个描述离实际我们编写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的类型是一个元组<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)}.

接着我们需要用题目中的限制条件,不能有相邻桶的类型相同,来链接所有可能的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多行,无比清晰。。。。。。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,547评论 6 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,399评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,428评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,599评论 1 274
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,612评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,577评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,941评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,603评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,852评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,605评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,693评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,375评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,955评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,936评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,172评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,970评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,414评论 2 342