资源描述：
《毕业设计-算法合集之《浅析差分约束系统》.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、狡层團的宪JI穡合——烫析菱分约東菜统华中师大一附中冯威[摘要]在面対多种多样的问题时，我们经常会碰到这样的情况：往往我们能够根据题目题面意思來建立一些简单的模型，但却面对这些模型无从下手。这时我们应该意识到，也许能够将这种模型与其他的模型之间搭起一座桥梁，使我们能够用更简单•直接的方式解决它。这里我们介绍一种方法，它很好地将某些特殊的不等式组与图相联结，让复杂的问题简单化，将难处理的问题用我们所熟知的方法去解决，它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过zju!5O8和zju!4
2、20两道题日解析差分约束系统在信息学题目中的应用，并逐渐归纳解决这类问题的思考方向。[目录]♦关键字【2】♦BelIman-ford算法【2】◊算法简单介绍【2】◊算法具体流程[2]◊例题一ZJU2008【4】♦差分约束系统【5】◊例题二ZJUI508[5]O线性程序设计[7]◊差分约束系统【7】◊例题三ZJU1420【8】♦结语[9]♦附录【9】[关键字]差分约束系统、不等式、单元最短路径、转化[正文]在分析差分约束系统之前，我们首先介绍一个解决单元最短路径问题的BellmanFord算法，它的应用十分广泛，在差分约束系统中更充当着重要的角色
3、。Bellman-ford算法算法简单介绍这个算法能在更一般的情况下解决最短路的问题。何谓一般，一•般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。我们这里仅以最短路径为例。Bellmanford类似于Dijkstra算法，对每一个节点vwV,逐步减小从起点s到终点v最短路的估计量dist[v]H至！I其达到真正的最短路径fflmindist[v]oBellman-ford算法同时返冋一个和尔值，如果不存在从源结点町达的负权冋路，算法返冋布尔值TRUE,反之返冋FALSEo算法具体流程1.枚举每条边(u,v)gE
4、(G)o2.对枚举到的边进行一次更新操作。1.冋到步骤1,此过程重复ml次，以确定没有更可以优化的情况°2.枚举每条边(u,V)若仍然存在可以更新的边，则说明有向图中出现了负权冋路,于是返冋布尔值FALSEo3.返冋布尔值TRUE。注：这里的更新操作是-•种松弛技术，以单元最短路径为例这个操作就是保证dist[vj<=dist[u]+w[u,v],即ifdist[v]>dist[u]+w[u,v]thendist[vj=dist[u]+w[u,v],如果是最长路径则是保证dist[v]>=dist[u]+w[u,v]o定义一一个有向图G=(V,
5、E),w(u,v)表示山结点u到v的边的权值。伪代码如下:Fori=lto
6、V
7、C
8、H1Dofor每条边(u,v)gE
9、G
10、Do更新操作(u,v,w(u,v))For每条边(u,v)gE
11、G
12、Do讦仍然有可更新内容thenreturnFalseReturnTrue下图描述了该算法的操作过程，粗线条代表已更新线段证明"下Bellman-Ford算法的止确图例中，S为源节点，粗线断覆盖的边表示最近一次执行更新操作的边。算法执行IVI-1次操作，每次操作都对所有可以进行松弛操作的边进行扩展。性。1.设G=(V,E)为有向加权图，源节点为S,加权函数为
13、w：E->Ro如果有负权回路则Bellman_ford算法」定会返冋布尔值false,否则返冋TRUE。证明略。1.设G=(V,E)为有向加权图，源节点为S加权函数为w：E-)R,并且G不含从s口J达的负权冋路，则算法Bellman_ford终止时,对所有从s可达的结点v有d［v］=mindist(s,v)。证明：设v为从s可达的节点，且p=为从s到v的一条最短路径，其中vO=s,vk=v。因为路径p是简单路径,所以k<=IVI-lo我们希望通过归纳证明对i=O,l,…,k,在对G的边进行完第i趟操作后有d［vi］=m
14、indist(s,vi),.fl.该等式此后一直保持成立，因为总共有IV1-1次操作，所以上述结论证明命题成立。我们发现与Dijkstra不同，Bellmanford更多的是对边进行操作，在稀疏图，即点多边少的图中，用BellmanFord更能高效的解决单元最短路径问题。下面一道例题來进一步熟悉BellmanFord并与Dijkstra作一下简讥的吋间上的比较。例题一：ZJU2008InvitationCards［题目大意］在有向加权图中G(V,E),邮局要从起点S向其他n个节点发送邮件，于是派出n个邮递员，分别到达其他n个地点发送，然后冋到起
15、点S,求出所有邮递员所经过的总路程的最小值。擞据范围］1<=P,Q<=1000000cP衣示节点数目，Q表示边的个数。［题目分析］这道题算法很简单，即
