使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是(),只使用约束条件进行裁剪的是()。
第1题:
A.使用材料最优
B.建立优化设计数学模型
C.确定优化设计问题的目标函数、约束条件和设计变量
D.选择适用的优化方法
第2题:
决策变量、目标函数和约束条件是数学规划模型的三个要素,若目标函数和约束条件均为线性的数学规划问题称为非线性规划。()
第3题:
此题为判断题(对,错)。
第4题:
解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是(),需要排序的是(),()。
第5题:
【问题 1】(8 分)
用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
第6题:
在规划问题中,若目标函数和约束条件中必须同时为决策变量的非线性函数,这类问题才称为非线性规划问题。()
第7题:
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品 放入背包。
【问题1】(8分)
用回溯法求解此0-1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点己经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1 cw ← cp ← 0
2 (1)
3 fp ← -1
4 while true
5 while k≤n and cw+w[k]≤W do
6 (2)
7 cp ← cp+v[k]
8 Y[k]← 1
9 k ← k+1
10 if k>n then
11 if fp<cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 (4)
本题考查的是用回溯法求解0-1背包问题。回溯法有两类算法框架:非递归形式和递归形式,本题采用非递归形式表示。理解回溯法的基本思想和这两类算法框架是正确解答本题的根本要求·回溯法从第一项物品开始考虑是否应该装入背包中,因此当前考虑的物品编号k从1开始,即k←1。然后逐项往后检查,若能全部放入背包则将该项放入背包,此时背包的重量应该是当前的重量加上当前考虑物品的重量,即cw←cw+w[k],当然背包中物品的价值也为当前的价值加上当前考虑物品的价值。若己经考虑完了所有的物品,则得到一个解,判断该解是否为当前最优,若为最优,则将该解的信息放入变量fp、fw和X中。若还没有考虑完所有的物品,意味着有些物品不能放入背包,此时先判断若不将当前的物品放入背包中,则其余物品放入背包是否可能得到比当前最优解更优的解,若得不到则回溯;否则继续考虑其余的物品。
【问题1】(共8分,各2分)
(1)k ← 1 或其等价形式
(2)cw ← cw + w[k] 或其等价形式
(3)k ← k – 1 或其等价形式
(4)k ← k + l 或其等价形式
第8题:
A. 变量目标函数
B. 变量约束条件
C. 约束条件个数
D. 不确定
第9题:
优化设计的数学模型的基本组成要素是()
第10题:
下列有关线性规划问题的标准形式的叙述中错误的是()。