你好,游客 登录 注册 搜索
背景:
阅读新闻

回溯法——求解0-1背包问题

[日期:2014-10-28] 来源:CSDN博客  作者:水田如雅 [字体: ]

  以前研究过一个简单的N皇后问题,对回溯法也有了个模糊的认识,大致理解就是:先一直做某件事,当完成某个条件时或者是触犯某个条件时,再返回到最近的一个类似还原点的地方。

  在用回溯法求解0-1背包问题的时候,主要遇到三个相对难解决的问题:1,什么是界限函数;2,什么时候用它;3,回溯到哪儿。

  什么是界限函数?

  如下图:

  当我们身在一棵搜索空间树中,站在一个K点举棋不定的时候,我们可以用它估算如果我们继续向下走,我们走完本段路会获得的总价值。假设我们现在有一个最大解,当我用界限函数算出一个价值后和我当前的最大解比较,如果能获得更大利益,我们选择继续向下走,如果不能,果断放弃。

  从下图中的伪代码可以看出,我们计算后半段最大价值的时候,使用的还是一个贪心算法,虽然分割的情况是不被允许的,但是我们可以用这个结果来进行估算。

  回溯法得到的搜索空间树:

  什么时候使用界限函数?

  数学一点儿的说法是:当X[i]=0时。

  通俗一点说:当进入右结点的时候。

  如何回溯的问题?

  向上回溯到第一个不是0的结点(并且这个结点不是顶点)。

  求解思路

  如上图搜索树,在建立搜索树之前,我将所有的物品按照V/W(价值重量比)从大到小排序,然后从第一个开始,依次向背包(背包大小110)中放入,放到第 6个的时候,这时候发现6太大了,不能装入了,这时候用界限函数判断下,如果继续下去,会获得的最大价值,得出这个价值后,和上几次查找得到的最大价值对比,但是因为我们在这之前还没有获得过别的解,所以界限函数再和最大价值的初值-1比较的时候,总是会选择继续。这样我们就得到了一个解139.然后我们回溯到第一个X[i]不等于0的地方,此处为X[5],然后将X[5]置为 0,这时候X[5]置0了,我们就先用界限函数判断下X[6]到X[8]的情况,得出了个164.44,这个比我们上次得到的第一个解也是最大的解139大,说明向后继续,肯会出现一个比139还大的解,所以我们选择向后继续。。。。。。

  。。。。。。。。。

  但我们回溯到X[1]的时候,我们将X[1]置0,这时候用界限函数估算下物品2到物品8可能获得的最大价值,发现是155.11,比我们实际得到的最大解159还小,然后果断放弃,再向上回溯,发现这已经到了尽头了,然后停止。

  结合以前的N皇后问题,N皇后问题是我一行一行的放皇后,如果当下一行放到最后一个位置的时候还是会产生攻击,这时候我们就调整上一行皇后的位置,然后再回到本行从第一个开始放。对比0-1背包,这个是完成一次求解过程,然后就回溯继续求解。

  所以,回溯法是先一直做,做不下去了,然后才向回走。

  小结:

  0-1背包问题的用回溯法解决最开始提出的三个问题挺关键的,试想,如果一个问题足够大的话,用界限函数能够砍掉很多不合条件的子节点,极大的提高了效率。

    原文链接:http://blog.csdn.net/lhc1105/article/details/40516483





收藏 推荐 打印 | 录入:Cstor | 阅读:
相关新闻       回溯法 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款