本人此时还是一名研一的小菜鸡,刚学会了这个算法的基本概念,来总结一下,谁知道今后的我再看到这篇自己写的博客的时候会不会笑出来,哈哈哈哈哈哈哈哈,所以吗,错了的化大佬们评论指正就好了。
还有系列文章动态规划法解01背包问题,分支限界法解01背包问题哈,需要的化以下是链接:
动态规划法:/qq_29051107/article/details/103394491
分支限界法:/qq_29051107/article/details/103395841
1背包问题题干(题目中所给出的条件和问题)
给定n种物品和一背包。物品i的体积是Si,其价值为Vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
C=50, S=(15,5,25,27,30),W=(30,12,44,46,50)
2回溯法求解
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
粘一段百度百科的内容作为概念解释哈,巴拉巴拉巴拉,喋喋以喋倚喋喋。
核心思路:
1.初始化:目标函数置为0,将物品按价值体积比的非增顺序排序
2.搜索:从根节点出发,尽量沿左孩子结点前进,当不能继续沿左孩子前进时,把搜索转到右子树,得到问题的一部分解。
3.估计:由部分解所能得到的最大价值:如果估计价值高于上界,继续向下搜索,直到找到可行解保存可行解,并用可行解得到的目标函数的值更新目标函数的上界,向上回溯,寻找其他可行解。若估计值小于目标函数的上界,则丢弃当前的部分解,向上回溯。
接下来解释一下接下来要出现的几个变量所代表的意思:
Weav:当前节点的估计价值
Wup:当前的最优值(注意,是当前,可能是最终的最优,也可能不是)
注意算法计算从这里就开始了!!!
第一步:
令Wup=0,将物体的序号按价值体积比,排序结果是(2, 1, 3, 4, 5)也就是此时的S和W需要按照新的物品顺序变一下,如下:
S=(5,15,25,27,30)
W=(12,30,44,46,50)
第二步:
生成节点1、 2、 3、 4、 5,(如下图所示)
得到部分解(1,1,1,0),
(因为从节点5开始就不在是左孩子了,所以要在这里估计一下价值,来确定是否还继续往下搜索,估计价值时认为物品可以部分放入的)
估计当前部分解的价值为:Weva=(12+30+44) +(0) +(50-5-15-25) *(50/30) =94.3,
因为Weva>Wup
所以继续向下搜索生成结点6,
得到可行解(1,1,1,0,0),
得到价值为86,
更新Wup=86
第三步:
回溯:沿右孩子回溯到左孩子4(即节点4),生成相应右孩子7(即节点7)(如下图)
得到部分解(1,1,0,1),
此时 估计价值Weva= ( 12+30) +( 46) +( 50-5-15-27)*( 50/30) = 93 > Wup
因为Weva>Wup,
继续生成结点8, 9,
得到可行解(1,1,0,1,0),
价值为88,
更新Wup=88
第四步:
回溯到8生成10,得到部分解(1,1,0,0), 估计部分解Weva=92>88
继续生成结点11,得到可行解(1,1,0,0,1), 更新Wup=92
因为11是左孩子,生成其对应的右孩子结点12,得到另一个可行解(1,1,0,0,0)
第五步:
回溯,沿结点12向上回溯到结点3生成结点13,
得到部分解(1,0),此时Weva= (12) +(44)+(50-5-25) *(46/27) =90.1<92
向上继续回溯生成结点14,得到部分解(0),
此时得到的Weva=(0) +(30+44) +(50-15-25)*(46/27) = 91.03<92,
因此,回溯到根结点,算法结束,得到最优解(1, 1, 0, 0, 1),最大价值92
总结:
回溯法不愧称为深度优先算法,总是一条路先摸索完成后,再回过头去看看有没有更好的路走。与分支限界法正好相反。本人博客中也有分支限界法的介绍。