算法设计与分析第7章作业.pdf

HarbinInstituteofTechnologyPage1of10Designedby谢浩哲「算法设计与分析」第7章作业2015.10学号:15S103172姓名:谢浩哲1.在下图中考虑哈密顿环问题.将问题的解空间表示成树,并分别利用深度优先搜索和广度优先搜索判定该图中是否存在哈密顿环.问题解空间的树状结构:算法概述:从起始点出发,搜索从这个点出发所有可到达的点(深度优先或广度优先策略均可).对于每到达一个点,判断:是否已经回到起始点,是否经过重复的点.若经过了重复了点,则不再搜索.若到达了起始点,并且恰好经过了所有的点,则找到了最优解.HarbinInstituteofTechnologyPage2of10Designedby谢浩哲算法实现:深度优先搜索:1importjava.util.ArrayList;2importjava.util.List;34publicclassSolution{5publicbooleangetHamiltonPathway(6intstartPoint,intcurrentPoint,7ListIntegerpathway,boolean[][]isAccessable){8booleanhasPathway=false;9inttotalPoints=isAccessable.length;1011if(startPoint==currentPoint&&12isAllVisited(totalPoints,pathway)){13returntrue;14}15for(inti=0;itotalPoints;++i){16if(isAccessable[currentPoint][i]&&17!isVisited(startPoint,i,pathway)){18pathway.add(i);19hasPathway=getHamiltonPathway(20startPoint,i,pathway,isAccessable);2122if(hasPathway){23break;24}25pathway.remove(pathway.size()-1);26}27}28returnhasPathway;29}3031privatebooleanisVisited(intstartPoint,32intcurrentPoint,ListIntegerpathway){33intstartPointCounter=0;34for(Integere:pathway){35if(e.intValue()==startPoint&&startPointCounter==0){36++startPointCounter;37continue;38}39if(e.intValue()==currentPoint){40returntrue;HarbinInstituteofTechnologyPage3of10Designedby谢浩哲41}42}43returnfalse;44}4546privatebooleanisAllVisited(47inttotalPoints,ListIntegerpathway){48for(inti=0;itotalPoints;++i){49if(!pathway.contains(i)){50returnfalse;51}52}53returntrue;54}55}广度优先搜索:1importjava.util.ArrayList;2importjava.util.LinkedList;3importjava.util.List;4importjava.util.Queue;56publicclassSolution{7privateclassPoint{8publicPoint(intpoint){9this.point=point;10this.pathway=newArrayListInteger();11}1213publicPoint(intpoint,ListIntegerpathway){14this.point=point;15this.pathway=pathway;16}1718publicintpoint;19publicListIntegerpathway;20}2122publicPointgetHamiltonPathway(intstartPoint,23boolean[][]isAccessable){24inttotalPoints=isAccessable.length;25QueuePointq=newLinkedListPoint();26q.offer(newPoint(startPoint));HarbinInstituteofTechnologyPage4of10Designedby谢浩哲2728while(!q.isEmpty()){29PointcurrentPoint=q.poll();3031if(startPoint==currentPoint.point&&32isAllVisited(totalPoints,currentPoint.pathway)){33returncurrentPoint;34}35for(inti=0;itotalPoints;++i){36if(isAccessable[currentPoint.point][i]&&37!isVisited(startPoint,i,currentPoint.pathway)){38ListIntegerpathway=39newArrayListInteger(currentPoint.pathway);40pathway.add(currentPoint.point);4142q.offer(newPoint(i,pathway));43}44}45}46returnnull;47}48}2.考虑8-魔方问题.分别用深度优先算法,广度优先算法,爬山法,最佳优先方法判定上图所示的初始格局能够通过一系列操作转换成目标格局,将搜索过程的主要步骤书写清楚.HarbinInstituteofTechnologyPage5of10Designedby谢浩哲问题的部分解空间树状结构:HarbinInstituteofTechnologyPage6of10Designedby谢浩哲深度优先搜索:搜索顺序为1-2-4-10-…广度优先搜索:搜索顺序为1-2-3-4-5-6-…爬山法:基于深度优先搜索,选取当前分支上最优解;搜索顺序为1-2-4-11-…最佳优先方法:基于深度优先搜索,选取所有分支上最优解;搜索顺序为1-2-4-11-…3.分别使用深度优先法和分支限界法求解子集和问题的如下实例.输入:集合S=7,4,6,13,20,8和整数K=18.输出:S’使得S’中元素之和等于K.深度优先搜索:问题的部分解空间如下如所示:算法实现:1importjava.util.List;23publicclassSolution{4publicbooleangetTargetNumbers(int[]numbers,5boolean[]isSelected,inttarget,6intsearchIndex,ListIntegerselectedNumbers){7booleanisTargetReached=false;8intcurrentSum=totalSum(selectedNumbers);910if(currentSum==target){11returntrue;12}elseif(currentSumtarget){13returnfalse;14}HarbinInstituteofTechnologyPage7of10Designedby谢浩哲1516for(inti=searchIndex;inumbers.length;++i){17if(!isSelected[i]){18isSelected[i]=true;19selectedNumbers.add(numbers[i]);2021isTargetReached=22getTargetNumbers(numbers,isSelected,target,23searchIndex+1,selectedNumbers);2425if(isTargetReached){26break;27}28isSelected[i]=false;29selectedNumbers.remove(selectedNumbers.size()-1);30}31}32returnisTargetReached;33}3435privateinttotalSum(ListIntegerselectedNumbers){36intsum=0;37for(Integere:selectedNumbers){38sum+=e.intValue();39}40returnsum;41}42}分支限界法:分枝限界法可以在深度优先搜索时进行必要的剪枝,例如对于分支7-4.此时的分支上的和为11,因此该分支上的数最大不可能超过18-11=7.因此可见,在深度优先搜索中搜索的13和8这两个分支其实可以进行剪枝.其他分支亦然.算法实现:只需将以上代码的17行替换为:1if(!isSelected[i]&&2currentSum+numbers[i]=target){3//...4}HarbinInstituteofTechnologyPage8of10Designedby谢浩哲4.将任意一整数n划分为若干整数之和的划分,并按照降序的序列输出出来,例如5的划分为:5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1.问题解空间的树状图:算法实现(深度优先搜索):1importjava.util.ArrayList;2importjava.util.List;34publicclassSolution{5publicListListIntegergetSplit(intn){6ListListIntegerresultSet=newArrayListListInteger();78for(inti=0;in;++i){9ListIntegercurrentSplit=newArrayListInteger();10currentSplit.add(n-i);1112resultSet.addAll(getSplit(i,n-i,currentSplit));13}14returnresultSet;15}1617publicListListIntegergetSplit(intn,intmaxValue,ListIntegercurrentSplit){18ListListIntegerresultSet=newArrayListListInteger();HarbinInstituteofTechnologyPage9of10Designedby谢浩哲1920if(n==0){21resultSet.add(currentSplit);22}23for(inti=0;in;++i){24if(n-i=maxValue){25ListIntegernewSplit=newArrayListInteger(currentSplit);26newSplit.add(n-i);27resultSet.addAll(getSplit(i,n-i,newSplit));28}29}30returnresultSet;31}32}5.在一个一维空间上有n个点1,2,3,4,…,n,有一个粒子它初始位置为1,粒子从初始位置1开始