in = cost[i][j];
244、 }
245、 low += min;
246、 }
247、 }
248、
249、 //估值
250、 int get_lb(Node p)
251、 {
252、 int ret = p.sumv * 2;//路径上的点的距离的二倍
253、 int min1 = INF, min2 = INF;//起点和终点连出来的边
254、 for (int i = 1; i <= n; i++){
255、 if (!p.visited[i] && min1 > cost[i][p.s]){
256、 min1 = cost[i][p.s];
257、 }
258、 }
259、 ret += min1;
260、 for (int i = 1; i <= n; i++){
261、 if (!p.visited[i] && min2 > cost[p.e][i]){
262、 min2 = cost[p.e][i];
263、 }
264、 }
265、 ret += min2;
266、 for (int i = 1; i <= n; i++){
267、 if (!p.visited[i]){
268、 min1 = min2 = INF;
269、 for (int j = 1; j <= n; j++){
270、 if (min1 > cost[i][j])
271、 min1 = cost[i][j];
272、 }
273、 for (int j = 1; j <= n; j++){
274、 if (min2 > cost[j][i])
275、 min2 = cost[j][i];
276、 }
277、 ret += min1 + min2;
278、 }
279、 }
280、 return (ret + 1) / 2;
281、 }
282、
283、 int solve()
284、 {
285、 //贪心法确定上界
286、 get_up();
287、 //取每行最小的边之和作为下界
288、 get_low();
289、 //设置初始点,默认从1开始
290、 Node star;
291、 star.s = 1;//起点为1
292、 star.e = 1;//终点为1
293、 star.k = 1;//走过了1个点
294、 for (int i = 1; i <= n; i++)
295、 {
296、 star.visited[i] = false;
297、 }
298、 star.visited[1] = true;
299、 star.sumv = 0;//经过的路径距离初始化
300、 star.lb = low;//让目标值先等于下界
301、 int ret = INF;//ret为问题的解
302、 pq.push(star);//将起点加入队列
303、 while (pq.size()){
304、 Node tmp = pq.top(); pq.pop();
305、 //如果已经走过了n-1个点
306、 if (tmp.k == n - 1){
307、 //找最后一个没有走的点
308、 int p;
309、 for (int i = 1; i <= n; i++){
310、 if (!tmp.visited[i]){
311、 p = i;//让没有走的那个点为最后点能走的点
312、 break;
313、 }
314、 }
315、 int ans = tmp.sumv + cost[p][tmp.s] + cost[tmp.e][p];//已消耗+回到开始消耗+走到P的消耗
316、 //如果当前的路径和比所有的目标函数值都小则跳出
317、 if (ans <= tmp.lb){
318、 ret = min(ans, ret);
319、 break;
320、 }
321、 //否则继续求其他可能的路径和，并更新上界
322、 else{
323、 up = min(up, ans);//上界更新为更接近目标的ans值
324、 ret = min(ret, ans);
325、 continue;
326、 }
327、 }
328、 //当前点可以向下扩展的点入优先级队列
329、 Node next;
330、 for (int i = 1; i <= n; i++){
331、 if (!tmp.visited[i]){
332、 next.s = tmp.s;//沿着tmp走到next，起点不变
333、 next.sumv = tmp.sumv + cost[tmp.e][i];//更新路径和
334、 next.e = i;//更新最后一个点
335、 next.k = tmp.k + 1;//更新走过的顶点数
336、 for (int j = 1; j <= n; j++) next.visited[j] = tmp.visited[j];//tmp经过的点也是next经过的点
337、 next.visited[i] = true;//自然也要更新当前点
338、 next.lb = get_lb(next);//求目标函数
339、 if (next.lb > up) continue;//如果大于上界就不加入队列
340、 pq.push(next);//否则加入队列
341、 }
342、 }
343、 }
344、 return ret;
345、 }
346、
347、 int main()
348、 {
349、 cin >> n;
350、 for (int i = 1; i <= n; i++){
351、 for (int j = 1; j <= n; j++){
352、 //对角线不可达
353、 if (i == j){
354、 cost[i][j] = INF;
355、 continue;
356、 }
357、 cin >> cost[i][j];
358、 }
359、 }
360、 cout << solve() << endl;
361、 return 0;
362、 }
四、运行输出结果：
1、 01背包问题 + 采药--1003
2、 TSP问题—1813+1814
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1、一开始我背包问题搞错了，把上界搞成贪心法求得的解了，导致一直有问题。后来经过胡杭天的提醒，我才意识到，背包问题要求的是最大价值，与之前作业里的不同，作业里要求的是最短运行时间，所以在这个问题里贪心法求得的解应该当作这个问题的下界。
, 《算法设计与分析-分支限界法》上机实验报告
目录
《算法设计与分析-分支限界法》上机实验报告
一、实验内容：
二、所用算法的基本思想及复杂度分析：
三、源程序及注释：
四、运行输出结果：
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
一、实验内容：
分支限界法问题。
二、所用算法的基本思想及复杂度分析：
1、 01背包问题+采药1003
1） 基本思想
对于一个给定容量的背包，01背包问题就是要求这个背包能容纳的最大价值。首先我们先算出其上下界。对于其下界，我们可以用贪心法来求出其最大价值，而上界就是所有物品价值的累加和。由上界和下界组成最优值区间。之后我们就可以进行搜索剪枝了，对于物品1，我们选择放入和不放入分别估算其价值，如果不在最优值区间里的我们对他进行剪枝，而在最优值区间内的结果我们选取估值最小的那个进行进一步展开，如此反复，每次都选估值最小的进行展开（展开的时候放和不放两种情况都要）。
2、 TSP问题—1813+1814
1） 基本思想
原理基本与01背包问题相同，也是选上界和下界，然后不断地搜索估值，最后得到最优解。其中，这里用贪心法求得上界（因为要求的是最短路径，所以与01背包有些许不同），下界就比较简单了，直接取每行的最小值进行相加即可。然后呢，就是对每个点进行估值，如果超过最优值区间则剪枝否则取最小的那个继续展开进行估值，一致循环直到找到最优解。
三、源程序及注释：
1、 01背包问题 + 采药--1003
2、 /*
3、 测试数据：
4、 6 5
5、 3 25
6、 2 20
7、 1 15
8、 4 40
9、 5 50
10、 */
11、
12、 #include <iostream>
13、 #include <queue>
14、 #include <algorithm>
15、 using namespace std;
16、
17、 struct Node{
18、 Node(){
19、 value = 0;
20、 weight = 0;
21、 level = 0;
22、 parent = 0;
23、 bound = 0;
24、 }
25、 int value; //搜索到该节点时的价值
26、 int weight; //搜索到该节点时的总重量
27、 float bound; //搜索以该节点为根的子树能达到的价值上界
28、 int level; //该节点所处层次，从0开始
29、 struct Node *parent; //指向父节点
30、 };
31、
32、 struct cmp{
33、 bool operator()(Node *a, Node *b){
34、 return a->bound < b->bound;
35、 }
36、 };
37、
38、 //物品
39、 struct Goods{
40、 int id;
41、 int w=0;
42、 int v=0;
43、 double v_perw=0;
44、 };
45、
46、 bool GoodCmp(Goods good1, Goods good2){
47、 return good1.v_perw > good2.v_perw;
48、 }
49、
50、
51、 Goods good[101];
52、 int c, n;
53、
54、 //限界函数
55、 float maxBound(Node *node, Goods good[], int c){
56、 //求以该节点为根的子树能达到的价值上界
57、 float maxValue;
58、 int restCapacity; //扩展到该节点时的剩余容量
59、 int i;
60、
61、 maxValue = node->value;
62、 restCapacity = c - node->weight;
63、 i = node->level;
64、 while (i < n && restCapacity > good[i].w){
65、 maxValue += good[i].v;
66、 restCapacity -= good[i].w;
67、 i++;
68、 }
69、 if (restCapacity != 0){
70、 maxValue += restCapacity * good[i].v_perw;
71、 }
72、 return maxValue;
73、 }
74、
75、 //bfs
76、 int searchCount = 0;
77、 int branchAndBound(Goods good[], int c){
78、 int x[n+1] = {0};
79、 int maxValue; //保存当前搜索到的最大价值
80、 int maxSize = 0;
81、 Node *maxNode = new Node(); //保存当前最大价值节点（叶节点）
82、 priority_queue<Node *, vector<Node *>, cmp> maxQueue; //最大价值优先队列
83、 Node *firstNode, *curNode;
84、
85、 searchCount = 1;
86、 firstNode = new Node();
87、 firstNode->bound = maxBound(firstNode, good, c);
88、 firstNode->parent = NULL;
89、 maxQueue.push(firstNode); //入队第一个结点
90、 maxValue = 0;
91、 maxNode = firstNode;
92、 while (!maxQueue.empty())
93、 {
94、 curNode = maxQueue.top();
95、 maxQueue.pop();
96、 //扩展左孩子结点
97、 if (curNode->weight + good[curNode->level].w <= c){
98、 //最大重量限界
99、 Node *leftNode = new Node();
100、 leftNode->value = curNode->value + good[curNode->level].v;
101、 leftNode->weight = curNode->weight + good[curNode->level].w;
102、 leftNode->level = curNode->level + 1;
103、 leftNode->parent = curNode;
104、 leftNode->bound = curNode->bound;
105、 if (leftNode->level < n){
106、 maxQueue.push(leftNode);
107、 searchCount++;
108、 }
109、 if (maxValue < leftNode->value){
110、 maxValue = leftNode->value;
111、 maxNode = leftNode;
112、 }
113、 }
114、 //扩展右孩子结点
115、 if (maxBound(curNode, good, c) > maxValue){
116、 //最大价值上界限界
117、 Node *rightNode = new Node();
118、 rightNode->value = curNode->value;
119、 rightNode->weight = curNode->weight;
120、 rightNode->level = curNode->level + 1;
121、 rightNode->parent = curNode;
122、 rightNode->bound = maxBound(rightNode, good, c);
123、 if (rightNode->level < n){
124、 maxQueue.push(rightNode);
125、 searchCount++;
126、 }
127、 }
128、 //跟踪队列大小
129、 if (maxQueue.size() > maxSize)
130、 maxSize = maxQueue.size();
131、 }
132、 curNode = maxNode;
133、 while (curNode){
134、 int tempValue = curNode->value;
135、 curNode = curNode->parent;
136、 if (curNode && curNode->value != tempValue)
137、 x[good[curNode->level].id] = 1;
138、 }
139、 return maxValue;
140、 }
141、
142、 int main()
143、 {
144、 cin >> c >> n;
145、 for (int i = 0; i < n; ++i){
146、 cin >> good[i].w >> good[i].v;
147、 good[i].id = i;
148、 good[i].v_perw = (float)good[i].v / good[i].w;
149、 }
150、 sort(good, good + n, GoodCmp); //按单位价值排序
151、 cout << branchAndBound(good, c) << endl;
152、 return 0;
153、 }
154、 TSP问题—1813+1814
155、 /*
156、 测试数据：
157、 5
158、 3 1 5 8
159、 3 6 7 9
160、 1 6 4 2
161、 5 7 4 3
162、 8 9 2 3
163、
164、 4
165、 3 6 7
166、 5 2 3
167、 6 4 2
168、 3 7 5
169、
170、 10
171、 42 160 34 136 134 94 78 18 196
172、 42 166 66 106 87 11 122 195 32
173、 160 166 4 98 198 3 154 75 121
174、 34 66 4 187 112 52 94 36 144
175、 136 106 98 187 12 64 45 46 48
176、 134 87 198 112 12 154 109 196 131
177、 94 11 3 52 64 154 11 79 80
178、 78 122 154 94 45 109 11 13 86
179、 18 195 75 36 46 196 79 13 162
180、 196 32 121 144 48 131 80 86 162
181、 */
182、
183、 #include<iostream>
184、 #include<algorithm>
185、 #include<cstdio>
186、 #include<queue>
187、 const int INF = 100000;
188、 const int MAX_N = 22;
189、 using namespace std;
190、 //n*n的一个矩阵
191、 int n;
192、 int cost[MAX_N][MAX_N];//最少3个点，最多MAX_N个点
193、 struct Node
194、 {
195、 bool visited[MAX_N];//标记哪些点走了
196、 int s;//第一个点
197、 int s_p;//第一个点的邻接点
198、 int e;//最后一个点
199、 int e_p;//最后一个点的邻接点
200、 int k;//走过的点数
201、 int sumv;//经过路径的距离
202、 int lb;//目标函数的值（目标结果）
203、 bool operator <(const Node& p)const{
204、 return p.lb < lb;//目标函数值小的先出队列
205、 }
206、 };
207、
208、 priority_queue<Node> pq;//创建一个优先队列
209、 int low, up;//下界和上界
210、 bool dfs_visited[MAX_N];//在dfs过程中搜索过
211、
212、 //确定上界,利用dfs（属于贪心算法），贪心法的结果是一个大于实际值的估测结果
213、 //当前节点，目标节点，已经消耗的路径
214、 int dfs(int u, int k, int l){
215、 if (k == n) return l + cost[u][1];//如果已经检查了n个节点，则直接返回路径消耗+第n个节点回归起点的消耗
216、 int minlen = INF, p;
217、 for (int i = 1; i <= n; i++){
218、 //取与所有点的连边中最小的边
219、 if (!dfs_visited[i] && minlen > cost[u][i]){
220、 minlen = cost[u][i];//找出对于每一个节点，其可达节点中最近的节点
221、 p = i;
222、 }
223、 }
224、 dfs_visited[p] = true;//以p为下一个节点继续搜索
225、 return dfs(p, k + 1, l + minlen);
226、 }
227、
228、 //取上界
229、 void get_up(){
230、 dfs_visited[1] = true;//以第一个点作为起点
231、 up = dfs(1, 1, 0);
232、 }
233、
234、 //取下界
235、 void get_low()
236、 {
237、 //取每行最小值之和作为下界
238、 low = 0;
239、 for (int i = 1; i <= n; i++){
240、 int min = INF;
241、 for(int j=1; j<=n; ++j){
242、 if(cost[i][j]<min)
243、 m
