货郎担问题(或称旅行商问题或巡回售货员问题)，是np问题中的著名问题。它通常的提法是：货郎到各村去卖货，再回到出发点处，每村到且仅到一次。为其设计一种路线，使得所用旅行售货的时间最短。

建立数学模型时，把村庄设为结点，村庄与村庄之间的路线设为结点之间的

【篇二：《算法分析与设计》实验指导书】

txt>一、实验目的

《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。

要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用c++实现所涉及的算法，并尽量做到低复杂度，高效率。 通过本课程的实验，使学生加深对课程内容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。

希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。 二、实验要求

《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析实验》课程教学大纲要求的内容。

在《算法设计与分析实验》课程实验过程中，要求学生做到：

（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。

（2）认真书写实验报告。

（3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。

（4）实验课程不迟到。如有事不能出席，所缺实验一般不补。 （5）本实验采用的开发环境为 microsoft visual c++ 6.0，同学在做实验之前要求熟悉该软件的使用方法。

（6）实验成绩主要从以下几方面考核：实验过程态度，实验结果及实验报告书写。

上机准备和上机调试

上机准备包括以下几个方面：

(1) 注意同一高级语言文本之间的差别。

(2)熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。

(3)掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。应该能够熟练运用高级语言的程序调试器dbbug调试程序。 (4)上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层函数。在调试过程中可以不断借助debug的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 总结和整理实验报告

实验结束后，要整理实验结果并认真分析和总结， 根据教师要求写出实验报告。

实验报告一般包括如下内容： [1] 实验内容 [2] 实验目的 [3] 程序清单 [4] 调试步骤

[5] 运行结果：原始数据，相应的运行结果和必要的说明。 [6]分析与思考

调试过程及调试中遇到的问题及解决办法;调试程序的心得与体会;其他算法的存在与实践等。 若最终未完成调试， 要认真找出错误并分析原因等。

实验一、利用分治算法，编程实现循环赛日程表安排问题 【实验学时】 4学时

【实验目的】

1．深刻理解并掌握“分治算法”的设计思想； 2．提高应用“分治算法”设计技能；

3．理解这样一个观点：用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。 【问题描述】

设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次; （3）循环赛一共进行n-1天.

按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时。 【基本要求】

1．实现《网球循环赛》问题的分治算法，并进行算法时间复杂性分析。

2．对实现的分治算法进行改进；

3．对上述改进后算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。

4. 设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用c＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 【基本步骤】

（1） 仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取

合适的存储结构实现应用的操作。

（2） 设计的结果应在visual c++ 实验环境下实现并进行调试。 （3） 实验要有详细的测试记录，包括各种可能的测试数据。 实验二 利用动态规划算法编程求解0-1背包问题 【实验学时】 4学时

【实验目的】

（1） 熟练掌握动态规划思想及教材中相关经典算法。

（2） 掌握动态规划算法求解问题的一般特征和步骤；使用动态规划法编 程，求解0/1背包问题。 【问题描述】

0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1,

v2, … ,vn}的物品和一个容量为c的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，

xi=1时，表示物品i被装入背包。0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确

定了(x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量

不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，

则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。

举例: 若商店一共有5类商品，重量分别为：3，4，7，8，9 价值分别为：4，5，10，11，13 则所选商品的最大价值为24 ,所选商品的一个序列为：0001 1 【基本要求】

进行算法时间复杂性分析。

3．对算法进行时间复杂性分析，通过实验结果分析对比，得出自己的结论和总结。

4. 设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用c＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。 【基本步骤】

（1） 仔细阅读实验要求，设计好输入输出，按照动态规划法的思想构思算法，选取合适的存储结构实现应用的操作。

（2） 设计的结果应在visual c++ 实验环境下实现并进行调试。 （3） 实验要有详细的测试记录，包括各种可能的测试数据。 实验三 利用贪心算法编程求解背包问题和 tsp问题 【实验学时】 6学时