数据结构学习笔记(01背包问题/图问题)-创新互联

01背包问题:在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求如何安排能带走最多价值的物品?

创新互联主要从事网站设计、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务通州,十载网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

动态规划解决背包问题:

设f(i,W)表示,从前i件物品中挑选一些,放进一个空间为W的背包中能获得的大总价值。

那么如果第i件物品也在最优解中,那么f(i,W)=f(i-1,W-Wi)+Pi,因为从最优解中吧i去掉,前面选中的物品肯定能使一个空间为W-Wi的背包价值大化,不然它们也不会出现在最优解中。

而如果第i件物品不在最优解中,那么f(i,W)=f(i-1,W),第i件物品没有占用空间。

通过比较上面两个表达式的大小可以决定第i个物品是不是在最优解中。这就形成了一个递归。

但是如果W

递归的终止条件是i=1.第一件物品如果能装下,价值就是Pi,装不下就是0.

有许多计算过程重复,可以把重复的f(i,w)保存下来降低复杂度。

图:

图可以用邻接表法表示。每个点拥有一个数组,记录了和它相邻的点。

图也可以用矩阵法表示,横纵是各个点,如果这两个点是相邻的则矩阵的值为1,否则0。只需要对角线的一半,因为另一半是重复的。横纵相同的点设为0.

广度优先搜索BFS:

选取某一点作为源点开始搜索,每一轮将某个点所有相邻的点搜索完毕(称为将此点探索完毕),然后从剩下未探索完毕点里选取一个作为下一轮探索的起点(选一个距离最近的,使用队列维护)。

因为每个点只能被发现一次,每个点(除了源)都有确定的父结点,因此广度优先搜索会形成一棵树。(广度优先树)

具体算法:

每个点有除了数据域,有三个字段。第一个是颜色,白色的表示没被发现,灰色的表示已经被发现了但是没有探索完毕(会出现在待探索队列中,或者刚出队,是本轮搜索的起点。),黑色的表示探索完毕(与其相邻的点全部被发现了)。第二个字段表示点的父亲(P,C相邻,探索P周边的时候第一次发现C使得C由白边灰,则P是C的父亲)。第三个结点表示深度(和源点的距离,儿子结点的深度为父亲结点的深度加一)。从源点开始,对其所有相邻的点进行搜索,每新发现一个点就涂成灰色,并且加入待探索队列中。如果某点周边探索完毕,此点就被涂成黑色,然后从队列中取出一个来进行下一轮搜索,直到所有结点变黑,队列中也变空,则整个图搜索完毕。

深度优先搜索:

从源点开始搜索,如果其存在未被发现(白色)的相邻点,就涂成灰色,并以那个点为起点继续往深处探索(递归)。如果某个点的所有邻点都被发现并且依次递归探索过了,那么把此点涂成黑色(形成了一棵树,此结点是树的根节点。)。如果地图中还存在白色的点,那么设为源点开始新一轮搜索(又形成一棵树)。因此深度优先搜索形成一个森林。

深度优先搜索会维护一个全局的时间戳变量,每次新发现一个点并开始一次递归搜索的时候时间戳自增一次。每个点会记录两个时间戳,一个是它被发现的时刻,一个是它被探索完毕的时刻(所有邻点都变黑)

最小生成树:能连通所有点,并且使得各边权值和最小的树.

构造最小生成树使用贪心算法(贪心算法:每一步都采取对当前状况最有利的选择)。假设有一个边的集合A,是一棵最小生成树的一个子集。如果每次都能找到一条边来加入A(称为安全边),并且保证A依旧是某个最小生成树的子集,那么最终就能构造出最小生成树。

寻找安全边的依据:A是某最小生成树的子集,S是图中的一个割集且S不妨害A(S没有割到A的边),那么S中权值最小的一条边可以安全的加入A中而保持A的性质。

Kruskal算法:

并查集是一种维护集合关系的数据结构,能够快速的判断一个元素是否在某个集合中(或者两个元素是否在同一个集合中),以及将两个集合合并起来。

Kruskal算法首先将每个点都生成一棵树(一个并查集合),然后按照权值由小到大遍历各边(安全边)。如果某边两点属于不同的并查集则合并两个集合,直到最后形成一棵树,也就是最小生成树。

Prim算法:

把一个点作为树的跟结点,从剩下的点里,每次选取一个离树最近的点连入树中,最终形成最小生成树(最近的意思是说,把这个点连接到树上的某个点,连线的权值最小。通常使用用斐波那契堆实现的最小优先队列来维护剩余的点)

具体算法:每个点有一个d字段表示和树的最小距离,初始时根结点的d设为0,其余结点的设为无穷大。每个结点还有一个p字段表示其父。准备一个以d为依据的最小优先队列将图中各点放入。

每次从最小优先队列中取出一个点S并进行如下操作:

1.将S加入树中(通过其父,队列中第一个取出的是d为0的根节点,无父)

