搜索法C程序设计.ppt

1、程序设计实践,程序设计方法之 搜索,搜索的本质,一句话的解释：在所有的情况中寻找符合要求的情况 类比的说法：搜索即一种特殊枚举 辨别：搜索是有选择的、有一定效率的，枚举是无选择的、低效率的,题目引入：傻大木买军火,要求： 1. 傻大木共购买了三种武器：2万美元一个的木瓜手雷，6万美元一支的啊卡卡47型冲锋枪和1万美元一个的大杀器。 2. 三种武器的数量各不相同。 3. 傻大木购买的木瓜手雷的个数在大杀器个数和冲锋枪支数之间。 4. 木瓜手雷必须成对购买。 5. 为了图吉利，傻大木购买的大杀器个数的尾数是8（如8，48等）。 6. 如果冲锋枪的支数是一位数，那么木瓜手雷的个数一定是两位数。（但如

2、果冲锋枪的支数不是一位数，那么木瓜手雷的个数可能是任何数。） 7. 傻大木的n万元可能恰好花完了，也可能没花完，但一定花了九成以上。,题目的简单思路,for size_bomb = min_possible to max_possible for size_kaka = min_possible to max_possible for size_bigkiller = min_possible to max_possible If Accept( size_bomb , size_kaka , size_bigkiller) Output( size_bomb , size_kaka , si

3、ze_bigkiller ) ,总结基本思路,枚举所有可能的情况，再在所有可能的情况中寻找符合要求的情况 同时我们可以发现，这道题目的变量数目是3（炸弹、咔咔、大杀器），是一个常量，也就是说，三层循环就可以枚举出所有可能的情况，那么对于变量数目为一个变量n的情况呢？ 不妨看下一道题目,深入：计算正行列式项,由键盘输入n，和一个n*n的矩阵，输出所有计算行列式时要用到的正项之和。 For example : Input: 2 1 2 3 4 Output: 4,解题思路,生成所有排列，即确定n个变量：j1、j2jn的值 对于每一组j1jn，计算对应逆序数 用求得的逆序数结合输入的矩阵计算出该项的

4、值t 若t0加到和sum中 若t0不做任何处理 最后输出sum,总结大概的代码：,for j1 = 1 to n do for j2 = 1 to n do for jn = 1 to n do if 任意两个ji，jk互不相等 t = calc( j1 , j2 jn) /计算逆序数 t = a1j1 * a2j2 * * anjn if ( t 0 ) sum = sum + t ; cout sum ;,我们发现：,要使用n层循环，也就是说，循环的个数是动态的 如何解决这个问题？ 使用递归的方法，n层循环转化成n层递归 具体方法，看如下的程序,bool usedMAXN ; / 用来实现

5、j1.jn互不相同 int jMAXN ; int t ; int sum ; void Search( int k ) if ( k n ) t = 1; / 对于储存在数组j中的n个变量计算逆序数 int i ; for ( i = 1 ; i 0) sum += t ; / sum = sum + t return； for ( jk = 1 ; jk = n ; jk + ) if ( !usedjk ) / 判断jk是否能取 usedjk = true; Search( k + 1 ); usedjk = false; ,解决了这个问题我们就可以给出搜索问题的模版程序,int jMA

6、XN / MAXN是可能的参数个数 void Search( int k ) if ( k n ) / k个参数的值已经确定了，验证是否符合条件 if ( Accpet() ) / 如果满足条件 . . / 做相应操作 return / 退出 / 对于第k个变量jk,枚举所有可能的值 for jk = each possible case if ( available( jk ) ) / 如果jk可以取这个值 . /完成相应操作，譬如usedjk = true; Search( k + 1 ); /搜索下一个变量jk+1 . /完成相应操作，譬如usedjk = false; ,解决实际问题，

