实验项目三：搜索算法

1、算法设计与分析实验报告实验项目（三） 搜索算法专业、班级学号姓名实验时间实验地点指导教师教学目标使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。（1） 掌握编程求解问题的常用算法策略。（2） 熟练强化深入计算机求解问题的过程。（3） 增强理论结合实际能力，增强获得理论联系实际问题的能力。（4） 培养系统分析能力和团队协作能力。一、 实验目的及要求（1） 练习搜索算法和分支限界算法中剪枝的使用；（2） 初步掌握回溯法和分支限界的编码。二、 实验设备（环境）及要求使用C/C+语言，Visu

2、al Studio 201X开发环境，Windows系列操作系统环境三、 成绩评定题号题型能力分值成绩备注设计分析题设计分析20设计分析题设计分析30设计分析题设计分析40报告格式10总成绩四、 实验内容与步骤1、 容器里有10升油，现在只有两个分别能装3升和7升油的瓶子，需要将10 升油等分成2 个5 升油。程序输出分油次数最少的详细操作过程。源程序：#include using namespace std;int pull(int m, int n) int n10 = 10, a = 0, b = 0, total = 1;while (n10 != 5) if (a = 0) n10

3、-= m; a += m;/向3/7L杯子倒入cout total+ : 10 L容器向 m L容器倒入 m L油 0 & b n) /3/7L杯子有油时倒入7/3L杯子if (b + a = n) b += a;cout total+ : m L容器向 n L容器倒入 a L油 endl;a -= a;else a -= n - b;cout total+ : m L容器向 n L容器倒入 n - b L油 endl;b = n;if (b = n) b -= n; n10 += n;cout total+ : n L容器向 10 L容器倒入 n L油 = n) if (a = 5)brea

4、k;else if (b = 5)break;cout n10 L容器中有 n10 L油, m L容器中有 a L油, n L容器中有 b L油 endl;return -total;int main() int min;cout 第 1 种方案： endl;min = pull(3, 7);cout 第 2 种方案： pull(7, 3)cout 第 2 种方案步骤最少。;else cout 第 1 种方案步骤最少。;return 0;运行结果：2、 用非递归回溯算法完成数独求解。“数独”是一种智力游戏，一般认为起源于“正交拉丁方”，经日本人推广后风靡全球。下图是一个数独的示例，需要根据 9

5、 9 盘面上的已知数字，推理出所有剩余空格的数字，并且满足同一行、同一列、每一个同色九宫内的数字均含19 不重复：数独的答案一般都是唯一的，如果有多个可行解也称为无解。实验要求：1) 输入数据共9 行，每行9 个连续的数字，0 代表未知，其它数字为已知。2) 输出数据共9 行，每行9 个连续的数字表示该数独的解。源程序：#includeint a99;int judge(int x,int y)int up,left;int i,j; up = x/3*3; left = y/3*3; for(i=0;i9;i+) if(axy = aiy&i!=x&aiy != 0) return 0;fo

6、r(i=0;i9;i+)if(axy = axi&i!=y&axi != 0) return 0;for(i=up;iup+3;i+)for(j=left;jleft+3;j+)if(i!=x | j!=y)if(aij = axy & aij!=0) return 0;void backtrack(int t)int i,j,x,y;if(t=81)printf(n=n);for(i=0;i9;i+)for(j=0;j9;j+)printf(%2d,aij);printf(n);elsex = t/9;y = t%9;if(axy != 0)backtrack(t+1);elsefor(i=

7、1;i=9;i+)axy = i;if(judge(x,y) backtrack(t+1); axy = 0;int main()char str99;int i,j;for(i=0;i9;i+)gets(stri);for(i=0;i9;i+)for(j=0;j9;j+)aij = strij - 0;backtrack(0);return 0;运行结果：3、 用分支与限界策略求解货物调运问题某大型集团公司在全国有m (1 m 20) 个产品生产基地(通称产地)，用Ai 表示(i = 1, 2, , m)，需要分别将这些物质调运到n (1 n 20) 个集中消费的地区(通称销地)，用Bj 表

8、示(j = 1, 2, , n)。已知这m 个产地的产量分别为a1, a2, , am(简写为ai)，n 个销地的销量分别为b1, b2, , bn(简写为bj)，从第i 个产地到第j 个销地的单位货运价格为cij，并且总产量和总销量不一定相等。应当如何制定调运方案，在尽可能地满足销量的前提下，使得总的运输费用为最小。u 例：某集团公司的产量和销量以及单位运价表(千元/吨)其总运费最小的调运方案为：运费总计：5 3 + 2 10 + 3 1 + 1 8 + 6 4 + 3 5 = 85(千元)。源代码：#include #include #define min(x,y) (xy?x:y)usi

9、ng namespace std;int freight34 = 3,11,3,10,1,9,2,8,7,4,10,5 ;int sales4 = 3,6,5,6 ;int production3 = 7,4,9 ;int mincost = 999;int key53 = 1,3,2,2,1,3,2,3,1,3,2,1,3,1,2 ;struct NodeType int r4;int lb;int pro34 = 0 ;bool operator s.lb;void ret() sales0 = 3, sales1 = 6, sales2 = 5, sales3 = 6;productio

10、n0 = 7, production1 = 4, production2 = 9;void bound(NodeType& e) int sum = 0, j;for (int m = 0; m 4; m+) j = e.rm;int temp, i = 0;int min = 100, max = 0, x3 = 0 ;for (int k = 0; k freightkj) x0 = k;min = freightkj;for (int k = 0; k 3; k+) if (max 0) temp = salesj;xij = min(salesj, productionxi)

11、;salesj -= productionxi;if (salesj 0) sum = sum + productionxi * freightxij;productionxi = 0;i+;else salesj = 0;sum = sum + freightxij * temp;productionxi -= temp;e.lb = sum;void bfs() priority_queue qu;NodeType e, e1;e.r4 = 0 ;for (int m = 0; m e.lb) mincost = e.lb;e1.r0 = e.r0;for (int k = 1; k 4; k+) e1.rk = keyjk - 1;j+;bound(e1);ret();if (e1.lb = mincost)qu.push(e1);cout 总运费最小的调运方案为： endl;cout tB1tB2tB3tB4 endl; cout endl;for (int i = 0;