算法之分支限界法实现.doc

实验5 分支限界法实现一、实验目标：1.熟悉分支限界法应用场景及实现的基本方法步骤；2.学会分支限界法的实现方法和分析方法：二、实验内容1. n后问题：编程计算当n=1到8时解的个数，分别利用回溯法和分支限界法实现，比较并分析你的算法效率。回溯法：代码：#include#includeusing namespace std;/法一：迭代回溯class Queenfriend int nQueen(int);private:bool Place(int k);void Backtrack(int t);int n;/皇后个数int *x;/当前解int sum;/当前已找到的可行方案数;bool Queen:Place(int k)for (int j = 1; j n)sum+;elsefor (int i = 1; i = n; i+)xt = i;if (Place(t)Backtrack(t + 1);int nQueen(int n)Queen X;/初始化XX.n = n;X.sum = 0;int *p = new intn + 1;for (int i = 0; i = n; i+)pi = 0;X.x = p;X.Backtrack(1);deletep;return X.sum;int main()cout 共有 nQueen(8) 种 endl;system(pause);return 0;截图：分支限界法：代码：#include#includeusing namespace std;class Queenfriend int nQueen(int);private:bool Place(int k);void redu(int t);int n;/皇后个数int *x;/当前解int sum;/当前已找到的可行方案数;/剪枝函数/判断当前状态是否合理，即皇后会不会互相攻击bool Queen:Place(int k)for (int j = 1; j k; j+)if (abs(k - j) = abs(xj - xk) | (xj = xk)return false;/所有皇后都不会互相攻击return true;int nQueen(int n)Queen X;/初始化XX.n = n;X.sum = 0;int *p = new intn + 1;for (int i = 0; i n)sum+;elsefor (int i = 1; i = n; i+)xt = i;if (Place(t)redu(t + 1);int main()cout 共有 nQueen(8) 种 endl;system(pause);return 0;截图：2. 单源最短路径问题：如图求出从源顶点0到其它顶点的最短路径长度，比较贪心算法和分支限界法。贪心算法（dijk）代码：#includeusing namespace std;#define maxint 10000/n为节点个数，v为源节点，dist为源节点到其他节点距离数组，/prev为源节点到顶点i的最短路径上的前一个节点，c为个节点之间的距离数组void Dijkstra(int n, int v, int dist, int prev, int * c)/顶点集合Sbool smaxint;for (int i = 1; i = n; i+)/源节点到各节点的距离记录disti = cvi;/S初始化为空si = false;if (disti = maxint)/不可达previ = 0;elseprevi = v;/源节点初始化distv = 0;sv = true;/核心算法for (int i = 1; i n; i+)int temp = maxint;int u = v;for (int j = 1; j = n; j+)/寻找距离最小而且不在S中的节点if (!sj & (distj temp)u = j;temp = distj;/把找到的节点加入到Ssu = true;/更新dist数组，通过u节点for (int j = 1; j = n; j+)int newdist = distu + cuj;if (newdist distj)distj = newdist;prevj = u;int main()cout 请输入节点个数 n;cout 请输入起点(例如1,2,3。) v;int *c = new int *n + 1;for (int i = 1; i = n; i+)ci = new intn + 1;cout 请输入各节点之间距离 endl;for (int i = 1; i = n; i+)for (int j = 1; j cij;if (cij = 0)cij = maxint;/测试数据/for (int i = 1; i = n; i+)/for (int j = 1; j = n; j+)/cij = maxint;/c13 = 20;/c14 = 5;/c23 = 30;/c24 = 20;/c34 = 30;/c45 = 10;int distmaxint;int prevmaxint;Dijkstra(n, v, dist, prev, c);for (int i = 1; i = 5; i+)if (disti = maxint)cout i v : 不可达 endl;elsecout i v : disti endl;for (int i = 1; i = n; i+)delete ci;delete c;system(pause);return 0;截图：分支限界法：代码：#include using namespace std;#define maxint 10000class MinHeapNodefriend class Graph;public:operator int()const return length; private:int i; /顶点编号int length; /当前路长;class MinHeapfriend class Graph;public:MinHeap(int maxheapsize = 10);MinHeap() delete heap; MinHeap & Insert(const MinHeapNode & x);MinHeap & DeleteMin(MinHeapNode &x);private:int cs, ms;MinHeapNode *heap;MinHeap:MinHeap(int maxheapsize)ms = maxheapsize;heap = new MinHeapNodems + 1;cs = 0;MinHeap & MinHeap:Insert(const MinHeapNode & x)if (cs = ms)return *this;int i = +cs;while (i != 1 & x heapi / 2)heapi = heapi / 2;i /= 2;heapi = x;return *this;MinHeap & MinHeap:DeleteMin(MinHeapNode& x)if (cs = 0)return *this;x = heap1;MinHeapNode y = heapcs-;int i = 1, ci = 2;while (ci = cs)if (ci heapci + 1)ci+;if (y = heapci)break;heapi = heapci;i = ci;ci *= 2;heapi = y;return *this;class Graphfriend int main();public:void ShortesPaths(int);private:intn, /图G的顶点数*prev; /前驱顶点数组int*c, /图G的领接矩阵*dist; /最短距离数组;void Graph:ShortesPaths(int v)/单源最短路径问题的优先队列式分支限界法MinHeap H(1000);MinHeapNode E;/定义源为初始扩展节点E.i = v;E.length = 0;distv = 0;while (true)/搜索问题的解空间for (int j = 1; j = n; j+)if (cE.ij != 0) & (E.length + cE.ijdistj) / 顶点i到顶点j可达，且满足控制约束distj = E.length + cE.ij;prevj = E.i;/ 加入活结点优先队列MinHeapNode N;N.i = j;N.length = distj;H.Insert(N);tryH.DeleteMin(E); / 取下一扩展结点catch (int)break;if (H.cs = 0)/ 优先队列空break;int main()cout 请输入节点个数 n;cout 请输入起点(例如1,2,3。) v;int *c = new int *n + 1;for (int i = 1; i = n; i+)ci = new intn + 1;cout 请输入各节点之间距离 endl;for (int i = 1; i = n; i+)for (int j = 1; j cij;if (cij = 0)cij = maxint;int distmaxint;for (int i = 1; i = n; i+)disti = maxint;int prevmaxint;Graph G;G.n = n;G.c = c;G.dist = dist;G.prev = prev;G.ShortesPaths(v);cout endl 分支限界法 endl;for (int i = 1; i = 5; i+)if (disti = maxint)cout i v : 不可达 endl;elsecout i v : disti endl;for (int i = 1; i = n; i+)deleteci;delete c;system(pause);return 0;截图：3. 矩阵连乘问题：A1A2A3A430*2020*1515*2525*20已知A1A4矩阵及其维数求最优计算顺序。代码：#includeusing namespace std;void matrixChain(int *p, int *m, int *s,int len)/p用来记录矩阵，mij表示第i个矩阵到第j个矩阵的最优解，s记录从最优解断开位置，len为矩阵个数int n = len - 1;for (int i = 1; i = n; i+)/初始化数组for(int j=1;j=n;j+)mij = 0;for (int r = 2; r = n; r+)for (int i = 1; i = n - r + 1; i+) /行循环int j = i + r - 1;mij = mi + 1j + pi - 1 * pi * pj;/初始化sij=k;寻找最优解，以及最优解断开位置sij = i;for (int k = i + 1; kj; k+)int t = mik + mk + 1j + pi - 1 * pk * pj;if (tmij)sij = k;/在k位置断开得到最优解mij = t;void traceback(int *s, int i, int j)if (i = j)return;traceback(s, i, sij);traceback(s, sij + 1, j);cout Multiply A i , sij and A sij + 1 , j endl;int main()int p5 = 30,20,15,25,20 ;int len = 5;cout 各矩阵为: endl;for (int i = 1; i = 4; i+)cout M i : pi - 1 * pi ;cout endl endl;int *m = new int *len;for (int i = 1; i len; i+)mi = new intlen;int *s = new int *len;for (int i = 1; i len; i+)si = new intlen;matrixChain(p, m, s, len);traceback(s, 1, 4);cout 最优计算次数为 m14 endl endl;system(pause);return 0;截图：4. 二分搜索问题：对于给定的有序整数集a=6，9，13，15，25，33，45，编写程序查找18与33，记录每次比较基准数。代码：#includeusing namespace std;void binary_search(int a, int n, int key)/a为按降序排列