搜索
深圳大学实验报告课程名称：算法设计与分析实验名称：消消乐问题学院：计算机与软件学院专业：计算机科学与技术报告人：蔡子辉学号：2017152128班级：03同组人：无指导教师：霍永凯实验时间：2018-04-15至2019-05-06实验报告提交时间：2018-05-04教务处制一．实验目的1、掌握回溯法设计思想。2、掌握消消乐问题的回溯法解法。二、实验步骤与结果说明：以下出现的m，n，k，x的意义如下：参数意义m棋盘的行数n棋盘的列数k棋子的种类总数x交换的步数（一）交换1步算法思想：遍历整个棋盘，每扫描到棋盘上一个点，就做如下操作：①交换：将当前点与附近的点进行交换，产生新的棋盘状态；②消除：对步骤①产生的所有新的棋盘状态进行消除，获得得分和减少步数；③在步骤②产生的棋盘状态里挑选一个分数最高的棋盘状态出来即可。最大规模：（二）交换x步1、暴力法算法思想：遍历整个棋盘，每扫描到棋盘上一个点，就做如下操作：①交换：将当前点与附近的点进行交换，产生新的棋盘状态；②消除：对步骤1产生的所有新的棋盘状态进行消除，获得得分和减少步数；③遍历步骤2消除后产生的所有新的棋盘状态，对于每个棋盘状态，重复步骤1-3，直到剩余步数为0。最大规模：2、查重法算法思想：当交换步数较多时，可能有一些棋盘状态是相同的。可以将所有棋盘状态放入一个集合中，如果当前状态已经在集合中，则结束当前状态，不再穷举。如下图，原来的棋盘状态产生了4个新的棋盘状态，他们的得分分别为9、4、10、9，里面有两个棋盘状态的得分都是9分，如果它们的棋盘也完全相同，则可以把第2个9分剪掉。最大规模：3、贪心法算法思想：对于每个棋盘，对它进行穷举式的交换后，它产生了众多的棋盘状态。在这些状态中选目前得分最高的棋盘状态（同时舍弃其他状态），然后继续进行穷举和筛选，一直重复该操作，直到剩余步数为0。如下图，原来的棋盘状态产生了5个新的棋盘状态，他们的得分分别为14、8、2、15、4，则只保留它们之中得分最高的棋盘状态——15分，其他状态全部剪掉。最大规模：4、平均法算法思想：对于每个棋盘，对它进行穷举式的交换后，它产生了众多的棋盘状态。在这些状态中选目前得分高于当前层所有状态的平均分的状态（同时舍弃其他状态），然后继续进行穷举和筛选，一直重复该操作，直到剩余步数为0。如下图，原来的棋盘状态产生了5个新的棋盘状态，他们的得分分别为8、1、4、10、2，先计算它们的平均分，结果为5分，于是把低于5分的棋盘状态1分、4分、2分都剪掉。最大规模：5、部分贪心法算法思想：对于规模比较大的棋盘，刚开始进行交换时，不同的交换位置可能对棋盘的格局影响特别大。所有可以在前几步进行穷举，然后再进行贪心。这样可以保证在前几步获得比较高的分数再进行贪心，以至于最后得到的分数不至于太低。（在实现时，采用了前30%步穷举，后70%步贪心）如下图，原来的棋盘状态先产生了2个新的棋盘状态状态1和状态2，这时候不进行剪枝，继续穷举。状态1又穷举产生3个新的棋盘状态，它们的分数分别为10、15、2，这时候只保留最高分15，其他的都剪掉；类似地，状态2又穷举产生了3个新的棋盘状态，它们的分数分别为10、1、8，这时候只保留最高分10，其他的都剪掉。最大规模：状态1状态26、部分平均法算法思想：与部分贪心法思想相同。（在实现时，采用了前30%步穷举，后70%步平均）如下图，原来的棋盘状态先产生了2个新的棋盘状态状态1和状态2，这时候不进行剪枝，继续穷举。状态1又穷举产生3个新的棋盘状态，它们的分数分别为10、8、3，计算它们的平均分，结果为7分，这时候把低于7分的3分给剪掉；类似地，状态2又穷举产生了3个新的棋盘状态，它们的分数分别为1、1、10，计算它们的平均分，结果为4分，这时候把低于4分的两个1分的棋盘状态剪掉。状态1状态2最大规模：三、实验分析（一）耗时t，误差e与棋盘的行数m的关系令n=15,k=5,x=3，作出t-m曲线图与e-m曲线图：0100000200000300000400000500000600000700000800000900000100000045678910耗时t（单位：纳秒）行数mt-m曲线图（n=15,k=5,x=3）暴力法查重法贪心法部分贪心法平均法部分平均法分析：从t-m曲线可以看出：①当棋盘的行数增大时，暴力法和查重法耗时增加得非常厉害；②暴力法与查重法的时间开始有所差别。这主要是因为棋盘增大时，棋盘将有更多相同的状态，从而更多的结点被剪掉；③所有的近似算法耗时明显小于暴力法和查重法。从e-m曲线可以看出：①部分平均法与部分贪心法的误差明显小于平均法与贪心法；②在m=7时，贪心法与平均法处曲线凹陷，这可能是由于这时候数据总体上偏大（具有相同的最大值和高于平均分的棋盘状态较多）；③随着m增大，各种近似算法的误差基本不变。即误差e与m没有明显的关系。（二）耗时t，误差e与棋盘的列数n的关系令m=15,k=5,x=3，作出t-n曲线图与e-n曲线图：02468101214161845678910误差e（%）行数me-m曲线图（n=15,k=5,x=3)贪心法部分贪心法平均法部分平均法分析：从t-n曲线可以看出：n对t的影响基本与m对t的影响基本相同，但m对t的影响比较显著。从e-n曲线可以看出：e与n并无明显的关系。010000020000030000040000050000060000070000080000090000045678910耗时t（单位：纳秒）列数nt-n曲线图（m=15,k=5,x=3）暴力法查重法贪心法部分贪心法平均法部分平均法051015202545678910误差e（%）列数ne-n曲线图（m=15,k=5,x=3)贪心法部分贪心法平均法部分平均法（三）耗时t，误差e与棋盘的棋子种类k的关系令m=9,n=9,x=3，作出t-k曲线图与e-k曲线图：分析：从t-k曲线可以看出：①当棋的种类k增大时，各种算法的耗时都越来越小；05000010000015000020000025000030000035000040000045000045678910耗时t（单位：纳秒）种类kt-k曲线图（m=9,n=9,x=3）暴力法查重法贪心法部分贪心法平均法部分平均法051015202545678910误差e（%）种类ke-k曲线图（m=9,n=9,x=3)贪心法部分贪心法平均法部分平均法②暴力法与查重法的时间差距逐渐减小。这主要是因为棋的种类增多时，棋盘更难出现相同的状态，从而剪枝效果越来越小。从e-k曲线可以看出：e与k并无明显的关系。（四）耗时t，误差e与棋盘的步数x的关系令m=7,n=7,k=5，作出t-x曲线图与e-x曲线图：0500000100000015000002000000250000030000003500000400000001234567耗时t（单位：纳秒）步数xt-x曲线图（m=7,n=7,k=5）暴力法查重法贪心法部分贪心法平均法部分平均法051015202530351234567误差e（%）步数xe-x曲线图（m=7,n=7,k=5)贪心法部分贪心法平均法部分平均法分析：从t-x曲线可以看出：①步数x对耗时t的影响非常大；②查重法的优势逐渐显示出来，这是因为步数较多时，具有较多相同的棋盘状态，因而剪枝效果明显；③各种近似算法依然能在较短的时间内得出近似结果。从e-x曲线可以看出：①当x增大时，各种近似算法都越来越难逼近最优解；②部分贪心法与部分平均法的曲线在x=4处凹下去，这是因为0.3*3=0.91，而0.3*4=1.21，所以穷举的步数在这里突然增加1步，以致误差有所下降。（五）总结对于较大的m,n,k，近似算法的误差并不会发生很大的改变；但对于较大的x，近似算法的误差则会有所增大。这是因为步数越多，越难用当前的棋盘预测未来。虽然x对精度有影响，但是半贪心法和半平均法的误差是波动式缓缓上升的，所以这两种算法得出的结果误差还比较小，具有一定的参考价值。四、实验心得通过这次实验，对回溯法有了较深的理解，同时了解到了剪枝的重要性，好的剪枝往往能快速得出误差较小的解。同时，通过这次的代码实现，更加熟练地运用了递归。这次实验，受益匪浅。注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。指导教师批阅意见：成绩评定：指导教师签字：年月日备注：