算法合集之《猜想及其应用》.ppt

《算法合集之《猜想及其应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、猜想及其应用内容简介前言类比猜想与熟悉的问题类比巨人与鬼青蛙的烦恼与特殊的问题类比圆圈点略归纳猜想青蛙过河（略）排列问题结语猜想是一种主观不充分似真推理。它建立在观察、分析、联想、归纳的基础上前言提出猜想以小规模数据验证猜想证明结论YN修改猜想解决问题由此可见，猜想是在深入分析问题的基础上，不懈探索、反复修正的过程。决不可能一蹴而就。提出猜想是整个过程的核心和重点。类比猜想、归纳猜想类比猜想事物A事物B性质a性质a性质b性质c性质a’性质b’性质c’性质d性质d’类比、猜想引例：巨人与鬼（1）问题描述平面上有n个巨人和n个鬼（1<=n<=50）。每个巨人都有新式激光

2、武器，可以对鬼进行直线攻击。然而这种武器有一种很大的弱点：两个不同武器发出的激光不能交叉，否则就有爆炸的危险。已知任意三个个体（包括巨人和鬼）都不在一条直线上，每个巨人负责攻击一个鬼。当然激光不能交叉。现在的问题是：请你求出任意一种攻击的方案。（即确定哪个巨人攻击哪个鬼）引例：巨人与鬼（2）试题中是实际上是要确定巨人与鬼之间的一一对应关系——这使我们很自然的联想到了匹配。引例：巨人与鬼（3）构图：将巨人、鬼都抽象成为顶点。巨人组成的点集记为X，鬼组成的点集记为Y。在所有的x∈X、y∈Y之间连一条边。任务：1、找到一个完备匹配。2、匹配边不相交。假设有相交边：OABCD方

3、案1ABCD方案2OA+OB>AB，OC+OD>CDAD+CB>AB+CD方案1的“匹配边长度总和”>方案2的“匹配边长度总和”引例：巨人与鬼（4）方案2与方案１，“匹配边的长度总和”减小了。故而：每一个“包含相交边的完备匹配”都能够转换成为“匹配边长度总和”更小的一个完备匹配——换句话说，“匹配边长度总和”最小的完备匹配一定不包含相交边！而我们要求的，正是一个不包含相交边的完备匹配！建立二分图最佳匹配模型：每条边的权值设为它两端顶点的欧几里德距离。用匈牙利算法求最佳匹配模型。问题解决了。引例小结本题二分图中的顶点具有特殊性：每个顶点都对应于平面上的一点。因此，顶点与顶

4、点之间不仅有逻辑关系，还有几何直观关系。正是由于充分利用了“几何直观”这一隐蔽关系才使得算法模型豁然开朗。例１：青蛙的烦恼(1)问题描述池塘里有n片荷叶（1<=n<=1000），它们正好形成一个凸多边形。我们按照顺时针方向将这n片荷叶顺次编号为1,2,…,n。有一只小青蛙站在一号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到另外任意一片荷叶上）。同时，它又希望跳过的总距离最短。请你编程，帮助小青蛙设计一条路线构图：首先将每片荷叶抽象成一个顶点，在任意两个顶点x,y之间连一条边，边的权值设为顶点x与y的欧几里德距离。模型：以1为起点的最短Hamilton链。

5、例１：青蛙的烦恼(2)经过观察分析，发现构造的图：是一个完全图。边的权值等于它两端顶点的欧几里德距离。图中的每个顶点对应于平面上的一点。这些性质和【引例】是多么相似啊！（这是表面上的类似）由于图中的每个顶点对应于平面上的一点，所以顶点之间不仅存在着由“边”连接的逻辑关系，还存在着特殊的“几何直观”关系。利用好这个隐含的条件是解题的关键——这正与【引例】的基本特性不谋而合！（这是本质上的类似）解决【引例】时利用这个特性可以将“匹配边总长度”不断的缩短；而本题所求的问题也是一个最短路问题。例１：青蛙的烦恼(3)根据两题诸多相似之处，我们猜测：证明设从1出发，首先到达顶点A(

6、2的两侧。不失一般性，设从i出发经过若干步到左侧的顶点B，再到右侧的顶点C，如下图所示：C1AB实线表示一步到达；虚线表示多步到达猜想B最短Hamilton链中不存在相交的边。例１：青蛙的烦恼(4)我们可以做这样的变换：1AB实线表示一步到达；虚线表示多步到达1AB实线表示一步到达；虚线表示多步到达CC变换后的链的长度，显然比变换前的要短。所以变换前的方案必然不是最优解。因此最优Hamilton链肯定不存在相交边。例１：青蛙的烦恼(5)…………12n以n为起点

7、，遍历{2..n}集合中的顶点一次且仅一次以2为起点，遍历{2..n}集合中的顶点一次且仅一次…………12n…………12n从1出发，遍历{1..n}中的顶点一次且仅一次，第一步必然是到2、或者n例１：青蛙的烦恼(6)设f[s,L,0]表示从s出发，遍历{s..s+L-1}中的顶点一次且仅一次的最短距离；f[s,L,1]表示从s+L-1出发，遍历{s..s+L-1}中的顶点一次且仅一次的最短距离。则：f[s,L,0]=min{dis(s,s+1)+f(s+1,L-1,0),dis(s,s+L-1)+f(s+1,L-1,1)}f[s,L,1]