《算法设计与分析》实验指导

1、算法分析与设计实验指导实验锦标赛问题实验目的1. 基本掌握分治算法的原理2. 能用程序设计语言求解锦标赛等问题的算法；预习要求1. 认真阅读数据结构教材和算法设计教材 ，了解分治算法原理；2. 设计用分治算法求解背包问题的数据结构与程序代码实验题【问题描述】设有 n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他 n-1个选手各赛一次；（2 ）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中 K i < n, 1w j

2、 w n-1。实验提示我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。MS丄1(1)1234214334124321123(2)12345678214367853412785643218567567814326587214378563214876543211234567(3)图12个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手

3、5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手 1至选手 4和选手 5至选手 8在后 4天的比赛日程。 依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 实验步骤 1. 设计并实现算法并准备测试用例 ,修改并调试程序 , 直至正确为止 ;2. 应用设计的算法和程序求锦标赛问题 ;3. 去掉测试程序 , 将你的程序整理成功能模块存盘备用 . 实验报告要求 1. 阐述实验目的和实验内容 ;2. 阐述分治算法原理 ;3. 提交实验程序的功能模块 ;4. 记录最终测试数据和测试结果

4、。 思考与练习 【金块问题】老板有一袋金块 （共n块，n是2的幕（n>=2 ）,将有两名最优秀的雇员 每人得到其中的一块， 排名第一的得到最重的那块， 排名第二的雇员得到袋子中最轻的金块。 假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。实验二 背包问题 实验目的 3. 能用程序设计语言实现求解背包问题的算法 ;4. 基本掌握动态规划法（贪心）的原理方法 . 预习要求 3. 认真阅读数据结构教材和算法设计教材 , 了解背包问题的常用算法原理 ;4. 设计用动态规划算法求解背包问题的数据结构和递归程序 . 实验题 【背包问题】 有不同价值、 不同重量的物品 n 件，求从这

5、 n 件物品中选取一部分物品的 选择方案，使选中物品的总重量不超过指定的限制重量W但选中物品的价值之和最大。 实验提示 设n件物品的重量分别为wo、w、wn-i，物品的价值分别为 vo、Vi、Vn-i。采用递归寻找物品的选择方案。 设前面已有了多种选择的方案， 并保留了其中总价值最大的方案 于数组option，该方案的总价值存于变量maxv。当前正在考察新方案，其物品选择情况保存于数组cop。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为 tw ；至此，若其余物品都选择是可能的话，本方案能达到 的总价值的期望值为 tv 。算法引入 tv 是当一旦当前

6、方案的总价值的期望值也小于前面方案 的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下 一个方案。因为当方案的总价值不比maxv大时，该方案不会被再考察，这同时保证函数后找到的方案一定会比前面的方案更好。对于第 i 件物品的选择考虑有两种可能：（1）考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行 的。选中后，继续递归去考虑其余物品的选择。（ 2） 考虑物品 i 不被选择，这种可能性仅当不包含物品 i 也有可能会找到价值更大的 方案的情况。按以上思想写出递归算法如下：try（物品i，当前选择已达到的重量和，本方案可能达到的总价值tv）/*

7、考虑物品 i 包含在当前方案中的可能性 */if（ 包含物品 i 是可以接受的 ） 将物品 i 包含在当前方案中；if （i<n-i）try（i+i,tw+ 物品 i 的重量 ,tv）;else/* 又一个完整方案，因为它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存 ;恢复物品 i 不包含状态；/*考虑物品i不包含在当前方案中的可能性*/if （不包含物品i仅是可男考虑的）if （i< n-1） try（i+1,tw,tv- 物品 i 的价值）;else/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/以当前方案作为临时最佳方案保存；为了理解上述算法

