首页 科技正文

临沂招聘网:树形DP——‘动’态计划与数据结构的连系,在树上做DP

admin 科技 2020-09-20 54 1

本文始发于小我私家民众号:TechFlow,原创不易,求个关注


今天是算法与数据结构的第15篇,也是动态计划系列的第4篇。

之前的几篇文章当中一直在聊背包问题,不知道人人有没有以为有些腻味“了”。虽然经典的文章当中背包一共有九讲,但除“了”竞赛选手,我们能明“了”到单调优化就已经异常精彩“了”。像是带有依赖的背包问题,和夹杂背包问题,有些剑走偏锋,以是这里不多做分享。若是人人感兴趣可以自行百度背包九讲查看,今天我们来看一个有趣的问题,通过这个有趣的问题,我们来领会一下在『树形结构』当中做动态计划的方式。

这个问题题意很简 朴[,给定一棵树,并不一定是二叉树,树上的树枝带有权重,可以看成是长度。要求树上最长的链路的长度是多少?

好比我们随手画一棵树,可能丑“了” 『点』[[,勿怪:

若是让我们用肉眼来看,稍微实验一下就能找到谜底,最长的路径应该是下图当中红色的这条:

然则若是让我们用算法来算,应该怎么办呢?

这道题实在有一个异常巧妙的设施,我们先不讲,先来看看动态计划怎么解决这个问题。

树形DP

动态计划并不只是可以在数组当中运行,实际上只要知足动态计划的状态转移的条件和无后效性就可以使用动态计划,无论在什么数据结构当中。树上也是一样的,明“了”“了”这 『点』[[之后,就只剩下“了”两个问题,第一个是状态是什么,第二个问题是状态之间怎么转移?

在之前的背包问题当中,状态就是背包当前用的体积,转移呢就是我们新拿一个物品的决议。然则这一次我们要在树上举行动态计划,相对来说状态和对应的转移会隐藏一些。没有关系,我会从头开始整理思绪,一 『点』[[一 『点』[[将推导和思索的历程解说清晰。

首先,我们都知道,状态之间转移实在本质上是一个由局部盘算整体的历程。我们通过相对容易的子状态举行转移,获得整体的效果。这个是动态计划的精髓,某种程度上来说它和分治法也对照靠近,都存在大问题和小问题之间逻辑上的关系。以是当我们面临一个大问题一筹莫展的时刻,可以借鉴一下分治法,〖思索一下从小〗问题入手。

以是,我们从小到大,由微观到宏观,【来看看最】简 朴[的情形:

这种情形很明显,链路只有一条,以是长度自然是5 + 6 = 11,这显然也是最长的长度。这种情形都没有问题,下面我们来把情形稍微再变得庞大一些,我们在树上多加入一层:

这张图稍微庞大“了”一些,然则路径也不难找到,应该是E-B-F-H。路径的总长度为12:

然则若是我们调换一下路径长度呢,好比我们把FG和FH的路径加长,会获得什么效果呢?

显然这种情形下谜底就变“了”,FGH是最长的。

举这个例子只为“了”说明一个很简 朴[的问题,「即」对于一棵树而言它上面的最长路径并不一定经由根节 『点』[[。好比适才的例子当中,若是路径必须要经由B的话,最长只能构造出4+2+16=22的长度,然则若是可以不用经由B的话,可以获得最长的长度是31。

得出这个结论看似似乎没有用,但实在对于我们理清思绪很有辅助。既然我们不能保证最长路径一定会经由树根,以是我们就不能直接转移谜底。那我们应该怎么办呢?

回覆这个问题光想是不够的,依然需要我们来考察问题和深入思索。

转移历程

我们再考察一下下面这两张图:

有没有发现什么纪律?

由于我们的数据结构就是树形的,以是这个最长路径不管它连通的哪两个节 『点』[[,一定可以保证,它会经由某一棵子树的根节 『点』[[。不要小看这个不起眼的结论,实际上它异常主要。有“了”这个结论之后,我们将整条路径在根节 『点』[[处切开。

切开之后我们获得“了”两条通往叶子节 『点』[[的链路,问题来“了”,根节 『点』[[通往叶子节 『点』[[的链路有许多条,「为什么是这两条」呢?

很简 朴[,由于这两条链路最长。以是这样加起来之后就可以保证获得的链路最长。这两条链路都是从叶子节 『点』[[通往A的,以是我们获得的最长链路就是以A为根节 『点』[[的子树的最长路径。

我们前面的剖析说“了”,最长路径是不能转移的,然则到叶子的最长距离是可以转移的。我们举个例子:

F到叶子的最长距离显然就是5和6中较大的谁人,B稍微庞大一些,D和E都是叶子节 『点』[[,这个容易明“了”。它另有一个子节 『点』[[F,对于F来说它并不是叶子节 『点』[[,然则我们前面算到“了”F到叶子节 『点』[[的最长距离是6,以是B通过F到叶子节 『点』[[的最长距离就是2 + 6 = 8。这样我们就获得“了”状态转移方程,不外我们转移的不是要求的谜底而是从当前节 『点』[[到叶子节 『点』[[的最长距离和次长距离

由于只有最长距离是不够的,由于我们要将根节 『点』[[的最长距离加上次长距离获得经由根节 『点』[[的最长路径,由于我们之前说过,所有的路径一定经由某棵子树的根节 『点』[[。这个想明“了”“了”是空话,然则这个条件简直很主要。既然所有的链路都至少经由某一个子树的根节 『点』[[,那么我们算出所有子树经由根节 『点』[[的最长路径,其中最长的谁人不就是谜底么?

下面我们演示一下这个历程:

上图当中用粉色笔标出的就是转移的历程,对于叶子节 『点』[[来说最长距离和次长距离都是0,主要的转移历程发生在中心节 『点』[[上。

转移的历程也很容易想通,对于中心节 『点』[[i,我们遍历它所有的子节 『点』[[j,然后维护最大值和次大值,我们写下状态转移方程:

状态转移想明“了”“了”,【剩下的就是编码的问题】“了”。可能在树上尤其是递归的时刻做状态转移有些违反我们的直觉,但实际上并不难,我们写出代码来看下,我们首先来看建树的这个部门。为“了”简化操作,我们可以把树上所有的节 『点』[[序号看成是int,对于每一个节 『点』[[,都市有一个数组存储所有与这个节 『点』[[毗邻的边,包罗父亲节 『点』[[。

由于我们只关注树上的链路的长度,并不体贴树的结构,树建好“了”之后,不管以哪一个 『点』[[为整体的树根效果都是一样的。以是我们随便找一个节 『点』[[作为整棵树的根节 『点』[[举行递归「即」可。强调一下,这个是一个很主要的性子,由于本质上来说,树是一个无向无环全连通图。以是不管以哪个节 『点』[[为根节 『点』[[都可以连通整棵子树。

我们建立一个类来存储节 『点』[[的信息,包罗id和两个最长以及次长的长度。我们来看下代码,应该比你们想的要简 朴[得多。

class Node(object):
    def __init__(self, id):
        self.id = id
        # 以当前节 『点』[[为根节 『点』[[的子树到叶子节 『点』[[的最长链路
        self.max1 = 0
        # 到叶子节 『点』[[的次长链路
        self.max2 = 0
        # 与当前节 『点』[[相连的边
        self.edges = []

    # 添加新边
    def add_edge(self, v, l):
        self.edges.append((v, l))


# 建立数组,存储所有的节 『点』[[
nodes = [Node(id) for id in range(12)]

edges = [(013), (021), (131), (144), (152), (565), (576), (287), (792), (7108)]

# 〖建立边〗
for edge in edges:
    u, v, l = edge
    nodes[u].add_edge(v, l)
    nodes[v].add_edge(u, l)

由于我们只是为“了”转达思绪,以是省去“了”许多面向对象的代码,然则对于我们明“了”问题思绪来说应该是够“了”。

下面,我们来看树上做动态计划的代码:

def dfs(u, f, ans):
    nodeu = nodes[u]
    # 遍历节 『点』[[u所有的边
    for edge in nodes[u].edges:
        v, l = edge
        # 注重,这其中包罗“了”父节 『点』[[的边
        # 以是我们要判断v是不是父节 『点』[[的id
        if v == f:
            continue
        # 递归,更新谜底
        ans = max(ans, dfs(v, u, ans))
        nodev = nodes[v]
        # 转移最大值和次大值
        if nodev.max1 + l > nodeu.max1:
            nodeu.max2 = nodeu.max1
            nodeu.max1 = nodev.max1 + l
        elif nodev.max1 + l > nodeu.max2:
            nodeu.max2 = nodev.max1 + l
    # 返回当前最优解
    return max(ans, nodeu.max1 + nodeu.max2)

看起来很庞大的树形DP,实在代码也就只有十来行,是不是简 朴[得有些出人意料呢?

然则照样老生常谈的话题,这十几行代码看起来简 朴[,然则其中的细节照样有一些的,尤其是涉及到“了”递归操作。对于递归不是稀奇熟悉的同砚可能会有些吃力,建议可以凭据之前的图 手[动在纸上验算一下,信赖会有更深刻的熟悉。

另一种做法

文章还没完,我们另有一个小彩蛋。实在这道题另有另外一种做法,这种做法异常机智,也一样先容给人人。

之前我们说“了”,由于树纪录的是节 『点』[[的连通状态,以是不管以哪个节 『点』[[为根节 『点』[[,都不会影响整棵树当中路径的长度以及结构。既然如此,若是我们富有想象力的话,我们把一棵树压扁,是不是可以看成是一串连在一起的绳子或者木棍?

我们来看下图:

我们把C 『点』[[向B 『点』[[靠近,并不会影响树的结构,究竟这是一个抽象出来的架构,我们并不关注树上树枝之间的夹角。我们可以想象成我们拎起“了”A 『点』[[,其他的几 『点』[[由于重力的作用下垂,最后就会被拉成一条直线。

好比上图当中,我们拎起“了”A 『点』[[,BCD都垂下。这个时刻位于最下方的 『点』[[是D 『点』[[。那么我们再拎起D 『点』[[,最下方的 『点』[[就成“了”C 『点』[[,那么DC之间的距离就是树上的最长链路:

我们把整个历程梳理一下,首先我们随便选“了”一个 『点』[[作为树根,然后找出“了”距离它最远的 『点』[[。第二次,我们选择这个最远的 『点』[[作为树根,再次找到最远的 『点』[[。这两个最远 『点』[[之间的距离就是谜底。

这种做法异常直观,然则我也想不到可以严谨证实的方式,有思绪的小伙伴可以在后台给我留言。若是有些想不通的小伙伴可以自己试着用几根绳子连在一起,然后拎起来做个实验。看看这样拎两次获得的两个 『点』[[,是不是树上距离最远的两个 『点』[[。

最后,我们来看下代码:

def dfs(u, f, dis, max_dis, nd):
    nodeu = nodes[u]
    for edge in nodes[u].edges:
        v, l = edge
        if v == f:
            continue
        nodev = nodes[v]
        # 更新最大距离,以及最大距离的 『点』[[
        if dis + l > max_dis:
            max_dis, nd = dis+l, nodev
        # 递归
        _max, _nd = dfs(v, u, dis+l, max_dis, nd)
        # 若是递归获得的距离更大,则更新
        if _max > max_dis:
            max_dis, nd = _max, _nd
    # 返回
    return max_dis, nd

# 第一次递归,获取距离最大的节 『点』[[
_, nd = dfs(0-100None)
# 第二次递归,获取最大距离
dis, _ = dfs(nd.id, -100None)
print(dis)

〖到这里〗,这道有趣的问题就算是解说完“了”,不知道文中的两种做法人人都学会“了”吗?第一次看可能会以为有些蒙,问题许多这是正常的,但焦 『点』[[的原理并不难,(画出图来好好演算)一下,一定可以获得准确的效果。

另外,今天第一次在次条当中接到“了”广告,嘿嘿,不外这笔钱我并不会自己留着,我会把广告以及之前粉丝打赏的相关收入所有以送书的形势回馈粉丝。〖详细的形式以及〗相关书籍还没有想好,我会在后序的文章底部同步相关信息的,万万不要错过哈。

今天的文章就是这些,若是以为有所收获,请随手 『点』[[个关注或者转发吧,你们的举手之劳对我来说很主要。

,

阳光在线

阳光在线www.lanbao-film.com({原诚信在}线)现已开放阳光在线手机<版>下载。<阳光>在线游戏公平、公开、公正,用实力赢取信誉。

版权声明

本文仅代表作者观点,
不代表本站Allbet的立场。
本文系作者授权发表,未经许可,不得转载。

评论

精彩评论
  • 2020-09-20 00:01:24

    Allbet Gmaing开户欢迎进入Allbet Gmaing开户(www.aLLbetgame.us):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。我就想发个言