2.遍历和S相邻的结点,如果某个邻结点C在队列中且SC的权值比C的d字段要小,则将d字段降低为此权值(自然在队列中的顺序得到提升),然后将C的父设为S。

单源最短路径:求从某源点出发,到图中各点的最短路径(各边权值不同)

最短估计路径和松弛:给每个点一个属性d,表示这个点距离源点的估计值,使得实际的最短路径权值不会超过这个值.

对点u和v进行松弛,是有可能降低v点的路径估计值的操作(d值)。如果d(v)>d(u)+uv,那么就将d(v)改为d(u)+uv,且将v的父设为u。意思是,u对v说,大哥啊,你原来的路太长了,改从我这经过吧!

对于从S到某一点v的最短路径,从s开始一路松弛下去,最终v的d值一定等于最短路径的权值。Dijkstra算法依据此条性质求最短路径。

Dijkstra算法:(要求图中不存在负权边

使用一个以d为依据的最小优先队列来维护未求得最短路径的各点(初始时,源点的d值为零,其余点的d值为无穷大)。每次从最小优先队列取出一点,并对其相邻的点依次进行松弛操作,以期降低估计值。这样下次从队列中取出的点就是剩余估计值最小的那个点,最小优先队列可以保证对于某一条最短路径而言,各点事依据估计值依次松弛下去的,最终估计值就是最短路径的权值,并通过松弛得到的父子关系确定路径。本质也是一种贪心策略。

大流解决大二分匹配问题:

流网络:

一个有向图,拥有一对源点s和汇点v,图中每点都出现在s到v的一条路径中。对每一点而言,净流入为零(类似基尔霍夫电流定律),每边有个容量值(类似于线路的大电流),实际流量(类似于电流)不能超过容量。

残留网络,增广路径和大流的Ford-Fulkerson方法:

一个流网络的残留网络的每边的权值等于容量-实际流量,反应了一个流量网络还剩余的运载能力。残留网络中如果存在从源点到汇点的路径,则成为增光路径。顺着此路径增加沿路的流即可增加整个网络的流。反复寻找增广路径并沿路增加,如果最终找不到增广路径了,说明已经找到了网络的大流。这个寻找大流的方法就是Ford-Fulkerson方法。如果各路径的容量是有理数,此方法一定可以找到大流。如果各路径是整数,复杂度则相对较低(每次增广至少增加一个整数单位)

Edmonds-Karp算法:

对Ford-Fulkerson方法的改进,每次在残留网络中寻找增广路径时,是寻找一个源点到汇点的最短路径。

Floyd-Warshall算法求两点间最短路径:

此算法通过动态规划的方式,递归求得图中任意两点间的最短路径。设某个图中前k个顶点的集合为Ak,若从i到j有若干这样的路径:i到k之间的中间点必须从集合Ak中选取。那么用d(i,j,k)来表示这些路径中最短的一条。显然当k为图的顶点树的时候,d(i,j,k)就是i和j之间的最短路径。

对于d(i,j,k),假如第k个点不i到j之间的中间点,那么d(i,j,k)=d(i,j,k-1),因为第k个点不影响路径;如果第k个点是i到j的中间点,那么路径分成两半,每一半都是对应两个端点间的最短路径,因此d(i,j,k)=d(i,k,k)+d(k,j,k)。因此d(i,k,k)+d(k,j,k)和d(i,j,k-1)谁比较小,决定了第k个点是否在i到j的最短路径上,形成递归。

递归的终止条件是k=0,此时没有中间点(空集),i和j直接相连,d(i,j,0)=W(i,j),也就是ij线的距离。

另外当k为i或j本身时,k必然不在中间点上,此时d(i,j,k)=d(i,j,k-1)

大二分匹配:

二分图:一个所有回路长度均为偶数的无向图,这样的图能够将顶点分为两部分,每部分内部各顶点间均不相连。

匹配:一个匹配是一个图的一组边的集合,图的每个顶点之多连接匹配中的一条边,如果没有就是这个点未被匹配到。一个匹配相当于将图中的若干顶点两两一对相连。

大二分匹配:假设一个二分图,顶点分为左,右两侧。每侧顶点内部互不相连。左侧每个顶点表示一个人,右侧每个顶点表示一份工作。二分图中每个连接人-工作的边表示这个人有能力做这项工作。每项工作最多只需要一个人,每个人最多只能完成一项工作,如何分配工作(匹配)才能人尽其用呢?这就是一个求二分图中大匹配的问题。

大流解决大二分匹配问题

在左侧顶点的左边加入源点,右侧顶点的右边加入汇点,连接源点-左侧各点-右侧各点-汇点的各边赋予1的容量,于是就构造出了一个流网络。由于各边容量均为1,那么使得此流网络形成大流的方案,也就是原二分图的大匹配了。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


文章题目:数据结构学习笔记(01背包问题/图问题)-创新互联
路径分享:http://myzitong.com/article/pccgi.html