填空题使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是(),只使用约束条件进行裁剪的是()。

填空题
使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是(),只使用约束条件进行裁剪的是()。

参考解析

解析: 暂无解析

相关考题:

解决0/1背包问题只可以使用动态规划和分支限界法。() 此题为判断题(对,错)。

回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数。() 此题为判断题(对,错)。

解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划,需要排序的是回溯法,分支限界法。() 此题为判断题(对,错)。

不能保证求得0-1背包问题的最优解。A.分支限界法B.贪心算法C.回溯法D.动态规划策略

阅读下列说明,回答问题1至问题2,将解答填入答题纸的对应栏内。【说明】0—1背包问题可以描述为:有n个物品,对i=l,2,…,n,第i个物品价值为vi,重量为wi(vi和wi为非负数),背包容量为w(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,即,且总重量不超过背包容量,即,其中,xi∈{O,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品放入背包。用回溯法求解此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←cp02 (1)3 fp←l4 while true5 while k≤n and cw+w[k]≤w d。6 (2)7 cp←cp+v[k]8 Y[k]←l9 k←k+110 if kn then11 if fpcp then12 fp←cp13 fw←cw14 k←n15 X←Y16 else Y (k)←O17 while BOUND(cp,cw,k,W) ≤fp do18 while k≠O and Y(k)≠l d019 (3)20 if k=0 then return2l Y[k]←022 cw←cw-w[k]23 cp←cp-v[k]24 (4)

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 ← 02 (1)3 fp ← -14 while true5 while k≤n and cw+w[k]≤W do6 (2)7 cp ← cp+v[k]8 Y[k]← 19 k ← k+110 if k>n then11 if fp<cp then12 fp ← cp13 fw ← ew14 k ← n15 X ← Y16 else Y(k)← 017 while BOUND(cp,cw,k,W) ≤fp do18 while k≠0 and Y(k)≠1 do19 (3)20 if k=0 then return21 Y[k]←022 cw ← cw ← w[k]23 cp ← cp ← v[k]24 (4)

【问题 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:当前已获得的部分解。

● (65) 不能保证求得0-1 背包问题的最优解。(65)A. 分支限界法B. 贪心算法C. 回溯法D. 动态规划策略

在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是()A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划

解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是(),需要排序的是(),()。

回溯算法和分支限界法的问题的解空间树不会是()A、有序树B、子集树C、排列树D、无序树

下面问题()不能使用贪心法解决。A、单源最短路径问题B、N皇后问题C、最小花费生成树问题D、背包问题

下列算法中不能解决0/1背包问题的是()A、贪心法B、动态规划C、回溯法D、分支限界法

在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是()A、回溯法B、分支限界法C、回溯法和分支限界法D、回溯法求解子集树问题

使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是(),只使用约束条件进行裁剪的是()。

0-1背包问题的回溯算法所需的计算时间为()A、O(n2n)B、O(nlogn)C、O(2n)D、O(n)

回溯法搜索解空间树时,常用的两种剪枝函数为()和()。

用回溯法解0/1背包问题时,该问题的解空间结构为()结构。

优化问题根据目标函数和约束条件函数性质的不同分为线性规划问题和()问题。

单选题回溯算法和分支限界法的问题的解空间树不会是()A有序树B子集树C排列树D无序树

填空题解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是(),需要排序的是(),()。

单选题在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是()A回溯法B分支限界法C回溯法和分支限界法D动态规划

填空题回溯法搜索解空间树时,常用的两种剪枝函数为()和()。

单选题在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是()A回溯法B分支限界法C回溯法和分支限界法D回溯法求解子集树问题

填空题用回溯法解0/1背包问题时,该问题的解空间结构为()结构。

填空题优化问题根据目标函数和约束条件函数性质的不同分为线性规划问题和()问题。

单选题下列算法中不能解决0/1背包问题的是()A贪心法B动态规划C回溯法D分支限界法