解题中的猜想

集训队文稿—猜想及其应用猜想及其应用集训队文稿—猜想及其应用内容简介前言类比猜想与熟悉的问题类比巨人与鬼青蛙的烦恼与特殊的问题类比圆圈点（略）归纳猜想青蛙过河（略）排列问题结语集训队文稿—猜想及其应用猜想是一种主观不充分似真推理。它建立在观察、分析、联想、归纳的基础上前言提出猜想以小规模数据验证猜想证明结论YN修改猜想解决问题由此可见，猜想是在深入分析问题的基础上，不懈探索、反复修正的过程。决不可能一蹴而就。提出猜想是整个过程的核心和重点。类比猜想、归纳猜想集训队文稿—猜想及其应用类比猜想事物A事物B性质a性质a性质b性质c性质a’性质b’性质c’性质d性质d’类比、猜想集训队文稿—猜想及其应用引例：巨人与鬼（1）问题描述平面上有n个巨人和n个鬼（1=n=50）。每个巨人都有新式激光武器，可以对鬼进行直线攻击。然而这种武器有一种很大的弱点：两个不同武器发出的激光不能交叉，否则就有爆炸的危险。已知任意三个个体（包括巨人和鬼）都不在一条直线上，每个巨人负责攻击一个鬼。当然激光不能交叉。现在的问题是：请你求出任意一种攻击的方案。（即确定哪个巨人攻击哪个鬼）集训队文稿—猜想及其应用引例：巨人与鬼（2）试题中是实际上是要确定巨人与鬼之间的一一对应关系——这使我们很自然的联想到了匹配。集训队文稿—猜想及其应用引例：巨人与鬼（3）构图：将巨人、鬼都抽象成为顶点。巨人组成的点集记为X，鬼组成的点集记为Y。在所有的x∈X、y∈Y之间连一条边。任务：1、找到一个完备匹配。2、匹配边不相交。假设有相交边：OABCD方案1ABCD方案2OA+OBAB，OC+ODCDAD+CBAB+CD方案1的“匹配边长度总和”方案2的“匹配边长度总和”集训队文稿—猜想及其应用引例：巨人与鬼（4）方案2与方案１，“匹配边的长度总和”减小了。故而：每一个“包含相交边的完备匹配”都能够转换成为“匹配边长度总和”更小的一个完备匹配——换句话说，“匹配边长度总和”最小的完备匹配一定不包含相交边！而我们要求的，正是一个不包含相交边的完备匹配！建立二分图最佳匹配模型：每条边的权值设为它两端顶点的欧几里德距离。用匈牙利算法求最佳匹配模型。问题解决了。集训队文稿—猜想及其应用引例小结本题二分图中的顶点具有特殊性：每个顶点都对应于平面上的一点。因此，顶点与顶点之间不仅有逻辑关系，还有几何直观关系。正是由于充分利用了“几何直观”这一隐蔽关系才使得算法模型豁然开朗。集训队文稿—猜想及其应用例１：青蛙的烦恼(1)问题描述池塘里有n片荷叶（1=n=1000），它们正好形成一个凸多边形。我们按照顺时针方向将这n片荷叶顺次编号为1,2,…,n。有一只小青蛙站在一号荷叶上，它想跳过每片荷叶一次且仅一次（它可以从所站的荷叶跳到另外任意一片荷叶上）。同时，它又希望跳过的总距离最短。请你编程，帮助小青蛙设计一条路线构图：首先将每片荷叶抽象成一个顶点，在任意两个顶点x,y之间连一条边，边的权值设为顶点x与y的欧几里德距离。模型：以1为起点的最短Hamilton链。集训队文稿—猜想及其应用例１：青蛙的烦恼(2)经过观察分析，发现构造的图：是一个完全图。边的权值等于它两端顶点的欧几里德距离。图中的每个顶点对应于平面上的一点。这些性质和【引例】是多么相似啊！（这是表面上的类似）由于图中的每个顶点对应于平面上的一点，所以顶点之间不仅存在着由“边”连接的逻辑关系，还存在着特殊的“几何直观”关系。利用好这个隐含的条件是解题的关键——这正与【引例】的基本特性不谋而合！（这是本质上的类似）解决【引例】时利用这个特性可以将“匹配边总长度”不断的缩短；而本题所求的问题也是一个最短路问题。集训队文稿—猜想及其应用例１：青蛙的烦恼(3)根据两题诸多相似之处，我们猜测：证明设从1出发，首先到达顶点A(2An)。由于所有点在一个凸包上、2An，所以除1、i以外的顶点必然被分作两个部分，分别位于线段1,A的两侧。不失一般性，设从i出发经过若干步到左侧的顶点B，再到右侧的顶点C，如下图所示：C1AB实线表示一步到达；虚线表示多步到达猜想B最短Hamilton链中不存在相交的边。集训队文稿—猜想及其应用例１：青蛙的烦恼(4)我们可以做这样的变换：1AB实线表示一步到达；虚线表示多步到达1AB实线表示一步到达；虚线表示多步到达CC变换后的链的长度，显然比变换前的要短。所以变换前的方案必然不是最优解。因此最优Hamilton链肯定不存在相交边。集训队文稿—猜想及其应用例１：青蛙的烦恼(5)…………12n以n为起点，遍历{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]=min{dis(s+L-1,s+L-2)+f(s,L–1,1)dis(s+L-1,s)+f(s,L-1,0)}f[s,1,0]=0,f[s,1,1]=0求：f[1,n,0]集训队文稿—猜想及其应用“与熟悉的问题类比”小结深入、透彻的分析模型。观察、联想。问题A算法A解决问题B类似算法B解决猜想与熟悉的问题进行类比的基本步骤是：分析：分析问题的特征抽象出模型。联想：与熟悉的，拥有类似特征、模型的问题类比。比较：确定类比对象后将两者比较，分析异同。猜想：根据已知问题猜想新问题的解决方法。集训队文稿—猜想及其应用归纳猜想（1）归纳，是指通过对特例的分析来引出普遍结论的一种推理形式前提归纳结论若干已知的个别、特殊事实普遍性的陈述、判断，猜想观察、分析、联想、概括的过程主观的、不充分、似真推理必须经过严格的逻辑论证集训队文稿—猜想及其应用归纳猜想（2）归纳猜想的一般步骤：列举。将一些特殊的、简单的、小规模的数据列举出来。（这一步可以用手推，或者编写简单的搜索小程序）观察。观察列举数据的规律。猜想。根据部分数据猜想一般结论。证明。证明猜想的正确性。（一般采用数学归纳法）集训队文稿—猜想及其应用例4：排列问题（1）问题描述在整数1，2，……，N的排列中，有些排列满足下面一个性质A：该排列中除了最后一个整数以外的每一个整数后面都跟有（不必直接紧跟）一个同它相差为1的整数。例如：N=4，排列1432是具有性质A的，而2431则不满足。设有一个N个数的排列，已知其中P(P=N)个位置上的数，求共有多少个这样的排列——在P个位置上具有已知的数，且具有上述性质A。例如：N=4，且已知第1位、第2位分别是1和4，则1432，1423就是这样的两个排列。集训队文稿—猜想及其应用例4：排列问题（2）当n=5时，有16组满足要求的序列（搜索出的解）：12345123541253412543152341524315423154325123451243514235143254123541325431254321观察发现：任何一个排列的后k位（1=k=n）是若干连续整数组成的集合集训队文稿—猜想及其应用例4：排列问题（3）任何一个排列的后k位（1=k=n）是若干连续整数组成的集合51243后5位：51243{1..5}后4位：1243{1..4}后3位：243{2..4}后2位：43{3..4}后1位：3{3}集训队文稿—猜想及其应用例4：排列问题（4）猜想1任何一个排列的后k位（1=k=n）是若干连续整数组成的集合。证明约定序列的第i位用v[i]表示。设序列后x位（x=1）是若干连续整数，这些整数构成集合{s..t}。那么倒数第x+1位上的数v[n-x+1]必然等于p-1或者p+1（p∈{s..t}）。显然v[n-x+1]∪{s..t}={s-1..t}或者{s..t+1}，还是若干连续整数。猜想2如果一个排列的后k位（1=k=n）是若干连续整数组成的集合，则这个排列符合题目要求。证明约定该序列的第i位用v[i]表示。设{v[n],v[n-1],…,v[n-k+1]}={s..t}。因为{v[n-1],…,v[n-k+1]}也是若干连续整数的集合，所以v[n]=s或t。如果v[n]=s，那么必有：s+1∈{v[n-1],…,v[n-k+1]}如果v[n]=t，那么必有：t-1∈{v[n-1],…,v[n-k+1]}即这是一个满足要求的序列。集训队文稿—猜想及其应用例4：排列问题（5）因此问题转化为：求后k位（1=k=n）是若干连续整数组成的集合的排列总数（由1，2，……，N组成）。设g[s,r]表示满足下面条件的序列C的总数：C由集合[s..s+r-1]中的数组成，且后k位（1=k=r）是若干连续整数组成的集合。如果原问题中倒数第i个位置上的数已经确定为x（1=i=r），那么C的倒数第i个位置上的数也要是x。集训队文稿—猜想及其应用例4：排列问题（6）g[s+1,r-1]如果倒数第r位确定为sg[s,r-1]如果倒数第r位确定为s+r-1g[s,r]=g[s,r-1]+g[s+1,r-1]如果倒数第r位不确定0其他情况g[s,1]=1求：g[1,n]集训队文稿—猜想及其应用例４小结题目给定的条件比较复杂，很不便于转化利用，极容易诱使选手走上“搜索”的“不归路”。本题解决的关键在于通过对特例的观察，归纳出两个大胆的猜想，将复杂、不利于利用的条件，变换到一个我们熟悉的形式，为动态规划模型的建立打开了通道。集训队文稿—猜想及其应用结语其实我们解题时都在不知不觉的猜想——猜想问题的性质；猜想模型的形式；猜想算法的内容……猜想是从已知向未知探索的重要途径。猜想≠偶然+运气。猜想是建立在观察、分析、联想、归纳基础上的一种主观不充分似真推理。它是观察能力、概括能力、联想能力、创新能力的综合体现。猜想的水平，最能反映一个人思维品质的高低。根据得到猜想方式的不同，又可以分为：类比猜想和归纳猜想但无论那种方法都离不开观察、分析和实践。可以说：观察是猜想的血液——贯穿于整个猜想过程之中；分析是猜想的灵魂——提出猜想的前提和基础；实践是猜想的骨架——支撑猜想的基石，脱离了实际，猜想毫无意义。