回溯法在0-1背包问题中的应用

回溯法在0-1背包问题中的应用

第 7第 1期卷 22 0年 1 08 2月

软件导刊So￣wa eGude r i

V0 . .2 17NO1 De . O 8 c2O

回溯法在0 1包问题中的应用—背徐颖(西安石油大学计算机学院，陕西西安 7 0 6 ) 1 0 5摘要：结60 1包问题介绍了回溯法的基本思想和解题步骤，—背并在VC .g境下验证了回溯法可以有效地解决”6 - O

0 1包问题。—背

关键词：溯法；—背包问题；解；空间回 01求解中图分类号：P 1 T 32文献标识码： A文章编号：6 2 7 0 (0 8 1— 0 4 0 17— 80 2 0 ) 2 0 5— 2

用值或称价值。他的问题就是在不超过背包载重量的前提

O引言 回溯法是算法设计的基本方法之一，又称“通用解题法”。

下，化所能携带的物品的总价值 P优 o

该问题是0 1—背包问题的一个典型实例。其数学描述为： n个物品，重量分别为W、值分别为P,中O 一，包的 价其≤≤n 1背载重量为。用表示物品被装入背包的情况，如果物品澉n 一1

使用回溯法可以系统地搜索所给问题的一个解或全部解。它适用于求解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解问题，且适用于求解组合数量较大的问题。因此.了解回溯法的基本思想与解题步骤对解决现实生活中的诸多问题具有非常重要的意义。

选中， 1否则，i。 Nx; x O求满足目标函数P m x p= -= a 和约束方i1=n— l

程

≤的物品组合 ( 一，,与相应的总价值P 铷， )。

1回溯法的基本思想 回溯法通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题，义其解空间。这定个解空间必须至少包含问题的一个解 (能是最优的 )然后组可。

3回溯法求解0 1—背包问题31定义问题的解空间 .

根据上述O l—背包问题的数学描述，向量可以表示成X=解

织解空间。确定易于搜索的解空间结构。典型的组织方法是图或树。一旦定义了解空间的组织方法，即可按照深度优先策略从开始结点出发搜索解空间。

并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树 .目标函数剪去得不到最用优解的子树，免无效搜索。避

