算法设计与分析实验报告
学号
姓名 教师 庄蔚蔚 班级 上课时间 上课地点 实验4 分支限界 1. 实验目的 1.1．掌握分支限界法的基本思路 1.2．掌握用分支限界法分析和处理货郎担问题和0/1背包问题 2. 实验环境 2.1 VC6.0 2.2 Window XP 3. 实验内容 3.1 圆排列问题 3.1.1 算法设计思想 自己没想出来，倒是看懂了百度的算法思想，我来简述一下（看明白后自己理解的手打，不知道对不对） 首先圆a、b、c假设三个圆 我们不能下意识认为圆A只是与圆B相切，圆b只与圆c相切，每次计算圆与圆距离时前都要判断这个圆与下一个圆或其他圆是否相切，如果下意识认为a是不能与c相切的就错了，圆与圆距离就会算错，这就需要以记录圆与圆坐标之间的坐标（一定是相切所以只需要考虑如何相切，怎么相切）。这题主要就判断圆是如何相切的。 因为圆的长度已知所以我们可以轻松求出圆的左右坐标（默认x轴）我们可以想象其中一个圆是无限（大或小）的，大的话忽略其他圆，小的话通过比较找出最小的左边坐标和最大的右边坐标，相减就是该圆排列长度然后每次不同排列的长度相比较以此类推，找出最小的minlen 3.1.2 程序源码 #include
double center(int t) //获取每个圆的圆心坐标 { double temp = 0; for(int j = 1; j < t; j++) { double xvalue = x[j] + 2.0 * sqrt(r[t] * r[j]); if(xvalue > temp) temp = xvalue; } return temp; } void compute(int n) //计算原的最小长度 { double low = 0, high = 0; for(int i = 1; i < n; i++) { if(x[i] - r[i] < low) low = x[i] - r[i]; if(x[i] + r[i] > high) high = x[i] + r[i]; } if(high - low < minlen) { minlen = high - low; } } void backtrack(int t,int n) { if(t == n) //层数到达，开始计算 { compute(n); } else { for(int j = t; j < n; j++) { swap(r[t],r[j]); double centerx = center(t); if(centerx + r[t] + r[1] < minlen) //剪枝 { x[t] = centerx; backtrack(t+1,n); } swap(r[t],r[j]);
} } } int main() { int n,i; scanf(\ for(i = 1; i < n+1; i++) { scanf(\ } backtrack(1,n+1); printf(\ return 0; } 3.1.3 实验结论 要有截图，验证最后结果（图片分布要合理）。 输入/输出应与TEST文件夹测试用例一致。 有 3.1.4 心得体会 这个是真的一点头绪都没有，解空间树画不出来，只能百度查询做法，我好菜啊，看了三天还没看明白，之后问舍友又弄懂一点，算法好难啊，那个算圆与圆之间距离倒是能弄明白，解空间树倒是能画出来了还是遍历所有树，剪枝函数没看明白
4. 教师批改意见 签字： 日期： 成绩
实验4 分支限界
