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

1、算法之分支限界法实现 实验5 分支限界法实现一、实验目标：1.熟悉分支限界法应用场景及实现的基本方法步骤；2.学会分支限界法的实现方法和分析方法：二、实验内容1. n后问题：编程计算当n=1到8时解的个数.分别利用回溯法和分支限界法实现.比较并分析你的算法效率。回溯法：代码：#include#includeusing namespace std;/法一：迭代回溯class Queen friend int nQueen(int);private: bool Place(int k); void Backtrack(int t); int n;/皇后个数 int *x;/当前解 int sum;

2、/当前已找到的可行方案数;bool Queen:Place(int k) for (int j = 1; j n) sum+; else for (int i = 1; i = n; i+) xt = i; if (Place(t) Backtrack(t + 1); int nQueen(int n) Queen X; /初始化X X.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 mai

3、n() cout 共有 nQueen(8) 种 endl; system(pause); return 0;截图：分支限界法：代码：#include#includeusing namespace std;class Queen friend 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;

4、j+) if (abs(k - j) = abs(xj - xk) | (xj = xk) return false; /所有皇后都不会互相攻击 return true;int nQueen(int n) Queen X; /初始化X X.n = n; X.sum = 0; int *p = new intn + 1; for (int i = 0; i n) sum+; else for (int i = 1; i = n; i+) xt = i; if (Place(t) redu(t + 1); int main() cout 共有 nQueen(8) 种 endl; system(pa

5、use); 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) /顶点集合S bool smaxint; for (int i = 1; i = n; i+)

6、 /源节点到各节点的距离记录 disti = cvi; /S初始化为空 si = false; if (disti = maxint)/不可达 previ = 0; else previ = 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; /把找到的节点加入到S su = true;

7、 /更新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

8、= 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

9、v : 不可达 endl; else cout 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 MinHeapNode friend class Graph;public: operator int()const return length; private: int i; /顶点编号 int length; /当前路长;class

10、 MinHeap friend 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;MinHea

11、p & 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 = c

12、s) if (ci heapci + 1) ci+; if (y = heapci) break; heapi = heapci; i = ci; ci *= 2; heapi = y; return *this;class Graph friend int main();public: void ShortesPaths(int);private: int n, /图G的顶点数 *prev; /前驱顶点数组 int *c, /图G的领接矩阵 *dist; /最短距离数组;void Graph:ShortesPaths(int v)/单源最短路径问题的优先队列式分支限界法 MinHeap H(

13、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); try H.DeleteMin

14、(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; f

15、or (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; else cout i v : disti endl; for (int i = 1; i = n; i+) deleteci; delete c; s

16、ystem(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 (in

17、t 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

18、= 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 = ne

19、w 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, i

20、nt n, int key)/a为按降序排列好了的数组.n为数组大小.key为查找的数字 int left = 0; /数组的首位置 int right = n - 1;/数组的最后一个位置 while (left 1);/用移位代替除以2可以提高效率 if (amid key) cout amid 为基准数 endl; right = mid - 1; else if (amid key) cout amid 为基准数 endl; left = mid + 1; else cout amid 为基准数 endl; cout 找到！ endl; return; /未找到 cout 此数不存在!

21、 endl; return;int main() int a7 = 6,9,13,15,25,33,45 ; int n = 7; binary_search(a, 7, 18); cout endl; binary_search(a, 7, 33); system(pause); return 0;截图：四、 实验体会：n后问题来说.回溯和分支限界法没有什么差别.因为回溯法.基于深度搜索.遍历每一种方案后.寻找一种最佳方法.而这题.是求次数.需要遍历每一种可行的方法。而分支限界法.因为.最终每一种可行方案都是1.n的一个全排列.所以n后问题中.回溯和分支限界.差别不大.基本没有差别。第二题贪心算法.主要就是借助新加入的节点.作为中间节点.搜索路径.看看有没有能够找到更近到其他未到节点的路径。