内容发布更新时间 : 2024/12/23 13:17:06星期一 下面是文章的全部内容请认真阅读。

武夷学院实验报告

课程名称： 算法分析与设计 项目名称： 分支限界法：最优及其优化 姓名： 专业：计算机科学班级：1班学号： 同组成员： 无

一、 实验预习部分： 实验目的及要求 进入实验机房，加深学生理解－回溯法在智能搜索计算技术中运用实际问题求解及其通用计算机系统运行环境平台，以及智能回溯法即试探性问题求解算法与核心系统软件、计算机语言和人的智能行为间相互嵌入与支持关系的认识，如视窗操作系统Windows XP/2003/2007等平台、计算机语言选择、静态数据初始化、动态数据决策应用、人类解决问题思路嵌入信息处理过程等；使学生掌握 通用经典信息处理计算技术灵活运用于问题求解个案、嵌入智能并能较好地解决问实际题。 实验设备（环境）及要求 微型计算机，visual C 6.0 实验内容 在视窗操作系统Windows XP/2003/20XX启动成功环境下，选择一个具体的需要回溯法搜索计算技术支持的实际问题，提出一个智能算法，并选择自己熟练掌握的计算机语言来编程，以达问题求解。实际问题(只选一个完成即可)如下： 1.给定有限n个城市及其连通图，并附加必要连线权值(如路程/交通费/速度/时间等值)，整型数n=NZ，NZ={3,4,5?,Nm}，Nm=max(NZ)，求出每人旅行完n个城市所花最少时间或最少花费是多少，参教材P149/P164。 2.十九世纪著名数学家高斯提出的八皇后问题求解，参见教材P154。 3.小偷行窃之0-1背包问题求解，实际例案数据可以自拟给出，参教材P156。 4.图的m着色问题*，参教材P160。 5.最优装载问题*，经销商/最小运输成本核算，拓扑特征数据可自拟给出。 6.不确定性问题*，彩票中奖概率事件等, 实际问题自拟给出【*选做内容】。 一、 实验过程记录部分： 八皇后问题 #include #include #include #define QUEEN 8 //皇后的数目 #define INITIAL -10000 //棋盘的初始值 int a[QUEEN]; //一维数组表示棋盘 void init() //对棋盘进行初始化 { int *p; for (p = a; p < a + QUEEN; ++p) { *p = INITIAL; } } int valid(int row, int col) //判断第row行第col列是否可以放置皇后 { int i; for (i = 0; i < QUEEN; ++i) //对棋盘进行扫描 { if (a[i] == col || abs(i - row) == abs(a[i] - col)) //判断列冲突与斜的冲突 return 0; } return 1; } void print() //打印输出N皇后的一组解 { int i, j; for (i = 0; i < QUEEN; ++i) { for (j = 0; j < QUEEN; ++j) { if (a[i] != j) //a[i]为初始值 printf(\ else //a[i]表示在第i行的第a[i]列可以放置皇后 printf(\ } printf(\ } for (i = 0; i < QUEEN; ++i) printf(\ printf(\ printf(\} void queen() //N皇后程序 { int n = 0; int i = 0, j = 0; while (i < QUEEN) { while (j < QUEEN) //对i行的每一列进行探测，看是否可以放置皇后 { if(valid(i, j)) //该位置可以放置皇后 { a[i] = j; //第i行放置皇后 j = 0; //第i行放置皇后以后，需要继续探测下一行的皇后位所以此处将j清零，从下一行的第0列开始逐列探测 break; } else { ++j; //继续探测下一列 } } if(a[i] == INITIAL) //第i行没有找到可以放置皇后的位置 { if (i == 0) //回溯到第一行，仍然无法找到可以放置皇后的位则说明已经找到所有的解，程序终止 break; else //没有找到可以放置皇后的列，此时就应该回溯 { --i; j = a[i] + 1; //把上一行皇后的位置往后移一列 a[i] = INITIAL; //把上一行皇后的位置清除，重新探测 continue; } } if (i == QUEEN - 1) //最后一行找到了一个皇后位置，说明找到一个结打印出来 {