1、 if （abs（k - j） = abs（xj - xk） | （xj = xk） return false; return true;void Queen:Backtrack（int t） if （t 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; pi = 0; X.x = p; X.Backtr
2、ack（1）; deletep; return X.sum;int main（） cout 共有 nQueen（8） 种 endl;system（pause）; return 0;截图：分支限界法： void redu（int t）;int n;/剪枝函数/判断当前状态是否合理，即皇后会不会互相攻击 /所有皇后都不会互相攻击return true; X.redu（1）;void swap（int &a, int &b）int t = a; a = b; b = t;redu（int t） redu（t + 1）;2. 单源最短路径问题：如图求出从源顶点0到其它顶点的最短路径长度，比较贪心算法和
3、分支限界法。贪心算法（dijk）#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; /源节点到各节点的距离记录disti = cvi; /S初始化为空si = false; if （disti = maxint）/不可达previ = 0; else previ = v; /源节点初
4、始化distv = 0; sv = true; /核心算法for （int i = 1; n; int temp = maxint; int u = v; for （int j = 1;/寻找距离最小而且不在S中的节点if （!sj & （distj temp） u = j; temp = distj; /把找到的节点加入到S su = true; /更新dist数组，通过u节点for （int j = 1; int newdist = distu + cuj; if （newdist distj） distj = newdist; prevj = u;cout 请输入起点（例如1,2,3。）
5、 int v; v; int *c = new int *n + 1; ci = new intn + 1;请输入各节点之间距离 cin cij; if （cij = 0） cij = maxint; /测试数据/for （int i = 1; / for （int j = 1; / cij = maxint; /c13 = 20; /c14 = 5; /c23 = 30; /c24 = 20; /c34 = 30; /c45 = 10; int distmaxint; int prevmaxint; Dijkstra（n, v, dist, prev, c）;= 5; if （disti =
6、 maxint） cout v 不可达 disti delete ci; delete c; system（#include class MinHeapNode friend class Graph;public: operator int（）const return length; int i; /顶点编号int length; /当前路长class MinHeap MinHeap（int maxheapsize = 10）; MinHeap（） delete heap; MinHeap & Insert（const MinHeapNode & x）; DeleteMin（MinHeapNo
7、de &x）; 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;Delete
8、Min（MinHeapNode& if （cs = 0） 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;class Graph friend int main（）; void ShortesPaths（int）;int n, /图G的顶点数*prev; /前驱顶点数组int *c, /图G的领接矩阵*dist; /最短距离
9、数组void Graph:ShortesPaths（int v）/单源最短路径问题的优先队列式分支限界法MinHeap H（1000）; MinHeapNode E; /定义源为初始扩展节点E.i = v; E.length = 0; distv = 0; while （true）/搜索问题的解空间 if （cE.ij != 0） & （E.length + cE.ij disti = maxint; Graph G; G.n = n; G.c = c; G.dist = dist; G.prev = prev; G.ShortesPaths（v）; endl 分支限界法deleteci;3.
10、 矩阵连乘问题：A1A2A3A430*2020*1515*2525*20已知A1A4矩阵及其维数求最优计算顺序。void matrixChain（int *p, int *m, int *s,int len）/p用来记录矩阵，mij表示第i个矩阵到第j个矩阵的最优解，s记录从最优解断开位置，len为矩阵个数int n = len - 1; i+）/初始化数组for（int j=1;j=n;j+） mij = 0; for （int r = 2; r r+）= n - r + 1; i+） /行循环int j = i + r - 1; mij = mi + 1j + pi - 1 * pi *
11、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）;Multiply A, sij and A sij + 1 int p5 = 30,20,15,25,2
12、0 ; int len = 5;各矩阵为:= 4; cout M pi - 1 * pi ; int *m = new int *len; len; mi = new intlen; int *s = new int *len; si = new intlen; matrixChain（p, m, s, len）;traceback（s, 1, 4）;最优计算次数为 m14 4. 二分搜索问题：对于给定的有序整数集a=6，9，13，15，25，33，45，编写程序查找18与33，记录每次比较基准数。void binary_search（int a, int n, int key）/a为按降序排
13、列好了的数组，n为数组大小，key为查找的数字int left = 0; /数组的首位置int right = n - 1;/数组的最后一个位置while （left 1）;/用移位代替除以2可以提高效率if （amid key） amid 为基准数 right = mid - 1; else if （amid left = mid + 1;找到！ return; /未找到此数不存在! return; int a7 = 6,9,13,15,25,33,45 ; int n = 7; binary_search（a, 7, 18）; binary_search（a, 7, 33）;return 0;四、实验体会：n后问题来说，回溯和分支限界法没有什么差别，因为回溯法，基于深度搜索，遍历每一种方案后，寻找一种最佳方法，而这题，是求次数，需要遍历每一种可行的方法。而分支限界法，因为，最终每一种可行方案都是1.n的一个全排列，所以n后问题中，回溯和分支限界，差别不大，基本没有差别。第二题贪心算法，主要就是借助新加入的节点，作为中间节点，搜索路径，看看有没有能够找到更近到其他未到节点的路径。
