算法设计与分析：回溯法-实验报告_计算机-数据结构与算法.pdf

《算法设计与分析：回溯法-实验报告_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析：回溯法-实验报告_计算机-数据结构与算法.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-优质专业-应用数学 学院 信息安全 专业 班 学号 实验题目 回溯算法 实验评分表 指导教师评分标准 序号 评分项目 评分标准 满分 打分 1 完成度 按要求独立完成实验准备、程序调试、实验报告撰写。20 2 实验容（1）完成功能需求分析、存储结构设计；（2）程序功能完善、可正常运行；（3）测试数据正确，分析正确，结论正确。30 3 实验报告 容齐全，符合要求，文理通顺，排版美观。40 4 总结 对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10-优质专业-实验报告 一、实验目的与要求 1、理解回溯算法的基本思想；2、掌握回溯算法求解问题的基本步骤；3、了解

2、回溯算法效率的分析方法。二、实验容【实验容】最小重量机器设计问题：设某一个机器有 n 个部件组成，每个部件都可以 m 个不同供应商处购买，假设已知 表示从 j 个供应商购买第 i 个部件的重量，表示从 j 个供应商购买第 i 个部件的价格，试用回溯法求出一个或多个总价格不超过 c 且重量最小的机器部件购买方案。【回溯法解题步骤】1、确定该问题的解向量及解空间树；2、对解空间树进行深度优先搜索；3、再根据约束条件（总价格不能超过 c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。4、达到叶结点时记录下当前最优解。5、实验数据 n,m,j i w,j i c的值由自己假设。三、算法思想和实

3、现【实现代码】准完成度按要求独立完成实验准备程序调试实验报告撰写实验容完成功能需求分析存储结构设计程序功能完善可正常运行测试数据正确分析正确结论正确实验报告容齐全符合要求文理通顺排版美观总结对实验过程遇到的问题能初步 思想掌握回溯算法求解问题的基本步骤了解回溯算法效率的分析方法二实验容实验容最小重量机器设计问题设某一个机器有个部件组成每个部件都可以个不同供应商处购买假设已知表示从个供应商购买第个部件的重量表示从个供应 确定该问题的解向量及解空间树对解空间树进行深度优先搜索再根据约束条件总价格不能超过和目标函数机器重量最小在搜索过程中剪去多余的分支到叶结点时记录下当前最优解实验数据的值由自己假设

4、三算法思想和实现实现代码-优质专业-准完成度按要求独立完成实验准备程序调试实验报告撰写实验容完成功能需求分析存储结构设计程序功能完善可正常运行测试数据正确分析正确结论正确实验报告容齐全符合要求文理通顺排版美观总结对实验过程遇到的问题能初步 思想掌握回溯算法求解问题的基本步骤了解回溯算法效率的分析方法二实验容实验容最小重量机器设计问题设某一个机器有个部件组成每个部件都可以个不同供应商处购买假设已知表示从个供应商购买第个部件的重量表示从个供应 确定该问题的解向量及解空间树对解空间树进行深度优先搜索再根据约束条件总价格不能超过和目标函数机器重量最小在搜索过程中剪去多余的分支到叶结点时记录下当前最优解

5、实验数据的值由自己假设三算法思想和实现实现代码-优质专业-【实验数据】假设机器有 3 个部件，每个部件可由 3 个供应商提供（n=3，m=3）。总价不超过 7（c=7）。部件重量表：重量 供应商 1 供应商 2 供应商 3 部件 1 2 3 3 部件 2 1 2 2 部件 3 3 4 1 部件价格表：价格 供应商 1 供应商 2 供应商 3 部件 1 2 3 3 部件 2 1 3 1 部件 3 1 1 3【运行结果】准完成度按要求独立完成实验准备程序调试实验报告撰写实验容完成功能需求分析存储结构设计程序功能完善可正常运行测试数据正确分析正确结论正确实验报告容齐全符合要求文理通顺排版美观总结对实

