利用动态规划(DP)进行全局比对(一)

动态规划是一种非常重要的方法,但是也很难理解。在此将通过实例来浅显的探讨一下动态规划的思想以及在早期的生物信息学中如何应用动态规划进行全局比对。

1、Dynamic programming —— 从背包问题说起

关于理解动态规划的例子网上有很多,此处以《图解算法》中的一个背包问题来入门动态规划。

1.1 背包问题:假设你是个小偷,背着一个可装4磅东西的背包。你可盗窃的商品有如下三件,为了使得盗窃商品的价值最大,该如何选择呢?

商品.png

很多人可能第一反应便是枚举法:将所有可能的装法都列出来,比较大小,取最大者即可。由于这里的商品较少,很容易就能列出所有的8种携带方法,然后去掉超重的,在剩下的组合中选择价值最大的即可。但是这种算法的复杂度为O(2**n),非常的慢。
稍微学过一些算法的人可能会想到贪心算法:先拿值钱的,能拿多少拿多少,但是在这里贪心算法得到的真的是最优解吗?贪心算法偷走的商品为音响(3000磅),但是这里最优解明显是(电脑+吉他,3500磅)。这也暴露了贪心算法的一个重大缺点,贪心算法得到的常常只是接近全局最优解而非真正的全局最优解,当然这不在我们的讨论范畴内。
下面来看看如何使用动态规划来得到最优解。

1.2 理解动态规划:从填网格开始

动态规划的中心思想是将大问题(网格)分解为小问题(小网格),先解决小问题的最优解最后综合得到大问题的最优解。上面背包问题的网格如下:


QXE%$DU3Z73F~NAI%OYK.png
1.2.1 吉他行

这是吉他行,意味着你将尝试将吉他装入背包。在每个单元格,都需要做一个简单的决定:偷不偷吉他?别忘了,你要找出一个价值最高的商品集合。
第一个单元格表示背包的容量为1磅。吉他的重量也是1磅,这意味着它能装入背包!因此这个单元格包含吉他,价值为1500美元。
与这个单元格一样,每个单元格都将包含当前可装入背包的所有商品。
这行的其他单元格也一样。别忘了,这是第一行,只有吉他可供你选择。换言之,你假装现在还没法盗窃其他两件商品。


PK}R$SJL08%`POIH@0V0KS.png

别忘了, 你要做的是让背包中商品的价值最大。 这行表示的是当前的最大价值。它指出,如
果你有一个容量4磅的背包,可在其中装入的商品的最大价值为1500美元(现在只有一把吉他给你偷)。

1.2.2 音响以及其他行

我们来填充下一行——音响行。你现在出于第二行,可偷的商品有吉他和音响。在每一行,可偷的商品都为当前行的商品以及之前各行的商品。因此,当前你还不能偷笔记本电脑,而只能偷音响和吉他。我们先来看第一个单元格,它表示容量为1磅的背包。在此之前,可装入1磅背包的商品的最大价值为1500美元。
该不该偷音响呢?

背包的容量为1磅,能装下音响吗?音响太重了,装不下!由于容量1磅的背包装不下音响,因此最大价值依然是1500美元。
1XH2~F(S$K0F5WY3U_}G3N.png

接下来的两个单元格的情况与此相同。在这些单元格中,背包的容量分别为2磅和3磅,而以前的最大价值为1500美元。
J8@B%00{G_B0BH@5_7KU7D3.png

由于这些背包装不下音响,因此最大价值保持不变。

背包容量为4磅呢?终于能够装下音响了!原来的最大价值为1500美元,但如果在背包中装入音响而不是吉他,价值将为3000美元!因此还是偷音响吧。
3K53CLS9}P}$J@8PP6A64$6.png

此时你更新了最大价值!如果背包的容量为4磅,就能装入价值至少3000美元的商品。在这个网格中,你逐步地更新最大价值。
%)3TVGKB2I@Q@ZS[9V]0N`U.png
1.2.3 电脑行

