回溯法 | 您所在的位置:网站首页 › 怎么叠一个空间大的包 › 回溯法 |
一、简介 01背包典型的解法是动态规划,之前的博客也有介绍,这里就不再赘述。 https://blog.csdn.net/Jayphone17/article/details/102553763 这里有一些回溯法相关的基础理论知识: https://blog.csdn.net/Jayphone17/article/details/102910824 二、算法设计 (1)定义问题解空间 购物车问题属于典型的01背包问题,问题的解是从n个物品中选择一些物品使其在不超过容量的前提下价值最大。没个物品有且仅有两种状态,要么装进购物车,要么不装进。用0表示不装进购物车,用1表示装进购物车。所以该问题的解是一个n元组,且每个分量的取值为0或者1。 (2)确定解空间组织结构 问题的解空间描述了2^n种可能接,也可以说是n个元素组成的集合所有子集个数。 可见,问题的解空间树为自己输,且是二叉树,解空间树的深度为问题的规模n。如图所示: (3)搜索解空间树 1.约束条件: 购物车问题的解空间包含2^n种可能解,存在某种或某些物品无法装进购物车的情况,因此需要设置约束条件,判断装进购物车的物品总重量是否超过购物车的重量,如果超出,就是不可行解,否则为可行解。搜索过程不再搜索那些导致不可行解的结点及其孩子结点。 约束条件是: 2.限界条件: 购物车01背包问题的可行解可能不止一个,问题的目标是找一个装入购物车的物品总结之最大的可行解,即最优解。因此,需要设置衔接条件来加速找出该最优解的速度。 根据解空间树的组织结构,对于任何一个中间结点z(中间状态),从根结点到z结点的分支所代表的状态(是否已经装进购物车)已经确定,从z到其子孙结点的分支状态是不确定的。 也就是说,如果z在解空间树中所处的层次是t,说明第一个物品到t-1个物品的状态已经是确定了。我们只需要沿着z的分支扩展很容易确定第t种物品的状态。此时,1~t种物品的状态已经确定了。 但是t+1~n种物品的状态还不确定。 我们设置前t种物品的状态是已经装进购物车的物品的总价值,用cp表示。 我们设置t+1~n种物品总价值用rp表示。 因此我们用cp+rp是所有从根结点出发经过中间结点z的可行解的价值上界。 如果价值上界小于或者等于当前搜索到的最优值(用bestp表示,初始值为0),则说明从中间结点z继续向子孙结点搜索不可能得到一个更优解,没有搜索的必要(剪枝),反之,继续向子孙结点搜索。 限界条件为:cp+rp |
CopyRight 2018-2019 实验室设备网 版权所有 |