应用数学 学院 信息安全 专业 班 学号 姓名
实验题目 回溯算法
实验评分表
序评分项目 号 1 完成度 指导教2 实验内容 师评分标3 实验报告 准 4
总结 评分标准 按要求独立完成实验准备、程序调试、实验报告撰写。 （1） 完成功能需求分析、存储结构设计； （2） 程序功能完善、可正常运行； （3） 测试数据正确，分析正确，结论正确。 满分 20 打分 30 内容齐全，符合要求，文理通顺，排版美观。 40 对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。 10 实验报告
一、实验目的与要求
1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。
二、实验内容
【实验内容】
最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知 表示从j个供应商购买第i个部件的重量， 表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】
1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索；
3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。
4、达到叶结点时记录下当前最优解。
5、实验数据n,m, w[i][j],c[i][j]的值由自己假设。
三、算法思想和实现
【实现代码】
【实验数据】
假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。 总价不超过7（c<=7）。 部件重量表： 重量 部件1 部件2 部件3 部件价格表： 价格 部件1 部件2 部件3
【运行结果】
供应商1 2 1 1 供应商2 3 3 1 供应商3 3 1 3 供应商1 2 1 3 供应商2 3 2 4 供应商3 3 2 1
实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。
四、问题与讨论
影响回溯法效率的因素有哪些？
答：影响回溯法效率的因素主要有以下这五点：
1、产生x[k]的时间；
2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间；
5、满足约束函数和上界函数约束的所有x[k]的个数。
五、总结
这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。
回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井
算法设计与分析：回溯法-实验报告
