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

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

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

好比我们随手画一棵树,可能丑了点,勿怪:

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

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

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


树形DP


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

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

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

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

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

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

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

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

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

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

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


转移历程


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

,

欧博官网ALLbet6.com

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

,

有没有发现什么纪律?

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

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

很简朴,由于这两条链路最长。以是这样加起来之后就可以保证获得的链路最长。这两条链路都是从叶子节点通往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.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)

到这里,这道有趣的问题就算是解说完了,不知道文中的两种做法人人都学会了吗?第一次看可能会以为有些蒙,问题许多这是正常的,但焦点的原理并不难,画出图来好好演算一下,一定可以获得准确的效果。另外,今天第一次在次条当中接到了广告,嘿嘿,不外这笔钱我并不会自己留着,我会把广告以及之前粉丝打赏的相关收入所有以送书的形势回馈粉丝。详细的形式以及相关书籍还没有想好,我会在后序的文章底部同步相关信息的,万万不要错过哈。