算法基础实践-01背包问题

算法基础实践—0-1背包问题组名：阿迪王包包里有糖组长：杨祺鹏组员：刘锦权,张鑫,胥樊,辜克生（191071班）,崔海涛(191071)指导老师：彭磊班号：191072,191071一．0-1背包问题介绍在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。注意：在本题中，所有的体积值均为整数,也就是说,每件物品只有取或者不取两种可能,不可以分解物品.二．背包问题的实质背包问题是一种组合优化的NP完全问题,相似的问题同样也是出现在商业,组合数学等行业,因此以最快速度和最精确得解决背包问题是非常有前景的.三．本小组的研究目标针对0-1背包这种特殊的背包问题,我们主要研究解决这个问题的传统算法以及最近新兴的算法,并且找出各种算法的优劣性,给出在不同情况应该用哪种算法才能最快最精确得解决0-1背包问题.四．实践过程传统算法选取:回溯法,遗传算法新型算法选取:蚁群算法,模拟退火算法,对这个四个算法，我们用一个形象的比喻先来介绍一下。问题：为了寻找世界上最高的山，一群兔子开始想办法（为了寻找最优路径）。一些兔子总是向着比自己高的山峰跑去。---局部搜索算法，回溯法一些兔子喝醉了，他们跑了很久很久，在这一段时间内，他们有可能进入平地，也可能进入高峰。然后兔子们醒酒了，他们向着最高的山峰跑去。---模拟退火算法一些兔子失忆了，被发射到了太空，并且在太空中随机得被发射到地球上，他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到最高的山峰。---遗传算法一些兔子在找到一个高山的时候，在山上拉了一坨便便使得别的兔子能找到这座高山，并且吸引别的兔子过来，被找到的高山越来越多，最后会找到最高的山峰。---蚁群算法1.回溯法回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法.回溯法解决0-1背包问题的优缺点:因为回溯法在构建解空间的时候要构建一棵完整的二叉树(最传统回溯法,没有进行优化),因此时间复杂度是指数型的.当背包物品很少,经过测试为小于等于15的时候,回溯法的效率是很高的,而且在1-15这一段数域内,解决时间相差无几,因此,在背包物品较少的时候,使用回溯法是很不错的选择.但是,随着背包物品的增加,在解决18个物品的时候,计算时间超过了500MS,19个物品就经常计算不出,20个物品的时候,就已经溢出了int32这个值表示的范围了。这是因为在构建解空间树的时候，就构建不出来了。回溯法求解的流程图：流程图中省略了开始构建解空间的部分，只写了回溯的算法。建立满二叉树的程序和生成随机数据的程序略。回溯算法的回溯程序：classDealBagProblem{publicTreeNode[]treeNode=BulidFullSubTree.treeNode;//已经建好的二叉树intmaxWeiht=0;//背包最大承重量inttreeLevel=Convert.ToInt32(Math.Floor(Math.Log(BulidFullSubTree.treeNodeNum,2)))+1;//二叉树的最大层数int[]optionW=newint[50000];//存储最优解的数组int[]optionV=newint[50000];//存储最优解的数组inti=0;//计数器，记录相应数组的下标intmidTw=0;//存储过程中的重量intmidTv=0;//存储过程中的价值intmidTw1=0;//同上intmidTv2=0;//同上BagNode[]bagNode;//存储货物节点string[]solution=newstring[2];//程序最终所得的最优解，分别存储：最优价值，总重量从最后一个物品开始找合适的解是非跳跃点去除跳跃点是受控跳跃点去除受控跳跃点合并是否否是循环调用回溯算法求出最优解publicDealBagProblem(BagNode[]bagN,TreeNode[]treeNode,intmaxW){bagNode=bagN;maxWeiht=maxW;}//cursor:二叉树下一个节点的指针;tw：当前背包的重量；tv：当前背包的总价值publicvoidBackTrace(TreeNodecursor,inttw,inttv){if(cursor!=null)//如果当前节点部位空值{midTv=tv;midTw=tw;if(cursor.left!=null&&cursor.right!=null)//如果当前节点不是叶子节点{//如果当前节点是根节点，分别处理其左右子树if(cursor.level==0){BackTrace(cursor.left,tw,tv);BackTrace(cursor.right,tw,tv);}//如果当前节点不是根节点if(cursor.level0){//如果当前节点是左孩子if(cursor.bLeftNode){//如果将当前货物放进书包而不会超过背包的承重量if(tw+bagNode[cursor.level-1].weight=maxWeiht){//记录当前节点放进书包Optiontrace[i].mark=i;Optiontrace[i].traceStr+=1;tw=tw+bagNode[cursor.level-1].weight;tv=tv+bagNode[cursor.level-1].value;if(cursor.left!=null){//如果当前节点有左孩子，递归BackTrace(cursor.left,tw,tv);}if(cursor.right!=null){//如果当前节点有右孩子，递归BackTrace(cursor.right,midTw,midTv);先判断是否是根节点，如果是根节点，就先进行回溯以求出下面的节点判断是否是根节点，如果不是根节点则回溯如果不是叶子节点且是左孩子节点，且加上该节点的重量的价值后都不超过限制，则记录下重量和价值如果该节点有右孩子节点，则进行回溯}}if(tw+bagNode[cursor.level-1].weightmaxWeiht){//Optiontrace[i].traceStr+=0;if(cursor.right!=null){//如果当前节点有右孩子，递归BackTrace(cursor.right,midTw,midTv);}optionV[i]=tv;optionW[i]=tw;i++;tv=0;tw=0;}}//如果当前节点是其父节点的右孩子记录当前节点下的tw,tv当递归回到该节点时，以所记录的值开始向当前节点的右子树递归注释很详细了哦else{midTv2=midTv;midTw1=midTw;Optiontrace[i].traceStr+=0;if(cursor.left!=null){BackTrace(cursor.left,midTw,midTv);}if(cursor.right!=null){//递归所传递的midTw1与midTv2是先前记录下来的BackTrace(cursor.right,midTw1,midTv2);}}}}//如果是叶子节点，则表明已经产生了一个临时解if(cursor.left==null&&cursor.right==null){//如果叶子节点是其父节点的左孩子if(cursor.bLeftNode){if(tw+bagNode[cursor.level-1].weight=maxWeiht){如果加上左孩子节点的重量超过限制，则记录重量和价值备用这个节点是叶子节点，如果加上该节点的重量不超过限制，则已经tw=tw+bagNode[cursor.level-1].weight;tv=tv+bagNode[cursor.level-1].value;if(cursor.left!=null){BackTrace(cursor.left,tw,tv);}if(cursor.right!=null){BackTrace(cursor.right,midTw,midTv);}}if(tw+bagNode[cursor.level-1].weightmaxWeiht){//MessageBox.Show(加上叶子结点重量超标,用前一个数值);tw=bagNode[cursor.level-1].weight;tv=bagNode[cursor.level-1].value;}}//存储临时优解optionV[i]=tv;optionW[i]=tw;i++;tv=0;tw=0;}}}所有的可能解都存在数组里面，最后对数组里面的数值进行比较就可以得出最优解了，数组最优解的比较略。运行截图：计算10个物品：如果加上该节点的重量超过了限制，则使用该节点的前一个节点的重量，记录重量和价值备用18个数据：2.遗传算法遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本计算过程：a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。遗传算法的优劣：遗传算法得出来的只是无限近似的最优解，而不是确切的解，而且最优解求出来以后可能会溢出。遗传算法流程图：随机产生初始种群收敛准则满足？执行选择算子NRandom[0,1]PcY执行交叉算子Random[0,1]PmY执行变异算子NNY输出搜索结果遗传算法只列出遗传算法的main函数，算法程序太长了，不一一详述。privatevoidgeneration(){intmate1,mate2;doubletmpWeight;boolispop;inti=0;while(ipopsize){ispop=false;while(!ispop){//选择mate1=selection();mate2=selection();//交叉crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);//变异for(intj=0;jlchrom;j++){newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);}tmpWeight=cal_weight(newpop[i].chrom);if(tmpWeight=contain){newpop[i].fitness=cal_fit(newpop[i].chrom);newpop[i].weight=tmpWeight;ispop=true;}}i++;}}}程序截图：十五个物品，计算时间仅10MS，但是只生成最优解。3.蚁群算法蚁群算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法的