{X,,n ) 0= 1 (0… X- I=或托 1。若n 3则此0 1 Ix=,—背包问题的解空间为{0 0 0, 0 0,) (,, ) (,, ) (,, ) (, 1, (,, ) (, 1, 0 10, 0 1 1, 1 0 0, 10,)(,, ) (,, )。 1 1 0, 1 1 1 1 32确定解空间的结构 .

可以用树的形式将解空间表达出来。树中从第i到第i 1层+层的边上的值表示解向量中耽的取值，假定第的左子树描 并层述物品被装入背包的情况，右子树描述物品被拒绝的情

2 0 1包问题 —背背包问题在现实生活中有着广泛的应用背景，如预算控

况。该0 1则—背包问题的状态空间树就表示为一棵高度为n的完全二叉树 (图l如所示 )。从根结点到叶子结点的任一路径就对应解空间中的一个解向量。

制、目选择、料切割、项材货物装载等问题。如果对每个对象只提供两种选择：部接受或全部拒绝，该背包问题就是0 1全则—背包问题。

33搜索解空间 .

构造出问题的状态空间树以后，可以从其根结点出发搜就索解空间，即决定每个物品的取舍。了使目标函数的值增加最为

般定一个旅行爱好者准备带着一个背包去旅行。一步假进

定旅行者知道背包所能承受的最大负荷为，以及他想要携带的n不同的有用物品集，帐篷、壶、缩饼干、漱用品个如水压洗等，个物品要么全部接受，么全部拒绝。假设每个物品i 每要由两个值来表征：个是重量值一个是旅行者赋予物品的有一

快，以优先选择价值最大的物品装入背包，可然后是价值量次之的物品……直至背包装不下为止。但是，如果所选择的物品重量很大，使得背包载重量消耗速度太快，以至后续能装入背包的物品迅速减少，使得继续装入背包的物品在满足了约束方程的要

作者简介：颖 (9 0 )女，苏丰县人，徐 18~,江西安石油大学计算机学院硕士研究生，究方向为算法分析与设计。研

回溯法在0-1背包问题中的应用

第 1 2期

徐

颖：回溯法在 O 1背

包问题中的应用一

5 5

x i=;物品i入背包[] l//装}

es b=[] i c c; l e+ p i/] (- w) w[J

rt nb/ e r;/ u背包装满，将所有物品的的总价值作为一个上限返回 35结果 .图1 n 3 0 1包问题的状态空间树 =时 -背

基于上述思想设计的回溯算法运行结果如图2所示。

求以后，无法达到目标函数的要求。因此，好优先选择那些既最能使目标函数的值增加最快。又能使背包载重量消耗速度较慢的物品装入背包。了达到这个目的，为首先把所有物品按价值重

量比的非增顺序排列，然后按照这个顺序进行搜索。在装包过程中，尽量优先选择价值重量比较高的物品装要入背包。表现在搜索过程中，就是要尽量沿着左子树结点前进。 当不能继续前进时 (设该结点为 T,得到问题的一个部分假 )就解，把搜索转移到右子树。估计由该部分解所能得到的最大并

价值，即结点T的上限。可以用贪婪算法处理剩余物品：将按照价值重量比非增顺序排列的剩余物品依次装入背包 .至无法完

全装入下一个物品时，就将该物品的一部分装满背包。这样就可以得到一个上限。如果该值为当前最优值：续由右子树向继下搜索，大部分解，至找到可行解；存可行解，把可行扩直保并

图 2 O 1包问题的回溯法运行结果 一背

4算法分析回溯算法的运行时间取决于它在搜索过程中所生成的结点数。而限界函数可以大大减少所生成的结点个数。避免无效

解的值作为当前最优值，向上回溯，找其他可行解；寻若该值小于当前最优值：丢弃当前正在搜索的部分解，向上回溯。复使反用此方法，至搜索完整个解空间。直 34应用回溯法求解0 1包问题的算法步骤 . -背 ( )价值重量比的非增顺序排列物品。 1按

搜索，快搜索速度。但调用限界函数计算上界需花费O( )加 n时间。最坏情况下有0(个右儿子结点需调用限界函数，故计 2)算0 1—背包问题的回溯算法的时间复杂度为 O(2) n。回溯法的

() 2初始化：当前背包重量C为0当前背包中物品总价值c W, p为0当前搜索深度i

,,为0当前解向量为x￣-,[]o当前最优值 P。 -为0()用限界函数。 3调

另一个重要特性就是在搜索执行的同时产生解空间。在搜索过程中的任何时刻，保留从开始结点到当前可扩展结点的路仅径，其空间需求为 0(从开始结点起最长路径的长度 )所以，。该算法的空问复杂度为O( ) n。

( ) I返回的上限大于当前最优值 P从物品开始把物 4 3果￣,品装入背包，至没有物品可装或装不下物品为止，生成直并部分解。转步骤 ( )否则，步骤 ( ) 5;转 6。 ( )果 k于或等于物品总数量 n,得到一个可行解， 5如大则并把该可行解的值作为当前最优值， in,步骤 ( )以便回溯令=转 3,搜索其他可行解；则， ik l拒绝物品 k,物品k l续装 否令=+,从+继入，步骤 ( )转 3。

5结束语综上所述，回溯法虽然是通过搜索问题的解空间来得到问题的解，它并不是首先生成问题的所有可能解，但然后再去逐一

判断这些解是否满足约束条件和目标函数，而是每次只构造

( )> 0[] 0,=一，至条件不成立。 6当k=且x k=时令k k 1直即沿着右分支结点方向向上回溯 .至左分支结点。直 ( )果 k O,法结束；则，步骤 8 7如<算否转 .

可能解的一部分，然后评估这部分解。如果这部分解有可能导致当前最优解，对其进一步构造；则，则否就放弃这部分解，回 …… 此处隐藏：2217字，全部文档内容请下载后查看。喜欢就下载吧 ……