搜索算法2.doc

枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件:⑴可预先确定每个状态的元素个数n;⑵状态元素a1,a2,…,an的可能值为一个连续的值域。设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k,ai1≤ai≤aik,……,an1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1,…,ai,…,an)满足检验条件then输出问题的解;枚举法的优点:⑴由于枚举算法一般是现实生活中问题的“直译”,因此比较直观,易于理解;⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明。枚举法的缺点:枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。一、“直译”的枚举算法例题:跳远,在水平面上整齐的放着n个正三角形,相邻两个三角形的底边之间无空隙,如左图所示。一个小孩子想站在某个三角形i的顶端,跳到三角形j的顶端上(i<j)。他总是朝着斜向45度的方向起跳,且初始水平速度v不超过一个给定值v0。在跳跃过程中,由于受到重力作用(忽略空气阻力),小孩子将沿着抛物线行进,水平运动方程为x=x0+vt,竖直运动方程为y=y0+vt–,运动轨迹是一条上凸的抛物线。取g=,(x0,y0)是起跳点坐标。请编程求出他从每个位置起跳能到达的最远三角形的编号。注意:跳跃过程中不许碰到非起点和终点的其他三角形。输入:第一行为两个正整数n,v0(3≤n≤10,1≤v0≤100),表示三角形的个数和最大水平初速度。第二行有n个正整数li(1≤li≤20),表示从左到右各个三角形的边长。输出:输出仅一行,包括n-1个数,表示从三角形1,2,3…n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形,相应的数为0。状态:起跳点i和i点后的点j。每个状态元素的取值范围:1≤i≤n-1,i+1≤j≤n约束条件的分析:判断小孩能否从i点跳到j点的方法如下:设起点和终点间的水平距离为l、垂直距离为h。则由物理知识(已在题目中给出)有:t=l/vh=vt–5t2=l–5*。因此,v=sqrt(5*l*l/(l-h))。当然,这个v不一定符合要求,它需要满足两个条件。⑴它不能大于极限速度v0,即必须有v≤v0⑵跳跃过程中不得碰到其他三角形。如何判断顶点k是否在抛物线下呢?我们可以算出到达时间t0=dx/v(其中dx为起点到顶点k的水平坐标增量),然后算出该时刻的竖直坐标增量vt0–。如果此增量大于起点到顶点k的竖直坐标增量,则抛物线在上方。只有起点和终点之间任何一个三角形的顶点不在抛物线下方,则跳远不能完成。我们在枚举过程中不断将小孩所能跳到的点j调整为best。枚举结束后,best即为试题要求的最远点。varlen:array[1..20]oflongint;x,y:array[1..20]ofdouble;{三角