算法之回溯法实现.docx

1、实验4 回溯法实现 一、实验目标：1.熟悉回溯法应用场景及实现的基本方法步骤；2.学会回溯法的实现方法和分析方法：二、实验内容1. 旅行售货员问题：当结点数为4，权重矩阵为0110239429340660，求最优路径及开销。2. 0-1背包问题：对于n=5，C=10，vi=6,3,5,4,6，wi=2,2，6,5,4，计算xi及最优价值V。分别利用动态规划、回溯法和分支限界法解决此问题，比较并分析这三种算法实现！三、实验过程1.源代码旅行售货员问题（回溯法）：#includeusing namespace std;class travel /回溯friend int TSP(int *, in

2、t, int, int);private:void Backtrack(int i);int n, /顶点数*x,*bestx;int *a,cc,bestc,NoEdge;void Swap(int a, int b)int temp;temp = a;a = b;b = temp;return;void travel:Backtrack(int i)if (i = n)if (axn - 1xn != NoEdge & axn1 != NoEdge &(cc + axn - 1xn + axn1) bestc | bestc = NoEdge)for (int j = 1; j = n;

3、j+) bestxj = xj;bestc = cc + axn - 1xn + axn1;elsefor (int j = i; j = n; j+)if (axi - 1j != NoEdge & axn1 != NoEdge& (cc + axi - 1xj bestc | bestc = NoEdge)swap(xi, xj);cc += axi - 1xi;Backtrack(i + 1);cc -= axi - 1xi;swap(xi, xj);int TSP(int* a,int v, int n, int NoEdge)travel Y;Y.x = new intn + 1;f

4、or (int i = 1; i = n; i+)Y.xi = i;Y.a = a;Y.n = n;Y.bestc = NoEdge;Y.bestx = v;Y.cc = 0;Y.NoEdge = NoEdge;Y.Backtrack(2);delete Y.x;return Y.bestc;int main()int const max = 10000;cout 请输入节点数: n;int *v = new intn;/保存路径int NoEdge = 0;int *p = new int*max;for (int i = 0; i n+1; i+)/生成二维数组pi = new intn+

5、1;cout 请依次输入各城市之间的路程： endl;for (int i = 0; i n; i+)for (int j = 0; j pi+1j+1;cout 最短路径长度： TSP(p, v, 4, 1000) endl;cout 路径为：;for (int i = 1; i 5; i+)cout vi ;cout endl;return 0;运行截图：旅行售货员问题（分支限界法）：#includeusing namespace std;#define MAX_CITY_NUMBER 10 /城市最大数目#define MAX_COST 1000 /两个城市之间费用的最大值int Cit

6、y_GraphMAX_CITY_NUMBERMAX_CITY_NUMBER;/表示城市间边权重的数组int City_Size; /表示实际输入的城市数目int Best_Cost; /最小费用int Best_Cost_PathMAX_CITY_NUMBER;/结点typedef struct Node int lcost; /优先级int cc; /当前费用int rcost; /剩余所有结点的最小出边费用的和int s; /当前结点的深度，也就是它在解数组中的索引位置int xMAX_CITY_NUMBER; /当前结点对应的路径struct Node* pNext; /指向下一个结点N

7、ode;/堆typedef struct MiniHeap Node* pHead; /堆的头MiniHeap;/初始化void InitMiniHeap(MiniHeap* pMiniHeap) pMiniHeap-pHead = new Node;pMiniHeap-pHead-pNext = NULL;/入堆void put(MiniHeap* pMiniHeap, Node node) Node* next;Node* pre;Node* pinnode = new Node; /将传进来的结点信息copy一份保存 /这样在函数外部对node的修改就不会影响到堆了pinnode-cc

8、= node.cc;pinnode-lcost = node.lcost;pinnode-pNext = node.pNext;pinnode-rcost = node.rcost;pinnode-s = node.s;pinnode-pNext = NULL;for (int k = 0; kxk = node.xk;pre = pMiniHeap-pHead;next = pMiniHeap-pHead-pNext;if (next = NULL) pMiniHeap-pHead-pNext = pinnode;else while (next != NULL) if (next-lcos

9、t) (pinnode-lcost) /发现一个优先级大的，则置于其前面pinnode-pNext = pre-pNext;pre-pNext = pinnode;break; /跳出pre = next;next = next-pNext;pre-pNext = pinnode; /放在末尾/出堆Node* RemoveMiniHeap(MiniHeap* pMiniHeap) Node* pnode = NULL;if (pMiniHeap-pHead-pNext != NULL) pnode = pMiniHeap-pHead-pNext;pMiniHeap-pHead-pNext =

10、pMiniHeap-pHead-pNext-pNext;return pnode;/分支限界法找最优解void Traveler() int i, j;int temp_xMAX_CITY_NUMBER;Node* pNode = NULL;int miniSum; /所有结点最小出边的费用和int miniOutMAX_CITY_NUMBER;/保存每个结点的最小出边的索引MiniHeap* heap = new MiniHeap; /分配堆InitMiniHeap(heap); /初始化堆miniSum = 0;for (i = 0; iCity_Size; i+) miniOuti =

11、MAX_COST; /初始化时每一个结点都不可达for (j = 0; j0 & City_GraphijminiOuti) /从i到j可达，且更小miniOuti = City_Graphij;if (miniOuti = MAX_COST) / i 城市没有出边Best_Cost = -1;return;miniSum += miniOuti;for (i = 0; ilcost = 0; /当前结点的优先权为0 也就是最优pNode-cc = 0; /当前费用为0（还没有开始旅行）pNode-rcost = miniSum; /剩余所有结点的最小出边费用和就是初始化的miniSumpNo

12、de-s = 0; /层次为0pNode-pNext = NULL;for (int k = 0; kxk = Best_Cost_Pathk; /第一个结点所保存的路径也就是初始化的路径put(heap, *pNode); /入堆while (pNode != NULL & (pNode-s) City_Size - 1) /堆不空 不是叶子for (int k = 0; kxk; /将最优路径置换为当前结点本身所保存的/* * pNode 结点保存的路径中的含有这条路径上所有结点的索引* * x路径中保存的这一层结点的编号就是xCity_Size-2* * 下一层结点的编号就是xCity_

13、Size-1*/if (pNode-s) = City_Size - 2) /是叶子的父亲int edge1 = City_Graph(pNode-x)City_Size - 2(pNode-x)City_Size - 1;int edge2 = City_Graph(pNode-x)City_Size - 1(pNode-x)0;if (edge1 = 0 & edge2 = 0 & (pNode-cc + edge1 + edge2) cc + edge1 + edge2;pNode-cc = Best_Cost;pNode-lcost = Best_Cost; /优先权为 Best_Co

14、stpNode-s+; /到达叶子层else /内部结点for (i = pNode-s; ixpNode-spNode-xi = 0) /可达 /pNode的层数就是它在最优路径中的位置int temp_cc = pNode-cc + City_GraphpNode-xpNode-spNode-xi;int temp_rcost = pNode-rcost - miniOutpNode-xpNode-s;/下一个结点的剩余最小出边费用和 /等于当前结点的rcost减去当前这个结点的最小出边费用if (temp_cc + temp_rcostBest_Cost) /下一个结点的最小出边费用和小

15、于当前的最优解，说明可能存在更优解for (j = 0; jxpNode-s + 1 = Best_Cost_Pathi;/将当前结点的编号放入路径的深度为s+1的地方temp_xi = Best_Cost_PathpNode-s + 1; /将原路/径中的深度为s+1的结点编号放入当前路径的 /相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换Node* pNextNode = new Node;pNextNode-cc = temp_cc;pNextNode-lcost = temp_cc + temp_rcost;pNextNode-rcost = temp_rcost;pNe

16、xtNode-s = pNode-s + 1;pNextNode-pNext = NULL;for (int k = 0; kxk = temp_xk;put(heap, *pNextNode);delete pNextNode;pNode = RemoveMiniHeap(heap);for (int k = 0; kCity_Size; k+) /复制路径Best_Cost_Pathk = temp_xk;int main() cout 请输入节点数： City_Size;cout 请依次输入各城市之间的距离 endl;for (int i = 0; i City_Size; i+)for

17、 (int j = 0; j City_Graphij;if (City_Graphij = 0)City_Graphij = 1000; Traveler();cout 最短路径长度： Best_Cost endl;cout 路径为：;for (int i = 0; i 4; i+)cout Best_Cost_Pathi+1 ;return 0;运行截图：0-1背包问题(动态规划)：#include#includeusing namespace std;void knapsack(int v, int *w, int c, int n, int*m) int jmax = min(wn -

18、 1, c); /1) 仅可选物品n时，容量为j的子问题的最优值 for (int j = 0; j = jmax; j+) mnj = 0; /注意j为整数for (int j = wn; j 0; i-) /2) 逐步增加物品数至n及容量至cjmax = min(wi - 1, c); /仅可选物品i时，容量为j的子问题的最优值 for (int j = 0; j = jmax; j+) mij = mi + 1j;for (int j = wi; j = w1) m1c = max(m1c, m2c - w1 + v1);void traceback(int *m, int *w, in

19、t c, int n, int *x)for (int i = 1; i b ? a : b;int min(int a, int b)return a b ? b : a;int main()int n, c;cout 请输入物品数： n;cout 请输入背包容量： c;int *v = new intn + 1;int *w = new intn + 1;cout 请输入物品重量数组： endl;for (int i = 1; i wi;cout 请输入物品价值数组： endl;for (int i = 1; i vi;int *p = new int*n + 1;/子问题最优解for (

20、int i = 1; i n + 1; i+)pi = new intc+1;int *x = new intn + 1;knapsack(v, w, c, n, p);traceback(p, w, c, n, x);cout m(i,j): 0; i-)for (int j = 0; j 11; j+)cout setw(2) pij ;cout endl;cout xi = ;for (int i = 1; i 6; i+)cout xi ;cout endl;cout V= p1c endl;for (int i = 1; i n + 1; i+)/deletedelete pi;delete p;delete v, w;return 0;运行截图：0-1背包问题（回溯法）#includeusing namespace std;int n, c, bestp; /物品的个数，背包的容量，最大价值int p10000, w10000, x10000, bestx10000; /物品的价值，物品的重量，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i, int cp, int cw) /cw当前包内物品重量，cp当前包内物品价值