电脑行的填值情形与音响行相似,此处为就不一步步推理了。


KR`2P`4Y4UJ1FI5T8L`16UU.png

image.png

对于容量为4磅的背包,填最后一个网格的情况很有趣。这是非常重要的部分。当前的最大价值为3000美元,你可不偷音响,而偷笔记本电脑,但它只值2000美元。价值没有原来高。但等一等,笔记本电脑的重量只有3磅,背包还有1磅的容量没用!

在1磅的容量中,可装入的商品的最大价值是多少呢?你之前计算过。
image.png

你可能始终心存疑惑:为何计算小背包可装入的商品的最大价值呢?但愿你现在明白了其中的原因!余下了空间时,你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为3500美元,因此偷它们是更好的选择。
最终的网格类似于下面这样。
image.png

答案如下:将吉他和笔记本电脑装入背包时价值最高,为3500美元。
其实,计算每个单元格的价值时,使用的公式都相同。
这个公式如下:


image.png

2、最长公共子串

在进行探讨最长公共子串问题前,先来总结下前面背包问题可得到的一些结论:

  1. 动态规划可帮助你在给定约束条件下找到最优解。在背包问题中,你必须在背包容量给定的情况下,偷到价值最高的商品。
  2. 在问题可分解为彼此独立且离散的子问题时,就可使用动态规划来解决。
    每种动态规划解决方案都涉及网格。
  3. 单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
  4. 每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。
2.1 最长子串问题:某天一位同学想在你自建的词典上面查询单词fish,但是一不小心输入了hish。但是词典中没有hish,在你的字典中,根本就没有这样的单词,但有几个类似的单词fish or vista?

hish和fish都包含的最长子串是什么呢? hish和vista呢?这就是我们要计算的值。

2.2 首先,我们要做的依然是画网格
image.png

在这里我们就不一步步画网格推导了,直接给出最终的网格:


image.png

在上面的背包问题中,我们给出了一个公式来计算背包网格中每个位置的值。这里我们依然可以给出一个计算最长公共子串网格每个位置的值的公式。


image.png

image.png

这个公式的伪代码如下:
if word_a[i] == word_b[j]:   #两个字母相同
    cell[i][j] = cell[i-1][j-1] + 1  
else:        #两个字母不同
    cell[i][j] = 0
#大白话讲即是 字母相同时等于斜左上方网格的值加1,不同的话则为0

3、小结

这里给了两个例子来浅显的探讨如何理解动态规划方法,而对于动态规划方法的使用:

  1. 需要在给定约束条件下优化某种指标时,动态规划很有用。
  2. 问题可分解为离散子问题时,可使用动态规划来解决。
  3. 每种动态规划解决方案都涉及网格。
  4. 单元格中的值通常就是你要优化的值。
  5. 每个单元格都是一个子问题,因此你需要考虑如何将问题分解为子问题。
  6. 没有放之四海皆准的计算动态规划解决方案的公式,这也是为什么在这里放两个例子的原因,另外想要更好的理解动态规划,必须要手动画格子,画格子,画格子。

4、背包问题的python 动态规划实现代码

def KnapsackProblem(row, col):
    # initialize the grid
    grid = [[0]+[1500]*col] + [[0, 1500]+[None]*(col-1) for _ in range(len(row)-1)]
    for i in range(1, len(row)):
        for j in range(1, col+1):
            if j >= goods[i][0]:
                grid[i][j] = max(grid[i-1][j], row[i][1]+grid[i-1][j-row[i][0]])
            else:
                grid[i][j] = grid[i-1][j]
    return grid


raw_goods = [(1, 1500), (4, 3000), (3, 2000), (4, 5000)]
# format goods
goods = {i: raw_goods[i] for i in range(len(raw_goods))}
Knapsack = 4
print(KnapsackProblem(row=goods, col=Knapsack))
print(goods)

参考:算法图解

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