贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告
课程名称：算法设计与分析 班级：信计101班 姓名：张 胜 实验序号：四 学号：1007010162 实验日期：2013-11-25 指导教师：程欣宇 实验成绩： 一、实验名称 回溯算法实验 - 频道分配问题 二、实验目的及要求 1、使用在线测评的算法题目评分系统来测试所写代码； 2、通过直观的应用问题，加深对回溯算法的理解； 三、实验环境 任意C或C++编写调试工具，北京大学ICPC在线测评系统POJ 四、实验内容 1、登陆POJ系统，找到题号为1129的题目-频道分配； 2、阅读题目，分析出求解该问题的思路； 3、使用回溯算法，实现本题； 4、进行简单测试，完成之后提交到POJ系统。 五、算法描述及实验步骤 回溯算法原理： 回溯法是一个既带有系统性又带有跳跃性的搜索算法，用它可以系统地搜索一个问题的所有解或任一解。它在问题的解空间树中，按深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。 回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已经被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。 频道分配问题描述： 当一个无线站广播覆盖一个非常大的区域时，需要使用转发器转发增强信号。然而，每个转发器使用的频道数必须仔细的选择，以使得相邻的转发器之间不会相互干扰。它们相互不干扰的条件是相邻的转发器使用不同的频道。 因为无线频谱是非常稀有的资源，因此，所给的转发器网络使用的频道数量必须最小化。你需要写一个程序读出转发器网络的描述，然后算出最小需要的频道数量。 注意：邻接关系具有对称性，如果A邻接B，则B邻接A。另外，因为转发器网络是平面的，所以通道不会交叉。 输入 输入由若干转发器网络的地图组成。每个地图的第一个行是转发器数量（1至26，用0表示输入结束）。每个转发器由字母A至Z标识，每行列出和一个转发器邻接的相邻转发器。 输出 对于每一个转发器网络地图，输出最少占用的频道数量（注意单复数）。 例子输入 2 A: B: 4 A:BC B:ACD C:ABD D:BC 4 A:BCD B:ACD C:ABD D:ABC 0 例子输出 1 channel needed. 3 channels needed. 4 channels needed. 实验步骤： 1、建立频道分配问题的解题思路 1、建立频道分配问题的解题思路 首先构建回溯算法的基本框架，对每输入的若干转发器网络的地图（行数：lines）,都对其所有可能的路径进行比较，找出相邻路径不同的组合即可。 2、构造算法框架 构造频道分配问题回溯算法如下： ① 回溯算法实现 void backtrack(int x) { if(x == lines) { int get=0; for(int i=0;i