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

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

1、猜想及其应用【摘要】猜想是重要的解题策略，对培养人的综合思维能力大有好处。本文第一部分介绍了猜想的基本要求和实现步骤，提出了两种重要的得到猜想的方法：类比和归纳。第二、三部分分别介绍了类比、归纳的基本性质、定义，以及解题的一般步骤。每一部分都通过若干道题目实际说明猜想在信息学竞赛中的应用最后总结全文，对猜想的方法、定义、分类、重要性等做了全面阐述。【关键字】猜想类比归纳【正文】一、引言猜想，是解决问题最基本、最重要的方法，是完成从已知世界到未知世界探索的有力工具。在信息学竞赛中，随着试题的隐蔽性越来越高，“猜想”这一研究手段也扮演着越来越

2、重要的角色。猜想不是胡猜乱想，必须综合分析条件作出“言之成理”的推测，然后在猜测的引导下进行“持之有据”的论证。因此猜想绝不仅仅是运气或者投机，正如一个小学生很难提出费马大猜想（现在已经证明了），不经过深入的观察、分析我们也不可能提出任何有价值的猜想。进行猜想的基本步骤是：提出猜想以小规模数据验证猜想证明结论YN修改猜想解决问题由此可见，猜想是在深入分析问题的基础上，不懈探索、反复修正的过程。决不可能一蹴而就。“提出猜想”是整个过程的核心。得到猜想的方法主要有类比和归纳。一、类比猜想所谓类比，就是由两个对象的某些相同或相似的性质，推断它们

3、在其他性质上也有可能相同或相似的一种推理形式。形式性的表示为：事物A具有性质a,b,c,d，事物B具有与之相应的类似性质a’,b’,c’，从而猜想B也有与d对应的类似性质d’。类比是一种主观的不充分的似真推理，因此，要确认由类比而得的猜想的正确性，还须经过严格的逻辑论证。§2.1与熟悉的问题类比若问题A（熟悉）已经解决，问题B（陌生）在形式、结构或性质方面与A类似，那么可以猜想：解决B的方法类似于解决A的方法。形象的表示为：问题A算法A解决问题B类似算法B解决猜想与熟悉的问题进行类比的基本步骤是：1、分析。分析问题的特征，抽象出模型。2、

4、联想。与熟悉的，拥有类似特征、模型的问题类比。3、比较。确定类比对象后将两者比较，分析异同。4、猜想。根据已知问题猜想新问题的解决方法。【引例】巨人与鬼问题描述平面上有n个巨人和n个鬼（1<=n<=50）。每个巨人都有新式激光武器，可以对鬼进行直线攻击。然而这种武器有一种很大的弱点：两个不同武器发出的激光不能交叉，否则就有爆炸的危险。已知任意三个个体（包括巨人和鬼）都不在一条直线上，每个巨人负责攻击一个鬼。当然激光不能交叉。现在的问题是：请你求出任意一种攻击的方案。（即确定哪个巨人攻击哪个鬼）输入l输入文件的第一行只有一个整数n。l接下来

5、n行每行两个整数x,y，表示巨人的坐标。l接下来n行每行两个整数x,y，表示鬼的坐标。输出l输出文件有n行，每i行包含一个整数p，表示第i个巨人攻击第p个鬼。分析试题中是实际上是要确定巨人与鬼之间的一一对应关系——这使我们很自然的联想到了匹配。将巨人、鬼都抽象成为顶点。巨人组成的点集记为X，鬼组成的点集记为Y。在所有的x∈X、y∈Y之间连一条边，接下来用匈牙利算法求二分图的完备匹配——然而题目还有一个特别的条件：任意两条匹配边不能相交。所以简单的匹配还不行。我们不妨令两条边相交，研究其特性：ABCDOABCD如果A攻击D，C攻击B（如上图

6、左所示），则匹配边会相交。一种自然的想法是将其变换到右图所示的形式。观察图形特点，发现：OA+OB>AB，OC+OD>CDAD+BC>AB+CD新的匹配方案与老的匹配方案相比，“匹配边的长度总和”减小了。故而，每一个包含相交边的完备匹配都能够转换成为“匹配边长度总和”更小的一个完备匹配——换句话说，“匹配边长度总和”最小的完备匹配一定不包含相交边！将原来的二分图完备匹配模型转换成二分图最佳匹配模型：每条边的权值设为它两端顶点的欧几里德距离。问题解决了。小结本题二分图中的顶点具有特殊性：每个顶点都对应于平面上的一点。因此，顶点与顶点之间不仅

7、有逻辑关系，还有几何直观关系。正是由于充分利用了“几何直观”这一隐蔽关系才使得算法模型豁然开朗。【例1】青蛙的烦恼问题描述池塘里有n片荷叶（1<=n<=1000），它们正好形成一个凸多边形。我们按照顺时针方向将这n片荷叶顺次编号为1,2,…,n。有一只小青蛙站在一号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到另外任意一片荷叶上）。同时，它又希望跳过的总距离最短。请你编程，帮助小青蛙设计一条路线。输入l输入文件第一行有一个整数n。l接下来n行每行两个整数x,y，表示第i片荷叶的坐标。输出l输出文件只有一个整数，即最短总距离。

8、分析这是一道难题。首先将每片荷叶抽象成一个顶点，在任意两个顶点x,y之间连一条边，边的权值设为顶点x与y的欧几里德距离。容易看出，题目的本质是求一条从1出发的Hamilton链——这是一道经典