算法设计与分析：回溯法-实验报告.pdf

真诚为您提供优质参考资料，若有不当之处，请指正。

应用数学学院信息安全专业班学号

姓名

实验题目回溯算法

实验评分表

序
评分项目评分标准满分打分
号

1完成度按要求独立完成实验准备、程序调试、实验报告撰写。20
指
导（1）完成功能需求分析、存储结构设计；
教（2）程序功能完善、可正常运行；
2实验内容30
师（3）测试数据正确，分析正确，结论正确。
评
分
标3实验报告内容齐全，符合要求，文理通顺，排版美观。40
准

对实验过程遇到的问题能初步独立分析，解决后能总
4总结10
结问题原因及解决方法，有心得体会。

1/6
真诚为您提供优质参考资料，若有不当之处，请指正。

实验报告

一、实验目的与要求

1、理解回溯算法的基本思想；

2、掌握回溯算法求解问题的基本步骤；

3、了解回溯算法效率的分析方法。
二、实验内容

【实验内容】

最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同

供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应

商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机

器部件购买方案。

【回溯法解题步骤】

1、确定该问题的解向量及解空间树；

2、对解空间树进行深度优先搜索；

3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程

中剪去多余的分支。

4、达到叶结点时记录下当前最优解。

w[i][j]c[i][j]
5、实验数据n,m,,的值由自己假设。
三、算法思想和实现

【实现代码】

2/6
真诚为您提供优质参考资料，若有不当之处，请指正。

3/6
真诚为您提供优质参考资料，若有不当之处，请指正。

【实验数据】

假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。

总价不超过7（c<=7）。

部件重量表：

重量供应商1供应商2供应商3

部件1233

部件2122

部件3341

部件价格表：

价格供应商1供应商2供应商3

部件1233

部件2131

部件3113

【运行结果】

4/6
真诚为您提供优质参考资料，若有不当之处，请指正。

实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小

重量机器的重量为4，总价钱为6。

四、问题与讨论

影响回溯法效率的因素有哪些？

答：影响回溯法效率的因素主要有以下这五点：

1、产生x[k]的时间；

2、满足显约束得x[k]值的个数；

3、计算约束函数constraint的时间；

4、计算上界函数bound的时间；

5、满足约束函数和上界函数约束的所有x[k]的个数。

五、总结

这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地

领悟到了回溯算法的思想。

回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不

能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

5/6
真诚为您提供优质参考资料，若有不当之处，请指正。

有条的、能避免不必要重复搜索的穷举式搜索算法。

我非常喜欢上机课，因为课上听的理论内容也许觉得懂了，但课后没有一些实践，

于是对一些难点实际上掌握得并不好。刚看到课题的实验内容，其实基本思路和条理还

是会有的，因为会有一定的知识基础，能够想到一些相关的解决思路，但有思路不一定

就能够解决问题，真正动手去做的时候才发现会出现更多的实际问题。解决遇到的问题

就是我们学习的过程，同时也能让我注意到一些以前不曾在意的问题。像我是使用C++

来写代码的，每次出现BUG我都能够积累一些经验。其中我这次实验时我就出现了这样

一个问题：

通过查找资料我才发现，是工程设置的问题。我在工程设置里面，把/subsystem

后的windows改成console，就可以正常运行了。于是我又更加深入的了解到，

/subsystem连接器参数，用来指定程序的入口函数，可以指定四种方式：“CONSOLE|

WINDOWS|NATIVE|POSIX”如果这个选项参数的值为“WINDOWS”，则表示该应用程序

运行时不需要控制台。而我建立的是win32字符模式应用程序，需要产生控制台窗口，

所以应该指定方式为console。

每次的实践都能有一些发现，不管是大是小，积累多了就成了自己丰富的经验。所

以我还是挺喜欢实验课的，能进行一些实用性很强的实践，更深层地领悟到书本的理论

知识，同时还能享受把bug逐个解决的快感。

6/6