滑雪问题

滑雪问题滑雪问题描述Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡（滑坡的长度由滑过点的个数来计算）。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子12345161718196152425207142322218131211109一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，例如一条可滑行的滑坡为24-17-16-1。问题分析•在最长路径的情况下，Ai-Ai-1------A1，它的子结构Ai-1------A0,也是最优的。所以搜索中如果遇到已经路过的节点，看是否路程长度增大。若是，则该路径有可能成为解，否则直接排出可能性。所以只要保证，每个节点都经历过，便能求得解。•因为不用求路径，所以每个点只用一个数字就可以记录改点是否经过，和该点的最长路程。每次DFS前找到点最高且没有经过的节点开始搜索。最后找到记录里最大的值，便是解。简化题目•对于所给出的矩阵找出一条最长的递减链,•满足链中相邻的两个元素间都是在矩阵中相邻的在这里我们用两种算法来解决该滑雪问题：（1）动态规划算法（2）穷举搜索算法动态规划算法基本思想•动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。子问题的重叠性动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划解题思路•定义dis_sk[i][j]表示从点(i,j)为起点滑行的最大长度。滑行时，选择周围可以滑行的且dis_sk值最大的方向滑行。如果(i,j)的四个相邻元素都存在的话，则可以得到如下递归式：•dis_sk[i][j]=max{dis_sk[i-1][j],dis_sk[i][j-1],dis_sk[i+1][j],dis_sk[i][j+1]}+1•通过递归地计算•dis_sk[i][j-1],•dis_sk[i][j+1],•dis_sk[i-1][j]•dis_sk[i+1][j]•的值，动态规划解题思路找中四个中最大的一个，即是下一步滑行的位置，以此递归，直到不能继续滑行时返回。求解过程中，每求解到一个点的最大滑行长度则保存在数组dis_sk[i][j]中，因此不会重复求解同一个点的最大滑行长度。•用两重循环搜索整个矩阵中dis_sk[i][j]最大的点，dis_sk[i][j]就是要求解的最长区域的长度。•那么我们很容易写出递归的：•intdis(inti,intj)•{for(i,j上侧，下侧，左侧，右侧)if(该位置没有越界)•{if(顺着该侧可以往下滑)如果该侧位置可以滑行的距离(递归调用dis函数)大于dis_sk[i][j]，则把dis_sk[i][j]改成该距离+1}}•把这个递归改成动态规划很容易，只要在开始判断一下if(dis_sk[i][j])returndis_sk[i][j];//dis_sk[i][j]开始为0•定义的变量如下：•inth[101][101];//输入的高度值•intdis_sk[101][101];//记录了每个点可以滑行的最大距离•intdx[]={-1,1,0,0};//为了方便上下左右侧的滑行的最大距离而使用的方便数组•intdy[]={0,0,-1,1};•intr,c;//输入的行和列•一个用来判断是否越界的辅助函数：•boolin_bound(inti,intj){•returni=0&&ir&&j=0&&jc;•}•动态规划实现的从i,j下滑最大距离：•intdis(inti,intj){•inttemp;•if(dis_sk[i][j])//如果已经求出来了，直接返回•returndis_sk[i][j];•for(intk=0;k4;k++){•if(in_bound(i+dx[k],j+dy[k])){//如果没有越界•if(h[i][j]h[i+dx[k]][j+dy[k]]){//如果顺着该侧可以滑•temp=dis(i+dx[k],j+dy[k]);//递归求dis(i+dx[k],j+dy[k])，并保存在临时变量temp中•dis_sk[i][j]=dis_sk[i][j]temp?dis_sk[i][j]:temp+1;//如果dis_sk[i][j]比temp小，则取temp+1•}•}•}•returndis_sk[i][j];•}最后是main函数，取dis(i,j)的最大者就是所求的最长区域的长度：intmain(){•intmax_dis=0;•inttemp;•inti,j;•cinrc;•for(i=0;ir;i++)•for(j=0;jc;j++){•cinh[i][j];•dis_sk[i][j]=0;•}••for(i=0;ir;i++)•for(j=0;jc;j++){•temp=dis(i,j);•max_dis=max_distemp?max_dis:temp;•}••coutmax_dis+1endl;•return0;•}用穷举法解决滑雪问题•什么是穷举法？•它将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。•适用穷举法解决问题特征•1.有明显穷举范围，穷举规则•2.一时找不出解决问题的更好途径时可用穷举法•例如此二维数组，用枚举法列出以各个点为起点的坡长：•12345•161718196•152425207•142322218•131211109•第一行各个点：•起点：点数：•11•2-12•3-2-13•4-3-2-14•5-4-3-2-15第二行各个点•起点：点数：•16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-116•16-12••17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-117•17-2-13•17-16-13•18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-118•18-3-2-14•18-17-2-14•18-17-16-14•19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-119•19-4-3-2-15•19-18-3-2-15•19-18-17-2-15•19-18-17-16-15••6-5-4-3-2-16•第三行各个点•起点：点数：•15-14-13-12-11-10-9-8-7-6-5-4-3-2-115•24-23-22-21-20-19-18-17-16-15-14-•13-12-11-10-9-8-7-6-5-4-3-2-124•24-23-14-13-12-11-10-9-8-7-6-5-4-3-2-116•24-23-12-11-10-9-8-7-6-5-4-3-2-114•24-23-22-11-10-9-8-7-6-5-4-3-2-114•24-23-22-21-10-9-8-7-6-5-4-3-2-114•24-23-22-21-8-7-6-5-4-3-2-112•24-23-22-21-20-7-6-5-4-3-2-112•24-23-22-21-20-19-18-17-16-110•24-23-22-21-20-19-18-17-2-110•24-23-22-21-20-19-18-3-2-110•24-23-22-21-20-19-6-5-4-3-2-112•24-23-22-21-20-19-4-3-2-110•24-15-14-13-12-11-10-9-8-7-6-5-4-3-2-116•24-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-118•24-17-2-14•24-17-16-14•25-24-23-22-21-20-19-18-17-16-15-14•-13-12-11-10-9-8-7-6-5-4-3-2-125•25-24-23-14-13-12-11-10-9-8-7-6-5-4-3-2-117•25-24-23-12-11-10-9-8-7-6-5-4-3-2-115•25-24-23-22-11-10-9-8-7-6-5-4-3-2-115•25-24-23-22-21-10-9-8-7-6-5-4-3-2-115•25-24-23-22-21-8-7-6-5-4-3-2-113•25-24-23-22-21-20-7-6-5-4-3-2-113•25-24-23-22-21-20-19-18-17-16-111•25-24-23-22-21-20-19-18-17-2-111•25-24-23-22-21-20-19-18-3-2-111•25-24-23-22-21-20-19-6-5-4-3-2-113•25-24-23-22-21-20-19-4-3-2-111•25-24-15-14-13-12-11-10-9-8-7-6-5-4-3-2-117•25-24-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-119•25-24-17-2-15•25-24-17-16-15•25-22-11-10-9-8-7-6-5-4-3-2-113•25-22-21-10-9-8-7-6-5-4-3-2-113•25-22-21-8-7-6-5-4-3-2-111•25-22-21-20-7-6-5-4-3-2-111•25-22-21-20-19-18-17-16-15-14-•13-12-11-10-9-8-7-6-5-4-3-2-123•25-22-21-20-19-18-17-16-19•25-22-21-20-19-18-17-2-19•25-22-21-20-19-18-3-2-19•25-22-21-20-19-6-5-4-3-2-111•25-22-21-20-19-4-3-2-19•25-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-119•25-18-3-2-15•25-18-17-2-15•25-18-17-16-15•25-20-7-6-5-4-3-2-19•25-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-121•25-20-19-4-3-2-17•25-20-19-18-3-2-17•25-20-19-18-17-2-17•25-20-19-18-17-16-17•20-7-6-5-4-3-2-1•20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1•20-19-4-3-2-1•20-19-18-3-2-1•20-19-18-17-2-1•20-19-18-17-16-1•7-6-5-4-3-2-1•第四行各个点•起点：点数：•14-13-12-11-10-9-8-7-6-5-4-3-2-114•23-14-13-12-11-10-9-8-7-6-5-4-3-2-115•23-12-11-10-9-8-7-6-5-4-3-2-113•23-22-11-10-9-8-7-6-5-4-3-2-113•23-22-21-10-9-8-7-6-5-4-3-2-113•23-22-21-8-7-6-5-4-3-2-111•23-22-21-20-7-6-5-4-3-