8、，特举以下实例。设有4件物品，它们的重量和价值见表:物品0123重量5321价值4431并设限制重量为7。则按以上算法，下图表示找解过程。由图知，一旦找到一个解，算法就 进一步找更好的佳。如能判定某个查找分支不会找到更好的解，算法不会在该分支继续查找,而是立即终止该分支，并去考察下一个分支。Try(1,5,12)超重Try(0,0,12)Try(1,0,8)ry(3,7,Try(2,5,不能得到更好的解得到解：(1,0,1,0)maxv=7得到解：（0,1,1,1）不能得到更好的解不能得到更好的解实验步骤4. 设计并实现算法并准备测试用例，修改并调试程序，直至正确为止5. 应用设计的算法和程序

9、求解背包问题；6. 去掉测试程序，将你的程序整理成功能模块存盘备用实验报告要求5. 阐述实验目的和实验内容 ;6. 阐述求解背包问题的算法原理7. 提交实验程序的功能模块 ;8. 记录最终测试数据和测试结果。 思考与练习 请用其它的算法（如贪心、分支限界等）求解背包问题。实验三 作业调度问题 实验目的 1. 熟悉多机调度问题的算法；2. 进一步掌握贪心算法3. 提高分析与解决问题的能力。 预习要求 1. 认真阅读教材或参考书 , 掌握贪心算法的基本思想；2. 写出求解“作业调度”的程序；3. 设计好测试用例。 实验题 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处

10、理完成。约定， 每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作 业不能拆分成更小的子作业。 实验提示 1. 把作业按加工所用的时间从大到小排序；2. 如果作业数目比机器的数目少或相等，则直接把作业分配下去；3 . 如果作业数目比机器的数目多， 则每台机器上先分配一个作业， 如下的作业分配时， 是选那个表头上 s 最小的链表加入新作业。typedef struct Jobint ID;/ 作业号int time;/ 作业所花费的时间Job;typedef struct JobNode / 作业链表的节点 int ID;int time;JobNode *next; JobNo

11、de,*pJobNode;typedef struct Header/ 链表的表头int s; pJobNode next;Header,pHeader;int SelectMin(Header* M,int m)int k=0;for(int i=1;i<m;i+) if(Mi.s<mk.s)k=i;return k; 实验步骤 1 先用贪心算法求解该问题，并测试你的程序，直至正确为止；2 针对问题实例，实录运行时的输入、输出文件；3 将你的程序和实录的界面存盘备用。 实验报告要求 阐述实验目的和实验内容；1 提交模块化的实验程序源代码；2 简述程序的测试过程，提交实录的输入、输

12、出文件；3 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。实验四 回溯算法设计 实验目的 1. 掌握回溯法解题的基本思想；2. 掌握回溯算法的设计方法；3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。 预习要求 1. 认真阅读教材或参考书 , 掌握回溯法解题的基本思想 , 算法的抽象控制策略；2. 了解子集和数问题及解向量的定长和变长状态空间表示；3. 针对解向量的定长表示 , 设计状态空间树节点扩展的规范 （限界） 函数及实现方法；4. 分析深度优先扩展状态空间树节点或回溯的条件；5. 分析和设计生成解向量各分量可选值的实现方法；6. 设计和编制回溯算法的

13、递归和迭代程序。 实验题 【组合数】找出从自然数 1, 2，n中任取r个数的所有组合。 实验提示 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候 选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满 足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。 在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解 的规模，以继续试探的过程称为向前试探。可以采用回溯法找问题的解， 将找到的组合以从小到大顺序

14、存于 a0 ，a1 ， ar-1 中，组合的元素满足以下性质：（1 ）ai+1>ai ，后一个数字比前一个大；（2）ai-i<=n-r+1。按回溯法的思想，找解过程可以叙述如下：首先放弃组合数个数为 r 的条件，候选组合从只有一个数字1 开始。因该候选解满足除问题规模之外的全部条件，扩大其规模，并使其满足上述条件（1），候选组合改为 1， 2。继续这一过程，得到候选组合 1 ， 2， 3。该候选解满足包括问题规模在内的全部条件，因而 是一个解。在该解的基础上，选下一个候选解，因 a2 上的 3 调整为 4，以及以后调整为 5 都满足问题的全部要求，得到解 1， 2， 4和 1， 2

15、， 5。由于对 5不能再作调整，就要从 a2 回溯到 a1 ，这时， a1=2 ，可以调整为 3，并向前试探，得到解 1 ， 3， 4。重复上述向前 试探和向后回溯，直至要从 a0 再回溯时，说明已经找完问题的全部解。按上述思想写成 程序如下：void comb(int n,int r) int i,j; i=0; ai=1;do if (ai-i<=n-r+1)/* 还可以向前试探 */ if (i=r-1)/* 已找到一个组合 */ for (j=0;j<r;j+) printf(“ %4d” ,aj); printf(“ n ” );ai+; continue;i+;ai =

16、 ai-1 + 1; /*向前试探 */ else if (i=0) return;/* 已找到所有解 */a-i+; /*回溯*/while (1); 实验步骤 1. 录入、修改并测试你的程序，直至正确为止；2. 针对问题实例，实录运行时的输入、输出界面；3. 将你的程序和实录的界面存盘备用。 实验报告要求 1. 阐述实验目的和实验内容；2. 提交模块化的实验程序源代码；3. 简述程序的测试过程，提交实录的输入、输出界面；4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。 思考与练习 1. 在3X 3个方格的方阵中要填入数字 1到N ( N > 10)内的某9个数字，

17、每个方格填 一个整数， 似的所有相邻两个方格内的两个整数之和为质数。 试求出所有满足这个要求的各 种数字填法。2. 试针对 0/1 背包问题设计回溯算法，比较与子集和数问题的算法差异。3. 求出在一个nxn的棋盘上，放置n个不能互相捕捉的国际象棋"皇后”的所有布局。实验五 旅行商问题 实验目的 1 掌握分支限界法算法的解题的基本思想和设计方法；2 区分分支限界算法与回溯算法的区别，加深对分支限界法的理解；3 理解分支限界法算法中的限界函数应遵循正确、准确、高效的设计原则。 预习要求 1 认真阅读教材或参考书 , 掌握分支限界法解题的基本思想； 2设计状态空间树节点扩展的规范 （限界）

18、 函数及实现方法；3 分析和设计生成解向量各分量可选值的实现方法。 实验题 某售货员要到若干城市去推销商品， 已知各城市之间的路程 （或旅费 ） 。他要选定一条从 驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程 （或总旅费 ） 最小。 设计提示 用分支限界求解旅行商问题， 其解空间是一个排列树。 有两种基本的实现方法。 第一种 是只使用一个优先队列， 队列中的每个元素中都包含到达根的路径。 另一种是保留一个部分 解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。 参考数据类型或变量 /* 定义边结构 */ typedef struct _EDGE int head; i

19、nt tail; EDGE;/* 定义路径结构 */ typedef struct _PATH EDGE edgeMAX_CITIES;int edgesNumber; PATH;/* 定义花费矩阵结构 */ typedef struct _MATRIX int distanceMAX_CITIESMAX_CITIES;int citiesNumber; MATRIX;/* 定义树结点 */typedef struct _NODE int bound;/相应于本结点的花费下界MATRIX matrix; /当前花费矩阵PATH path;/已经选定的边struct _NODE* left; /

20、左枝struct _NODE* right; /右枝 NODE; 参考子程序接口与功能描述 int Simplify(MATRIX* c)功能：归约费用矩阵，返回费用矩阵的归约常数EDGE SelectBestEdge(MATRIX c)功能： 搜索所有花费为零的边中最合适的，使左枝下界更大MATRIX LeftNode(MATRIX c, EDGE edge)功能： 删掉所选分枝边MATRIX RightNode(MATRIX c, EDGE edge, PATH path)功能： 删除行列和回路边后的矩阵EDGE LoopEdge(PATH path, EDGE edge)功能： 计算回路

21、边的函数，除了加入的新边，当前结点路线集合中还可能包含一些已 经选定的边， 这些边构成一条或几条路径， 为了不构成回路， 必须使其中包含新边的路 径头尾不能相连，本函数返回这个头尾相连的边，以便把这个回路边的长度设成无穷。int MatrixSize(MATRIX c, PATH path)功能： 计算花费矩阵当前阶数void ShowPath(PATH path, MATRIX c)功能：显示路径void ShowMatrix(MATRIX c)功能： 显示花费矩阵 实验步骤 1 录入、修改并测试你的程序，直至正确为止；2 针对问题实例，实录运行时的输入、输出界面；3 将你的程序和实录的界面

22、存盘备用。 实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；4 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。 思考与练习 1 试针对作业调度问题设计分支限界算法，并上机测试其正确性。2 试对本实验中的问题，用回溯解法求解，并比较这两种算法的区别与执行效率。附：实验（设计）报告参考格式设计一多段图问题的动态规划算法与实现一、实验目的1. 掌握有向网的成本邻接矩阵表示法；2. 掌握多段图问题的动态规划递推算法；3. 进一步掌握动态规划法的基本思想和算法设计方法；二、实验内容1 任务描述1）多段图问题简介 2）设计任务简介设计求解多段图问题的动态规划算法，即设计和实现多段图问题的表示方案、动态 规划递推算法，设计对算法或程序的测试方案并完成测试。2 多段图问题的表示方案本设计采用成本邻接矩阵表示多段图， 针对多段图 （可插入图例 ） 描述成本邻接矩阵 的规模与元素意义 3 递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设