论文--数与图的完美结合——浅析差分约束系统

《论文--数与图的完美结合——浅析差分约束系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数与图的完美结合-------浅析差分约束系统[摘要]在面对多种多样的问题时，我们经常会碰到这样的情况：往往我们能够根据题目题面意思来建立一些简单的模型，但却面对这些模型无从下手。这时我们应该意识到，也许能够将这种模型与其他的模型之间搭起一座桥梁，使我们能够用更简单直接的方式解决它。这里我们介绍一种方法，它很好地将某些特殊的不等式组与图相联结，让复杂的问题简单化，将难处理的问题用我们所熟知的方法去解决，它便是差分约束系统。这里我们着重介绍差分约束系统的原理和其需要掌握的bellman-ford算法。然后通过z

2、ju1508和zju1420两道题目解析差分约束系统在信息学题目中的应用，并逐渐归纳解决这类问题的思考方向。[目录]◆关键字·······························································································【2】◆Bellman-ford算法············································································【2】◇算法

3、简单介绍·················································································【2】◇算法具体流程················································································【2】◇例题一ZJU2008····································································

4、··········【4】第22页/共22页◆差分约束系统····················································································【5】◇例题二ZJU1508··············································································【5】◇线性程序设计··········································

5、·······································【7】◇差分约束系统·················································································【7】◇例题三ZJU1420············································································【8】◆结语·······························

6、····································································【9】◆附录···································································································【9】[关键字]差分约束系统、不等式、单元最短路径、转化[正文]在分析差分约束系统之前，我们首先介绍一个解决单元最短路径问题的BellmanFord算法，它的应用十分广

7、泛，在差分约束系统中更充当着重要的角色。Bellman-ford算法第22页/共22页算法简单介绍这个算法能在更一般的情况下解决最短路的问题。何谓一般，一般在该算法下边的权值可以为负，可以运用该算法求有向图的单元最长路径或者最短路径。我们这里仅以最短路径为例。Bellmanford类似于Dijkstra算法，对每一个节点vV，逐步减小从起点s到终点v最短路的估计量dist[v]直到其达到真正的最短路径值mindist[v]。Bellman-ford算法同时返回一个布尔值，如果不存在从源结点可达的负权回路，算法

8、返回布尔值TRUE，反之返回FALSE。算法具体流程1．枚举每条边(u,v)E（G）。2．对枚举到的边进行一次更新操作。3．回到步骤1，此过程重复n-1次，以确定没有更可以优化的情况。4．枚举每条边（u，v）若仍然存在可以更新的边，则说明有向图中出现了负权回路，于是返回布尔值FALSE。5．返回布尔值TRUE。注：这里的更新操作是一种松弛技术，以单元最短路径为例这个操作就是保证dist[v]<=di