算法之回溯法实现

实验4 回溯法实现 一、实验目标：1.熟悉回溯法应用场景及实现的基本方法步骤；2.学会回溯法的实现方法和分析方法：二、实验内容1. 旅行售货员问题：当结点数为4，权重矩阵为40660，求最优路径及开销。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 *, int, 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; 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;for (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+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 City_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; /指向下一个结点Node;/堆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 = 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-lcost) (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 = 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 = 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; /剩余所有结点的最小出边费用和就是初始化的miniSumpNode-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_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_CostpNode-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) /下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解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;pNextNode-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 (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 - 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, int 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 (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当前包内物品价值int j;if (in) /回溯结束if (cpbestp)bestp = cp;for (i = 0; i = n; i+) bestxi = xi;elsefor (j = 0; j = 1; j+)xi = j;if (cw + xi * wi = c)cw += wi * xi;cp += pi * xi;Backtrack(i + 1, cp, cw);cw -= wi * xi;cp -= pi * xi;int main()int i;bestp = 0;cout 请输入物品数: n;cout 请输入背包容量: c;cout 请输入物品重量数组: endl;for (i = 1; i wi;cout 请输入物品价值数组: endl;for (i = 1; i pi;Backtrack(1, 0, 0);cout V = bestp endl;cout xi = ;for (i = 1; i = n; i+)cout bestxi ;cout endl;system(pause);return 0;运行截图：0-1背包问题（分支限界法）：#include using namespace std;class Object friend int Knapsack(int *, int *, int, int, int *);public:int operator = a.d);private:int ID; /物品编号float d; /单位重量价值;class bbnode friend class Knap;friend int Knapsack(int *, int *, int, int, int *);private:bbnode * parent; /指向父节点的指针int LChild; /如果是左儿子结点取1，也即说明该物品已装进背包;class HeapNode friend class Knap;friend class MaxHeap;public:operator int()const return uprofit; ;private:int uprofit, /结点的价值上界profit; /结点所相应的价值int weight; /结点所相应的重量int level; /活结点在子集树中所处的层序号bbnode *ptr; /指向该活结点在子集树中相应结点的指针;class MaxHeap public:MaxHeap(int maxElem)HeapElem = new HeapNode*maxElem + 1; /下标为0的保留capacity = maxElem;size = 0;void InsertMax(HeapNode *newNode);HeapNode DeleteMax(HeapNode* &N);private:int capacity;int size;HeapNode *HeapElem; /0-1背包问题的主类class Knap /Knapsack主函数功能：解决初始化、求解最优值和最优解、回收内存friend int Knapsack(int *, int *, int, int, int *);public:int MaxKnapsack();private:MaxHeap * H;/Bound辅助Maxknapsack函数：计算结点价值上界int Bound(int i);/AddLiveNode辅助Maxknapsack函数：将活结点插入子集树和优先队列中void AddLiveNode(int up, int cp, int cw, int ch, int level);bbnode *E; /指向扩展结点的指针int c; /背包容量int n; /物品总数int *w; /物品重量数组（以单位重量价值降序）int *p; /物品价值数组（以单位重量价值降序）int cw; /当前装包重量int cp; /当前装包价值int *bestx; /最优解;void MaxHeap:InsertMax(HeapNode *newNode)/极端情况下暂未考虑,比如堆容量已满等等int i = 1;for (i = +size; i / 2 0 & HeapElemi / 2-uprofit uprofit; i /= 2)HeapElemi = HeapElemi / 2;HeapElemi = newNode;HeapNode MaxHeap:DeleteMax(HeapNode *&N)/极端情况下暂未考虑if (size 0)N = HeapElem1;/从堆顶开始调整int i = 1;while (i size)if (i * 2 + 1) uprofit HeapElemi * 2 + 1-uprofit)HeapElemi = HeapElemi * 2;i = i * 2;elseif (i * 2 = size)HeapElemi = HeapElemi * 2;i = i * 2;elsebreak;if (i size)HeapElemi = HeapElemsize;size-;return *N;int Knap:MaxKnapsack()H = new MaxHeap(1000);bestx = new intn + 1;/初始化,为处理子集树中的第一层做准备,物品i处于子集树中的第i层int i = 1; /生成子集树中的第一层的结点E = 0; /将首个扩展点设置为null，也就是物品1的父节点cw = 0;cp = 0;int bestp = 0; /当前最优值 int up = Bound(1); / 选取物品1之后的价值上界 /当选择左儿子结点时，上界约束up不用关心，重量约束wt需要考虑。因为上界约束跟父节点相同。 /当选择右儿子结点时，上界约束up需要考虑，重量约束不需要考虑。因为父节点和该结点重量相同。while (i != n + 1)/检查当前扩展结点的左儿子结点int wt = cw + wi; /当前选择物品i之后的总重量wtif (wt bestp)bestp = cp + pi;AddLiveNode(up, cp + pi, cw + wi, 1, i);/检查当前扩展结点的右儿子结点up = Bound(i + 1); /未选择物品i之后的价值上界if (up = bestp)AddLiveNode(up, cp, cw, 0, i);/从优先队列中选择价值上界最大的结点成为扩展结点HeapNode* N;H-DeleteMax(N);E = N-ptr;cw = N-weight;cp = N-profit;up = N-uprofit;i = N-level + 1; /准备生成N.level+1层的子集树结点/从子集树中的某叶子结点开始构造当前最优解for (int i = n; i 0; i-)bestxi = E-LChild;E = E-parent;return cp;int Knap:Bound(int i)int cleft = c - cw;int b = cp;while (i = n & wi = cleft)cleft -= wi;b += pi;i+;if (i parent = E;b-LChild = ch;HeapNode *N = new HeapNode;N-uprofit = up;N-profit = cp;N-weight = cw;N-level = level;N-ptr = b;H-InsertMax(N);/Knapsack返回最大价值，最优值保存在bestxint Knapsack(int *w, int *p, int c, int n, int *bestx)/数组w、p和bestx中下标为0的元素保留不用 /初始化int W = 0;int P = 0;Object *Q = new Objectn;for (int i = 1; i = n; i+)Qi - 1.ID = i;Qi - 1.d = 1.0*pi