7、案例1：寻宝,有一个n*m的棋盘，如图所示，骑士X最开始站在方格(1,1)中，目的地是方格(n,m)。他的每次都只能移动到上、左、右相邻的任意一个方格。每个方格中都有一定数量的宝物k（可能为负），对于任意方格，骑士X能且只能经过最多1次（因此从(1,1)点出发后就不能再回到该点了）。 你的任务是，帮助骑士X从(1,1)点移动到(n,m)点，且使得他获得的宝物数最多。,按照一般的思路进行分析,枚举所有的情况：即枚举所有可能的路径 Search的参数由两个变量构成：int x , y Search函数枚举在(x,y)点处可能的走法，即：上、左、右 边界条件为(x=n) /存储3种行走方式对应的坐标

8、变化值 int dataMAXN+1MAXM+1; /储存(x,y)中的宝藏价值 int max; bool usedMAXN+1MAXM+1; /用来辅助判断(x,y)是否走到过 void Search( int x , int y ，int sum)/ 三个参数表示状态 if ( x = n ) /搜索这个格子 ,案例2：滑雪,小袁非常喜欢滑雪， 因为滑雪很刺激。为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。小袁想知道在某个区域中最长的一个滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。如下： 一个人可以从某个点滑向上下左右相邻四个

9、点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-.-3-2-1更长。事实上，这是最长的一条。 你的任务就是找到最长的一条滑坡，并且将滑坡的长度输出。 滑坡的长度定义为经过点的个数，例如滑坡24-17-16-1的长度是4。,继续按一般的思路分析,由于这个题目中间起点有多种可能：(1,1)到(n,m)都有可能，故要考虑从多个起点开始进行搜索 对每个点枚举可能的情况：上下左右四个方向 如果从某个起点(x0,y0)走到某个点(x,y)时，发现经过的路径长度length max，则更新max 最后输出max的值,bool avail( int x1

10、 , int y1 , int y1 , int y2 ); /avail函数判断是否(x1,y1)的高度大于(x2,y2)的高度 int max ; /记录最大值 void Search( int x , int y , int length ) if ( length max ) max = length ; /如果到达(x,y)点时走过的路径已经大于max, 更新max的值 if ( avail( x , y , x - 1 , y ) ) Search( x - 1 , y , length + 1 ) ; if ( avail( x , y , x + 1 , y ) ) Searc

11、h( x + 1 , y , length + 1 ) ; if ( avail( x , y , x , y - 1 ) ) Search( x , y - 1 , length + 1 ) ; if ( avail( x , y , x , y + 1 ) ) Search( x , y + 1 , length + 1 ) ; /分别判断(x,y)的四个方向是否可走，如果可走，搜索这个方向 ,int main() . int i , j ; max = 1; for ( i = 1 ; i = n ; i + ) for ( j = 1 ; j = n ; j + ) Search( i

12、 , j , 1 ); /分别把每个点作为起点展开搜索 cout max ; . ,main函数的处理：,最后，我们总结搜索题的一般特性,题目涉及的情况多 规律不明显，无法推到出题目的规律或者找到一个绝对可行的数学公式 一般要求是求出符合条件的解，求最大、最小值，求某种路径 符合以上特征的题目是多的，大家相信已经有一些感受：搜索是一种相当重要的算法,解决搜索题目的一般方法#1,分析题目中的所有可能情况，即搜索的对象（如傻大木为所有军火组合、行列式那道题目为所有的1n组合、藏宝是所有的(1,1)到(n,m)的路径、滑雪是所有的递减型滑道） 分析题目搜索的目标（即傻大木中符合条件的军火搭配、行列式

13、中的正项、藏宝中的最大价值路径、滑雪中的最长滑道）,解决搜索题目的一般方法#2,分析为了实现搜索目的，而要用的表示状态的方法 具体而言，即对应的函数的头部： 行列式：void search( int k ) 寻宝：void search( int x , int y , int sum ) 滑雪：void search( int x , int y , int length ) 要保证参数变量准确、完备的表示出每个状态的情况,解决搜索题目的一般方法#3,确定每个状态中状态转移的方式 即搜索中的主程序部分 void Search( int x , int y , int length ) if ( length max ) max = length ; if ( avail( x , y , x - 1 , y ) ) Search( x - 1 , y , length + 1 ) ; if ( avail( x , y , x + 1 , y ) ) Search( x + 1 , y , length + 1 ) ; if ( avail( x , y , x , y - 1 ) ) Search( x , y - 1 , length + 1 )