首页
题目
学科
试卷
登入
注册
首页
题目
详情
解空间树的动态搜索。
问答题
2019-08-09 16:41:49
0
157
参考答案:(1)回溯求解0/1背包问题,虽剪枝减少了搜索空间,但整个搜索按深度优先机械进行,是盲目搜索(不可预测本结点以下的结点进行的如何)。(2)回溯求解TSP也是盲目的(虽有目标函数,也只有找到一个可行解后才有...
查看答案
参考答案
科目:
算法与数据分析
学科:
计算机科学与技术
感兴趣题目
分支限界法与回溯法的不同。
排列树问题:设计一个用队列式分支限界法搜索排列树树的函数。该函数得参数包括结点可行性判定函数和上界函数。
子集树问题:设计一个用队列式分支限界法搜索子集树的函数。该函数得参数包括结点可行性判定函数和上界函数。
最佳调度问题:假设有n个任务由k个可并行工作的机器来完成。完成任务i需要的时间是 。设计一个算法完成这n个任务的最佳调度,使得完成全部任务的时间最早。
子集和问题:设 是n个正整数的集合,c是一个正整数。那么是否存在S的一个子集S1,使得子集中元素之和等于c,即
虑分数背包问题,定义如下:给出n 个大小为 s1, s2, …, sn , 价值为v1, v2, …, vn 的物品, 并设背包容量为C, 要找到非负实数x1, x2, …, xn, 使和 在约束 下最大。写出求解问题的贪心算法,估计算法的时间复杂性。
最优分解问题:设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和,使得这些自然数的乘积最大。设计一个算法,得到最优分解方案。
最优服务次序问题:设有n个顾客同时等待一项服务。顾客i需要的服务时间为 。应该如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间等于n个顾客服务时间的总和除以n。对于给定的n个顾客需要的服务时间,计算最优服务次序。
会场安排问题:假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动,计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间,分别表示为b(i),f(i)。
记矩阵连乘积 。 确定计算A[1:n]的最优计算次序,使得所需数乘的次数最少。1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解,即最优子结构性质。2、该问题具备子问题的重叠性质。3、说明采用动态规划方法可以解决该问题。4、设计该算法,分析算法的复杂性。
设序列 是序列 X=和Y=的最长公共子序列。a) 请说明最长公共子序列具有最优子结构性质。b) 设c[i][j]记录序列 i和 的最长公共子序列的长度。由最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。 c) 写出寻找最长公共子序列的算法。
定义函数设计一个计算A(m,n)的动态规划算法,该算法之占用O(m)空间。
相关题目
网络银行一定是完全依赖网络的银行。这种说法____
最为常用的路由协议有()。
当浏览器终止Applet时,()函数被调用。
()阶段要做的工作是将需求分析得到的用户需求抽象为反映用户观点的概念模型。
在Windows操作系统中可以通过安装()组件创建FTP站点。
目录XYZ的访问控制列表配置成:每个人:(RX)(RX);管理员:(ALL)(ALL)位于XYZ目录中的文件ABC有如下权限:每个人:(RWXD)用户X既没有被直接授予也没有被直接拒绝权限,用户X对文件ABC有效的权限是什么()。
系列机不再是方向,因为它约束了计算机系统结构的发展。
若某机器数为10000000,它代表-127,则它是()
计算机的所有计算都是在内存中进行的。
若想快速的将一个Excel数据表格的行、列交换,可以
微程序放在______中。
下面说法错误的是()
判定覆盖又叫()
()是指准备测试环境、获得测试数据、开发测试规程,以及为该过程挑选和准备辅助测试工具的过程
VI设计的原则包括()
这里可作为广告区域
专业远程教育题库
微信扫码关注 无忧题库 公众号