6、验过程遇到的问题能初步 思想掌握回溯算法求解问题的基本步骤了解回溯算法效率的分析方法二实验容实验容最小重量机器设计问题设某一个机器有个部件组成每个部件都可以个不同供应商处购买假设已知表示从个供应商购买第个部件的重量表示从个供应 确定该问题的解向量及解空间树对解空间树进行深度优先搜索再根据约束条件总价格不能超过和目标函数机器重量最小在搜索过程中剪去多余的分支到叶结点时记录下当前最优解实验数据的值由自己假设三算法思想和实现实现代码-优质专业-实验结果：选择供应商 1 的部件 1、供应商 1 的部件 2、供应商 3 的部件 3，有最小重量机器的重量为 4，总价钱为 6。四、问题与讨论 影响回溯法效率

7、的因素有哪些？答：影响回溯法效率的因素主要有以下这五点：1、产生 xk 的时间；2、满足显约束得 xk 值的个数；3、计算约束函数 constraint 的时间；4、计算上界函数 bound 的时间；5、满足约束函数和上界函数约束的所有 xk 的个数。五、总结 这次实验的容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井准完成度按要求独立完成实验准备程序调试实验报告撰写实验容完成功能需求分析存储结构设计程序功能完善

8、可正常运行测试数据正确分析正确结论正确实验报告容齐全符合要求文理通顺排版美观总结对实验过程遇到的问题能初步 思想掌握回溯算法求解问题的基本步骤了解回溯算法效率的分析方法二实验容实验容最小重量机器设计问题设某一个机器有个部件组成每个部件都可以个不同供应商处购买假设已知表示从个供应商购买第个部件的重量表示从个供应 确定该问题的解向量及解空间树对解空间树进行深度优先搜索再根据约束条件总价格不能超过和目标函数机器重量最小在搜索过程中剪去多余的分支到叶结点时记录下当前最优解实验数据的值由自己假设三算法思想和实现实现代码-优质专业-有条的、能避免不必要重复搜索的穷举式搜索算法。我非常喜欢上机课，因为课上听

9、的理论容也许觉得懂了，但课后没有一些实践，于是对一些难点实际上掌握得并不好。刚看到课题的实验容，其实基本思路和条理还是会有的，因为会有一定的知识基础，能够想到一些相关的解决思路，但有思路不一定就能够解决问题，真正动手去做的时候才发现会出现更多的实际问题。解决遇到的问题就是我们学习的过程，同时也能让我注意到一些以前不曾在意的问题。像我是使用 C+来写代码的，每次出现 BUG 我都能够积累一些经验。其中我这次实验时我就出现了这样一个问题：通过查找资料我才发现，是工程设置的问题。我在工程设置里面，把/subsystem后的 windows 改成 console，就可以正常运行了。于是我又更加深入的了

10、解到，/subsystem 连接器参数，用来指定程序的入口函数，可以指定四种方式：“CONSOLE|WINDOWS|NATIVE|POSIX”如果这个选项参数的值为“WINDOWS”，则表示该应用程序运行时不需要控制台。而我建立的是 win32 字符模式应用程序，需要产生控制台窗口，所以应该指定方式为 console。每次的实践都能有一些发现，不管是大是小，积累多了就成了自己丰富的经验。所以我还是挺喜欢实验课的，能进行一些实用性很强的实践，更深层地领悟到书本的理论知识，同时还能享受把 bug 逐个解决的快感。准完成度按要求独立完成实验准备程序调试实验报告撰写实验容完成功能需求分析存储结构设计程序功能完善可正常运行测试数据正确分析正确结论正确实验报告容齐全符合要求文理通顺排版美观总结对实验过程遇到的问题能初步 思想掌握回溯算法求解问题的基本步骤了解回溯算法效率的分析方法二实验容实验容最小重量机器设计问题设某一个机器有个部件组成每个部件都可以个不同供应商处购买假设已知表示从个供应商购买第个部件的重量表示从个供应 确定该问题的解向量及解空间树对解空间树进行深度优先搜索再根据约束条件总价格不能超过和目标函数机器重量最小在搜索过程中剪去多余的分支到叶结点时记录下当前最优解实验数据的值由自己假设三算法思想和实现实现代码