软件设计师-算法设计和分析(一)
上传时间：上传者：ppkao
卷面总分：76分
试卷类型：中级软件设计师模拟试题
所需费用：2元
是否有答案：有
作答时间：90分钟
软件设计师-算法设计和分析(一)
问答题：&二、案例分析试题（1）阅读下列说明，回答问题。
某餐厅供应各种标准的营养套餐。假设菜单上共有n项食物m1，m2，...，mn，每项食物mi的营养价值为vi，价格为Pi，其中i=1，2…，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过M营养价值最大的套餐。
下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺（1）、（2）和（3）处。伪代码中的主要变量说明如下。
n：总食物项数。
v：营养价值组，下标从1～n，对应第1到第n页食物的营养价值。
p：价格数组，下标从1～n，对应第1到n项食物的价格。
M：总标准即套餐的价格不超过M。
x：解向量（数组），下标从1～n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元素值为1表示对应的食物出现在套餐中。
nv:n+1行M+1列的二维数组，其中行和列的下标均从0开始，nv[i][j]表示由前i项食物组合且价格不超过项j套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nv[n][M]。伪代码如下：
MaxNutrientValue（n,v,p,M,x）
for i=0 to n
nv[i][0]=0
for j=1 to M
nv[0][j] =0
for i=1 to n
for j=1 to M
if j＜ p[i]//若食物mi不能加入到套餐中
nv[i] [jl =nv[i-1][j]
nv[i][j] =nv[i-1][j]
nv[i] [j] =nv[i-1][j-p[i]]+v[i]
for i=n downto 1
return x and nv[n] [M]
现有5项食物， 每项食物的营养价值和价格如表9.3所示。
表9.3食物营养价值及价格表
编码 营养价值 价格
若要求总价格不超过100的营养价值最大的套餐，则套餐应包含的食物有 （4） （用食物项的编码表示），对应的最大营养价值为 （5） 。
问题1中伪代码的时间复杂度为 （6） （用O符号表示）。（2）阅读下列说明，回答问题1至问题3。
快速排序是一种典型的分治算法。采用快速排序对数组A[P..r]排序的3个步骤如下。
（1）分解：选择一个枢轴（pivot）元素划分数组。将数组A[p..r]划分为两个子数组（可能为空）A[p..g-1]和A[q+1..]，使得A[g]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。
（2）递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。
（3）合并：快速排序在原地排序，故不需合并操作。
下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。
A：待排序数组。
p，r：数组元素下标，从p到r。
q：划分的位置。
x：枢轴元素。
i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值。
j：循环控制变量，表示数组元素下标。
QUICKSORT （A,p， r）
if （p＜r）
q = PARTITION（A,p,r）；
QUICKSORT（A，p，q-1）；
QUICKSORT （A，q+1，r）；
PARTITION （A，p，r）
x=A[r]; i=p-1；
for（j=p；j≤r-1; j++）
if（A[j]≤x）
交换A[i]和A[j]
交换 （1） 和 （2） //注：空（1）和空（2）答案可互换，但两空全部答对方可得分
（1）假设要排序包含n个元素的数组，清给出在各种不同的划分情况下，快速排序的时间复杂度，用0记号。最佳情况为 （4） ，平均情况为 （5） ，最坏情况为 （6） 。
（2）假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况 （7） 。（最佳、平均、最坏）
（1）待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码。利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM（i/j）表示随机取i到j之间的一个数，包括i和j。
RANDOMIZED-PARTITION（A,p,r）
i= RANDOM（p，r）;
交换 （8） 和 （9） ；//注：空（8）和空（9）答案可互换
return PARTITION（A,p,r）;
（2）随机化快速排序是否能够消除最坏情况的发生 （10） 。（是或否）（3）阅读下列说明，回答问题。
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，即“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析，且总重量不超过背包容量，即“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析，其中，Xi∈0，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←cp←0
4 while true
5 while k≤n and cw+w[k]≤W do
cp← cp+v[k]
if k＞n then
if fp＜cp then
else Y（k）← 0
while BOUND（cp, cw, k, W） ≤fp do
while k≠0 and Y（k） ≠1 do
if k=0 then return
cw←cw-w[k]
cp ← cp-v[k]
考虑表9.2的实例，假设有3个物品，背包容量为22。图9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品 （5） ，获得的价值为 （6） 。
表9.2 0-1背包问题实例
物品1 物品2 物品3
重量 15 10 10
价值 30 18 17
单位价值 2 1.8 1.7
“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析
对于表9.2的实例，若采用穷举法搜索整个解空间，则搜索树的节点数为 （7） ，而用了上述回溯法，搜索树的节点数为 （8） 。（4）阅读下列说明，回答问题。
现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各项点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各项点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。
本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1，2，...，n），W=Wij，n*n为权重矩阵。设“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析为从顶点i到顶点，的一条最短路径的权重。当k=0时，不存在中间顶点，因此“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析。
当k＞0时，该最短路径上所有的中间顶点均属于集合1，2，…，k，若中间顶点包括顶点k，则“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析，若中间顶点不包括顶点k，则“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析。
于是得到如下递归式。
“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析
因为对于任意路径，所有的中间顶点都在集合1，2，…，n内，因此矩阵“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析n*n给出了任意两个顶点之间的最短路径，即对所有“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析表示顶点i到顶点，的最短路径。
下面是求解该问题的伪代码，请填充其中空缺的（1）～（6）处。伪代码中的主要变量说明如下。
W：权重矩阵；
n：图的顶点个数；
SP：最短路径权重之和数组，SP[i]表示顶点f到其他各顶点的最短路径权重之和，i从1到n；
min_SP：最小的最短路径权重之和；
min_v：具有最小的最短路径权重之和的顶点；
i：循环控制变量；
j：循环控制变量；
k：循环控制变量；
LOCATE-SHOPPINGMALL （W, n）
for i=1 to n
for j = 1 to n
“该试题”需要考试资料网会员 登录 进入在线考场才能查看试题答案及解析
for i=1 to n
for j=1 to n
min_SP=SP [1]
for i=2 to n
if min_SP＞SP [i]
min_SP=SP[i]
问题1中伪代码的时间复杂度为______（用O符号表示）。
热门相关试卷
最新相关试卷当前位置： >>
算法设计与分析
算法设计与分析第5章 回溯法1 学习要点理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架2 学习要点通过应用范例学习回溯法的设计策略 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团问题； （7）图的m着色问题 （8）旅行售货员问题3 回溯法－引言实例哈尔滨走到罗马 若完全不认识 路，会怎样走 哈尔滨两类问题存在性问题 优化问题可行解 最优解罗马4 回溯法－引言问题描述假定问题的解能表示成一个n-元组(X1,…,Xn),其中Xi 取自某个有穷集Si。所有这些n-元组构成问题的解 空间。假设集合Si的大小是mi,可能的元组数为 m=m1m2…mn两类问题存在性问题 求满足某些条件的一个或全部元组，如果不存在这 样的元组算法应返回No；这些条件称为约束条件。 优化问题 给定一组约束条件，在满足约束条件的元组中求使 某目标函数达到最大（小）值的元组。满足约束条 件的元组称为问题的可行解。5 回溯法－引言实例――罗密欧与朱丽叶问题 迷宫是一些互相连通的交叉路口的集合，给定一个入口、一个出口。 当从入口到出口存在通路时，输出选中的一条通路；否则，输出无 通路存在。 朱丽叶 (出口) 4 3 5 2 1 罗密欧 (入口) (a) 交叉路口 7 6 路口动作结果 1向前进入2 2向左进入3 3向右进入4 4（死路）回溯进入3 3（死路）回溯进入2 2向前进入5 5（死路）回溯进入2 2向右进入6 6向左进入7 (b)搜索过程6 回溯法－引言回溯法与穷举查找是一样的吗? 可以把回溯法和分支限界法看成是穷举法的一个改进. 该方法至少可以对某些组合难题的较大实例求解. 不同每次只构造侯选解的一个部分 然后评估这个部分构造解:如果加上剩余的分量也不可能求得 一个解,就绝对不会生成剩下的分量最坏情况: 指数级爆炸问题7 回溯法－相关概念以深度优先的方式系统地搜索问题的解的算法 称为回溯法 使用场合对于许多问题，当需要找出它的解的集合或者要求 回答什么解是满足某些约束条件的最佳解时，往往 要使用回溯法。 这种方法适用于解一些组合数相当大的问题，具有 “通用解题法”之称。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必 要搜索的穷举式搜索法。8 回溯法－相关概念具体做法系统性人工智能: 解空间树的不同 生成策略回溯法在问题的解空间树中，按深度优先策略，从根 结点出发搜索解空间树。跳跃性算法搜索至解空间树的任意一点时，先判断该结点是 否包含问题的解。如果肯定不包含，则跳过对该结点 为根的子树的搜索，逐层向其祖先结点回溯；否则， 进入该子树，继续按深度优先策略搜索。解空间树是实际存在的吗?9 回溯法－相关概念注意 同一个问题可以有多种表示，有些表示方法更简单， 所需表示的状态空间更小（存储量少，搜索方法简单）。问题的解向量 回溯法希望一个问题的解能够表示成一个n元 式(x1,x2,…,xn)的形式。 显约束 对分量xi的取值限定。 隐约束 为满足问题的解而对不同分量之间施加的约束。 解空间 对于问题的一个实例，解向量满足显式约束条 件的所有多元组，构成了该实例的一个解空间。10 回溯法－相关概念例如: 有n种可选择物品的0-1背包问题解空间由长度为n的0-1向量组成 n=3 : {(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1) (1,0,1),(1,1,0),(1,1,1)} 解空间结构: “树”或”图”11 回溯法－相关概念活结点:指一个自身已生成但其儿子还没有全部 生成的节点 扩展结点:一个正在产生儿子的结点 死结点:指一个所有儿子已经产生的结点.死节 点都是无法扩展的节点 深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子 C，就把C当做新的扩展结点。在完成对子树C（以 C为根的子树）的穷尽搜索之后，将R重新变成扩展 结点，继续生成R的下一个儿子（如果存在） 活结点 1 扩展结点回溯2死结点结束条件: 1)找到解 2)解空间无活结点12 回溯法－相关概念下面对解空间的树结构定义某些术语。 树上的每个节点确定了一个“问题的状态” 从根到各个节点的所有路径定义为这个问题的 “状态空间” “解状态集”由“问题状态集”的子集s组成。 从根到s的每一条路径定义了解空间的一个多 元组。 “回答状态集”是解状态集的一个子集，从根到 该子集的每一路径确定了解集合中的一个多元 组，它满足这个问题的约束条件。 解空间树型结构称为“状态空间树”。问题状态集 子集 解状态集 子集 回答状态集13 回溯法－相关概念对于某一问题，一旦给出了状态树的结 构，问题就比较好解。求解方法是系统地生成问题状态，进而确定 哪些问题状态是解状态，最后确定那些解状 态是回答状态。14 回溯法－相关概念两种生成问题状态的基本方法都是从根开始，产生其它节点。 在生成问题状态时，先建立一个活节点表。 如果对于一个扩展节点R，一旦产生了它的 一个儿子c，那么c就变成了一个新的扩展节 点。在完成对子树c的穷尽搜索以后，R将重 新变成扩展节点，这是一种深度优先的问题 状态生成法。 在一个扩展节点真正变成死节点之前，它一 直是扩展节点，这就是宽度优先的方法。15 回溯法－相关概念回溯法：为了避免生成那些不可能产生最佳解的问题 状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需 解的活结点，以减少问题的计算量。 具有限界函数的深度优先生成法称为回溯法16 0-1背包问题给定n种物品和一背包。物品i的重量是 wi，其价值为vi，背包的容量为C。问应 如何选择装入背包的物品，使得装入背 包中物品的总价值最大?输入：C&0, wi&0, vi&0, 1≤ i≤n 输出：(x1, x2, …, xn), xi∈{0, 1}, 满足17 0-1背包问题实例 (1)物品个数为 n=3 (2)背包的容量为 C=30 (3)物品的重量分别为 w={16，15，15} (4)物品的价值分别为 p={45，25，25} 问应如何选择装入背包的物品，使得装 入背包中物品的总价值最大?问题解空间： （x1,x2,x3） {(0,0,0),(0,1,0),(0,0,1),(1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1)}18解的形式 0-1背包问题问题解空间： （x1,x2,x3） {(0,0,0),(0,1,0),(0,0,1),(1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1)} 解空间树 解空间：子集树 可行性约束函数： ∑wixi≤C 上界函数： Bound() 算法：略19 0-1背包问题定义（子集树）部分解 当所给的问题是从n个元素的集合S中找出满足某种 性质的子集时，相应的解空间树称为子集树 子集树通常有 2n 个叶结点，结点总数为 2n+1-1 遍历解空间树需要 Ω(2n)的计算时间例如0-1背包问题：3个元素（x1,x2,x3），每个元素的集 合为{0，1}，搜索空间为：{(0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1)},状态有23=8种20 0-1背包问题问题： n=3，C=30，w={16，15，15}，p={45，25，25} 可行性约束函数： 解空间树――扩展结点，活结点，死结点 左儿子：xi=1 右儿子：xi=0(1,0,0) (0,1,1)21 0-1背包问题问题解空间： （x1,x2,x3） {(0,0,0),(0,1,0),(0,0,1),(1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1)} 解空间树――扩展结点，活结点，死结点(1,0,0) (0,1,1)22 回溯法的基本思想回溯法求解步骤1、针对所给问题，定义问题的解空间； 2、确定易于搜索的解空间结构； 3、以深度优先方式搜索解空间，并在搜索 过程中用剪枝函数避免无效搜索。 常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子 树； 用限界函数剪去得不到最优解的子树。23 回溯法的基本思想回溯法解题的一个显著特征是在搜索过 程中动态产生问题的解空间。 算法只保存从根结点到当前扩展结点的 路径。如果解空间树中从根结点到叶结点的最长路 径的长度为h(n)，则回溯法所需的计算空间 通常为O(h(n))。 显式地存储整个解空间则需要O(2h(n))或 O(h(n)!)内存空间。子集树 排列树24 0-1背包问题实例 (1)物品个数为 n=4 (2)背包的容量为 C=7 (3)物品的重量分别为 w={3，5，2，1} (4)物品的价值分别为 p={9，10，7，4}可行性约束函数 限界函数（上界函数）： Bound(i)25 0-1背包问题C=7 实例 贪心策略上界计算方法： 以物品单位重量价值的递减序排序id p w d=p/w sorted id4 4 1 4 [1]3 7 2 3.5 [2]1 9 3 3 [3] 4，3，1，22 10 5 2 [4]物品按照d的顺序装入――产生一个非可行解(上界)― x=[1,0.2,1,1], 价值2226 0-1背包问题限界函数(上界的计算方法) :r是当前尚未考虑的剩余物品价值总和,cp是 当前价值,bestp是当前最优价值. 当 cp+r&=bestp时,可剪去右子树 贪心策略计算方法：将剩余物品按照单位重 量价值排序,然后依次装入物品,直至装不下 时,再装入该物品的一部分而装满背包.该价 值是右子树中解的一个上界.27 递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递 归方法实现回溯法。 f(n,t) /g(n, t):在当 前扩展结点处未搜 void backtrack (int t) 索过的子树的起始 { 编号和终止编号 if (t&n) output(x); else for (int i=f(n,t);i&=g(n,t);i++) { h(i): 当前扩展结点处 x[t]=h(i); x[t]的第i个可选值 if (constraint(t)&&bound(t)) backtrack(t+1); } constraint()=true Bound()=true 在当 } 前扩展结点处x[1:t] 在当前扩展结点处x[1:t]取值满足约束 条件，否则剪枝 取值未使目标函数 越界，否则剪枝28 迭代回溯采用树的非递归深度优先遍历算法，可将回溯法表示为一个 非递归迭代过程。void iterativeBacktrack () { int t=1; F(n,t) /g(n, t):在当 while (t&0) { 前扩展结点处未搜 if (f(n,t)&=g(n,t)) 索过的子树的起始 for (int i=f(n,t);i&=g(n,t);i++) { 编号和终止编号 x[t]=h(i); if (constraint(t)&&bound(t)) { if (solution(t)) output(x); else t++;} } 是部分解,继续纵向 else t--; 搜索 } }29 回溯法剪枝策略Constraint(t):True:当前扩展结点处的取值满足问题的约束条 件 False:当前扩展结点处的取值不满足问题的约束 条件, 可剪去子树Bound(t):True:当前扩展结点处的取值未使目标函数越界 False:当前扩展结点处的取值已使目标函数越界, 可剪去子树30 旅行售货员问题给定n个顶点的带权图G=(V, E),图中各边 的权为正数，图中的一条周游路线是包 括V中的每个顶点在内的一条回路，一条 周游路线的费用是这条路线上所有边的 权之和。 旅行商问题(Traveling Salesperson)是要在 图G中找出一条有最小费用的周游路线。 此问题是NP完全问题。NP完全问题有一种令人惊奇的性质，即如果一个NP完 全问题能在多项式时间内得到解决，那么NP中的每一 个问题都可以在多项式时间内求解，即P=NP。 目前还没有一个NP完全问题有多项式时间算法。31 旅行售货员问题形式化描述设G=(V，E)是一个带权图，图中各条 边的耗费cij＞0。当(i,j)? E时，定义 cij=∞，设|V|=n＞1。图中的一条周游 路线是包括V中的每个节点在内的一条 有向回路。一条周游路线的耗费是这 条路线上所有边的耗费之和。所谓旅行售货员问题就是要在G中找 出一条有最小耗费的周游路线32 旅行售货员问题实例如: 三条周游路径(解空间)： [1,2,4,3,1] [1,3,2,4,1] [1,4,3,2,1] 1 6 3 20 30 5 4 4 2 1033 旅行售货员问题实例解空间树 A1 2 31 6 330 5 42 10 4B3 2204 4 2C4DE3F4G MH NI2 3J PK23 4最优解： 1，3，2，4，134LOQ 旅行售货员问题定义（排列树） 当所给的问题+是确定n个元素满足某种性质的 排列时，相应的解空间树称为排列树 排列树通常有 n! 个叶结点 遍历解空间树需要 Ω (n!)的计算时间 举例搜索空间为(1,2,3,…,n-1,n),(2,1,3,…,n-1,n), (2,3,1,…,n-1,n), (2,3,4,1,…,n-1,n), (n,n-1,…,3,2,2) 第1个元素有n种选择，第2个元素有n-1种选择,…,第 n个元素有1种选择，共n!个状态35 装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船， 其中集装箱i的重量为wi，且装载问题 确定是否有一个合理的装载方案可将这n个集装箱装上这2艘 轮船。如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略 可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。36 装载问题转换问题 将第一艘轮船尽量装满等价于选取全体集装箱的一个子集， 使该子集中集装箱重量之和最接近第一艘轮船的载重量。 由此可知，装载问题等价于以下特殊的0-1背包问题。用回溯法设计解装载问题的O(2n)计算时间算法。 在某些情况下该算法优于动态规划算法。37 装载问题可行性约束函数(选择当前元素) 上界函数(不选择当前元素)： 当前载重量cw + 剩余集装箱的重量r ≤ 当前最优载重量bestw 解空间树当前方案装的 太少了设Z是当前扩展结点,以 Z为根的子树中任一叶 子结点的载重量不超过 cw+r38 装载问题剪枝函数约束条件剪去”不可行解”的子树 上界条件剪去不含最优解的子树保证算法搜索到的每个叶结点都是迄今为止找到 的最优解39 批处理作业调度给定n个作业的集合{J1,J2,…,Jn}。 每个作业必须先由机器1处理，然后由机器2处理。 作业Ji需要机器j的处理时间为tji。 对于一个确定的作业调度，设Fji是作业i在机器j上完成处理 的时间。 所有作业在机器2上完成处理的时间和称为该作业调度的完 成时间和。 批处理作业调度问题 对于给定的n个作业，制定最佳作业调度方案，使其完成时 间和达到最小。40 批处理作业调度实例 tji 作业1 作业2 作业3 机器1 2 3 2 机器2 1 1 3解空间 这3个作业共有6种可能的调度方案 1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；41 批处理作业调度解空间树1 2tji作业1机器1机器2B2 13 3 1作业2 作业32 3 21 1 3C3DE2F3G M18H N20I1 2J P19K12 3L19O21Q19最佳调度方案是1,3,2，其完成时间和为18。42 n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国 际象棋的规则，皇后可以攻击与之处在同一行或同一列或同 一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个 皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 Q 1 Q 2 Q 3 Q 4 5 Q 6 Q Q 7 Q 8 1 2 3 4 5 6 7 843 n后问题实例 4皇后 解向量：(x1, x2, x3, x4) 解空间：44 ? 4! 种可能 显约束：xi=1,2, 3,4 1 2 3 4Q Q Q Q4隐约束： 1 2 3 1)不同列：xi≠xj 2)不处于同一正、反对角线(不处于同一斜线) |i-j|≠|xi-xj| 解空间树：4叉树排列树问题Xi: 皇后i放在棋盘的第i 行的X[i]列44 图的m着色问题给定无向连通图G和m种不同的颜色。用这些颜色为图G 的各顶点着色，每个顶点着一种颜色。是否有一种着色法 使G中每条边的2个顶点着不同颜色。这个问题是图的m可 着色判定问题。 若一个图最少需要m种颜色才能使图中每条边连接的2个 顶点着不同颜色，则称这个数m为该图的色数。求一个图 的色数m的问题称为图的m可着色优化问题。 1 4 3 2 1 5 2 5 3 445 图的m着色问题如果一个图的所有节点和边，都能用某 种方式画在一个平面上且没有任何两边 相交，则称这个图是平面图。 例如，图 (a) 是一个可平面图。因为它可 以画成如图 (b)的形式，实际上图a) 与图 b)同构。图6-6(c)就是不可平面图。46 平面图和不可平面图1 4 5 2 3(a) 可平面图4 1 2 3 5 6 8 7 9 107 6 8910(c) 不可平面图(b) 图(a)的同构47 图的m着色问题实例 5顶点，3着色 解向量：(x1, x2, x3, x4 , x5) 解空间：35种可能 显约束：xi=1,2, 3 隐约束： 顶点i与已着色的相邻顶点颜 色不重复 解空间树：3叉树 P144 a b d e c48 讨论回溯法是一种非常高效的技术吗?克服困难性. 至少可以对某些组合难题的较大实例求解. 最坏情况下,生成一个呈指数增长的状态空间中所有的 可能解 缩小状态空间树规模的技巧利用组合问题的对称性 把值预先分配给解的一个或多个分量 预排序49 回溯法效率分析通过前面具体实例的讨论容易看出，回溯算法的效率 在很大程度上依赖于以下因素： 由解空间结构确定 (1)产生x[k]的时间； 1,2,3 (2)满足显约束的x[k]值的个数； (3)计算约束函数constraint的时间； (4)计算上界函数bound的时间； (5)满足约束函数和上界函数约束的所有x[k]的个数。 好的约束函数能显著地减少所生成的结点数。但这样的 约束函数往往计算量较大。因此，在选择约束函数时通 常存在生成结点数与约束函数计算量之间的折衷。 对于许多问题而言，在搜索试探时选取x[i]的值顺序是任 意的。在其它条件相当的前提下，让可取值最少的x[i]优 先。 50 回溯法效率分析实例 图中关于同一问题的2棵不同解空间树剪去12个元组(a)剪去8个元组(b) 前者的效果明显比后者好51 回溯法效率分析回溯法的有效性O(p(n)2n)或O(q(n)n!) 当问题的规模较大时,也能用很少的时间求出问题的 解效率分析时的难点:生成结点的数目随问题的具体内容和结点的不同生 成方式而变动 同一问题的不同实例所产生的结点数也不同 对于问题的具体实例很难预测回溯法的算法行为,难 以估算解具体实例时产生的结点数52 回溯法效率分析如何估计出回溯算法的状态空间树的规模?概率方法:在解空间树上生成一条从根到一个叶子的随 机路径,并按照生成路径过程中不同选择的数 量信息,来估计树的规模. 设第i层的每个节点平均有ci个子女(满足约束 条件的子结点),则估计树中的结点数量为:1+c1+c1c2+…+c1c2…cn求所有解时,解空间中所有满足条 件的结点都必须生成53 回溯法效率分析蒙特卡罗(Monte Carlo)算法在一般情况下可以保证对问题的所有实例都 以高概率给出正确解,但是通常无法判定一个 具体解是否正确. 用于求问题的准确解 缺点:无法有效的判定所得到的解是否肯定 正确.54 回溯法效率分析提高估计的精确度选取若干条不同的随机路径(&20), 分别对各 随机路径估计结点总数,然后再取这些结点总 数的平均值55 总结回溯法主要用于以下困难的组合问题这些问题可能存在精确解,但无法用高效的算 法求解回溯法不同于穷举查找法 回溯法提供了一种有价值的解题方法56 总结理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架57
赞助商链接
算法设计与分析复习题目及答案_IT认证_资格考试/认证_教育专区。一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 A )实现的算法。 C、贪心法 ...算法设计与分析(第2版) 王红梅 胡明 习题答案_理学_高等教育_教育专区。算法设计与分析(第2版) 王红梅 胡明 课后答案 习题1 1. 图论诞生于七桥问题。 出生于...算法分析与设计 学习总结 题目:算法分析与设计学习总结 学专届 院业次 信息科学与工程学院 2013 级计算机应用技术 学生姓名 学号
二○一三年一月十五日...算法设计与分析教案_理学_高等教育_教育专区。《算法设计与分析》教案 张静 第1章 绪 论算法理论的两大论题: 1. 算法设计 2. 算法分析 1.1 1.1.1 算法...算法设计与分析考试题及答案_IT/计算机_专业资料。算法试题及答案 一、填空题(20 分) 填空题 1.一个算法就是一个有穷规则的集合, 其中之规则规定了解决某一...设计分治算法确定一个给定的整数 x 是否在 M 中,并分析算法的时间 复杂性。 12. 设 S 是 n(n 为偶数)个不等的正整数的集合,要求将集合 S 划分为子集 ...算法设计与分析课程论文 1.引言 算法设计与分析是数据结构的有力补充,从中可以了解到算法设计的奥妙以 及对数据结构中的数据存储结构更深层次的运用。 计算机算法...算法设计与分析学习心得班级:物联网 1201 姓名:刘潇 学号: 一、实验内容: 这学期的算法与设计课,老师布置了这四个问题,分别是货郎担问题,动态生成二维 ...算法设计与分析期末试卷A卷_工学_高等教育_教育专区。算法设计与分析试题A卷 一、选择题 1.二分搜索算法是利用(A )实现的算法。 A、分治策略 B、动态规划法 ...四川理工学院课程设计 算法设计与分析课程设计 学学专班 生: 号: 业:信息与计算科学 级:2012.2 指导教师:吴树林 四川理工学院理学院 一 、问题描述输入一列...
All rights reserved Powered by
www.tceic.com
copyright ©right 。文档资料库内容来自网络，如有侵犯请联系客服。
