没有合适的资源?快使用搜索试试~ 我知道了~
算法设计与分析试题1.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 117 浏览量
2022-05-08
12:25:16
上传
评论
收藏 1.05MB DOC 举报
温馨提示
试读
17页
算法设计与分析试题1.doc
资源推荐
资源详情
资源评论
算法设计与分析试题
一、 对于下图使用 Dijkstra 算法求由顶点 a 到顶点 h 的最短路
径。
解:用
表示已经找到最短路径的顶点,
表示与
中某个顶点相邻接且不
在
中的顶点;
表示加入到最短路径中的边,
为与
中的顶点相邻接且
距离最短的路径。【 分】
步骤
【以上每
步 分】
结果:从 到 的最短路径为 ,权值为 。【
分】
求所有顶点对之间的最短路径可以使用 算法,使其起始节点从
循环到 ,每次求起始节点到其他节点的最短路径,最终可以求得所有顶点
对之间的最短路径。【 分】
二、 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且
背包容量 M=150,使用回溯方法求解此背包问题。请写出状态空间搜索树。
1
物
品
! " #
重
量
3
5
3
0
6
0
5
0
4
0
1
0
2
5
价
值
1
0
4
0
3
0
5
0
3
5
4
0
3
0
解:按照单位效益从大到小依次排列这 个物品为:" #!。将它们的序
号分别记为 ~。则可生产如下的状态空间搜索树。其中各个节点处的限界函
数值通过如下方式求得:【排序 分】
【状态空间搜索树及其计算过程 分,
每个节点 分】
.
2
.
在 $
处获得该问题的最优解为 ,背包效益为 %。即在背包中装
入物品 "、 、#、、 时达到最大效益,为 %,重量为 %。【结论
分】
三、 已 知
k=1,2,3,4,5,6,r
1
=5,r
2
=10,r
3
=3,r
4
=12,r
5
=5
,r
6
=50,r
7
=6,求矩阵链积 A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求
积顺序。(要求:给出计算步骤)
解:使用动态规划算法进行求解。
求解矩阵为:【每个矩阵 分】
% % % % %%
% % % % &%
% % &% %
3
% %%% %
% %%
%
因此,最佳乘积序列为(
)((
)(
)),共执行乘法 %%
次。【结论 分】
四、回答如下问题:
(1) 什么是算法?算法的特征有哪些?
(2) 什么是 P 类问题?什么是 NP 类问题?请描述集合覆盖问
题的近似算法的基本思想。
解:()算法是解决某类问题的一系列运算的集合【 分】。具有有穷行、可
行性、确定性、% 个或者多个输入、 个或者多个输出【 分】。
()用确定的图灵机可以在多项式实践内可解的判定问题称为 ' 类问题【
分】。用不确定的图灵机在多项式实践内可解的判定问题称为 ' 类问题。【
分】
集合覆盖问题的近似算法采用贪心思想:对于问题()"*,每次选择 " 中
覆盖了尽可能多的未被覆盖元素的子集 +,然后将 , 中被 + 覆盖的元素删除,
并将 + 加入 ! 中,最后得到的 ! 就是近似最优解。【 分】
五、排序和查找是常用的计算机算法。按照要求完成以下各题:
(1) 对 数 组
%
%
%
%
%
%
4
剩余16页未读,继续阅读
资源评论
- 逝水残影2023-02-04资源内容详尽,对我有使用价值,谢谢资源主的分享。
老帽爬新坡
- 粉丝: 81
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功