分支限界求解布线问题(C语言)

问题描述印刷电路板将布线区域划分成n×m个方格如图a所示。

精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。

在布线时，电路只能沿直线或直角布线，如图b所示。

为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。

一个布线的例子：图中包含障碍。

起始点为a，目标点为b。

算法思想解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。

与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。

接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。

这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。

即加入剪枝的广度优先搜索。

算法具体代码如下：1、Queue.h[cpp]view plain copy1.#include<iostream>ing namespace std;3.4.template <class T>5.class Queue6.{7.public:8. Queue(int MaxQueueSize=50);9. ~Queue(){delete [] queue;}10.bool IsEmpty()const{return front==rear;}11.bool IsFull(){return ( ( (rear+1) %MaxSize==front )?1:0);}12. T Top() const;13. T Last() const;14. Queue<T>& Add(const T& x);15. Queue<T>& AddLeft(const T& x);16. Queue<T>& Delete(T &x);17.void Output(ostream& out)const;18.int Length(){return (rear-front);}19.private:20.int front;21.int rear;22.int MaxSize;23. T *queue;24.};25.26.template<class T>27.Queue<T>::Queue(int MaxQueueSize)28.{29. MaxSize=MaxQueueSize+1;30. queue=new T[MaxSize];31. front=rear=0;32.}33.34.template<class T >35.T Queue<T>::Top()const36.{37.if(IsEmpty())38. {39. cout<<"queue:no element,no!"<<endl;40.return 0;41. }42.else return queue[(front+1) % MaxSize];43.}44.45.template<class T>46.T Queue<T> ::Last()const47.{48.if(IsEmpty())49. {50. cout<<"queue:no element"<<endl;51.return 0;52. }53.else return queue[rear];54.}55.56.template<class T>57.Queue<T>& Queue<T>::Add(const T& x)58.{59.if(IsFull())cout<<"queue:no memory"<<endl;60.else61. {62. rear=(rear+1)% MaxSize;63. queue[rear]=x;64. }65.return *this;66.}67.68.template<class T>69.Queue<T>& Queue<T>::AddLeft(const T& x)70.{71.if(IsFull())cout<<"queue:no memory"<<endl;72.else73. {74. front=(front+MaxSize-1)% MaxSize;75. queue[(front+1)% MaxSize]=x;76. }77.return *this;78.}79.80.template<class T>81.Queue<T>& Queue<T> ::Delete(T & x)82.{83.if(IsEmpty())cout<<"queue:no element(delete)"<<endl;84.else85. {86. front=(front+1) % MaxSize;87. x=queue[front];88. }89.return *this;90.}91.92.93.template<class T>94.void Queue <T>::Output(ostream& out)const95.{96.for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)97. out<<queue[i];98.}99.100.template<class T>101.ostream& operator << (ostream& out,const Queue<T>& x) 102.{x.Output(out);return out;}2、6d4.cpp[cpp]view plain copy1.//布线问题队列式分支限界法求解2.#include "stdafx.h"3.#include "Queue.h"4.#include <fstream>5.#include <iostream>ing namespace std;7.8.ifstream fin("6d4.txt");9.10.const int n = 7;11.const int m = 7;12.int grid[n+2][m+2];13.14.struct Position15.{16.int row;17.int col;18.};19.20.bool FindPath(Position start,Position finish,int& PathLen,Position *&path);21.22.int main()23.{24.int PathLen;25.26. Position start,finish,*path;27.28. start.row = 3;29. start.col = 2;30.31. finish.row = 4;32. finish.col = 6;33.34. cout<<"布线起点"<<endl;35. cout<<start.col<<" "<<start.row<<endl;36. cout<<"布线结束点"<<endl;37. cout<<finish.col<<" "<<finish.row<<endl;38.39. cout<<"布线方格阵列如下(0表示允许布线，1表示不允许布线)："<<endl;40.for(int i=1; i<=m; i++)41. {42.for(int j=1; j<=n; j++)43. {44. fin>>grid[i][j];45. cout<<grid[i][j]<<" ";46. }47. cout<<endl;48. }49.50. FindPath(start,finish,PathLen,path);51.52. cout<<"布线长度为:"<<PathLen<<endl;53. cout<<"布线路径如下："<<endl;54.for(int i=0; i<PathLen; i++)55. {56. cout<<path[i].col<<" "<<path[i].row<<endl;57. }58.59.return 0;60.}61.62.bool FindPath(Position start,Position finish,int& PathLen,Position *&path)63.{64.//计算从起始位置start到目标位置finish的最短布线路径65.if((start.row == finish.row) && (start.col == finish.col))66. {67. PathLen = 0;68.return true;69. }70.71.//设置方格阵列“围墙”72.for(int i=0; i<= m+1; i++)73. {74. grid[0][i]=grid[n+1][i]=1; //顶部和底部75. }76.for(int i=0; i<= n+1; i++)77. {78. grid[i][0]=grid[i][m+1]=1; //左翼和右翼79. }80.81.//初始化相对位移82. Position offset[4];83.84. offset[0].row=0;85. offset[0].col=1;//右86.87. offset[1].row=1;88. offset[1].col=0;//下89.90. offset[2].row=0;91. offset[2].col=-1;//左92.93. offset[3].row=-1;94. offset[3].col=0;//上95.96.int NumOfNbrs=4;//相邻方格数97. Position here,nbr;98. here.row=start.row;99. here.col=start.col;100.101. grid[start.row][start.col]=2;//标记可达方格位置102. Queue<Position> Q;103.104.do {//标记相邻可达方格105.for(int i=0; i<NumOfNbrs; i++)106. {107. nbr.row=here.row + offset[i].row;108. nbr.col=here.col+offset[i].col;109.110.if(grid[nbr.row][nbr.col]==0)//该方格未被标记111. {112. grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; 113.if((nbr.row==finish.row) && (nbr.col==finish.col)) 114. {115.break; //完成布线116. }117. Q.Add(nbr);118. }119. }120.//是否到达目标位置finish？121.if((nbr.row==finish.row) && (nbr.col==finish.col))122. {123.break;//完成布线124. }125.126.//活结点队列是否非空？127.if(Q.IsEmpty())128. {129.return false;//无解130. }131. Q.Delete(here);//取下一个扩展结点132. }while(true);133.134.//构造最短布线路径135. PathLen=grid[finish.row][finish.col]-2;136. path=new Position[PathLen];//从目标位置finish开始向起始位置回溯137. here=finish;138.for(int j=PathLen-1; j>=0; j--)139. {140. path[j]=here;//找前驱位置141.for(int i=0; i<NumOfNbrs; i++) 142. {143. nbr.row=here.row+offset[i].row; 144. nbr.col=here.col+offset[i].col; 145.if(grid[nbr.row][nbr.col]==j+2) 146. {147.break;148. }149. }150. here=nbr;//向前移动151. }152.return true;153.}程序运行结果如图：。

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实验报告实验项目实验五实验类别验证性学生姓名王龙学生学号201400797 完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。

【实验性质】验证性实验。

【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用一个数组存起来.Fenzhi函数: 由于先前赋值时, 用一个二维数组将结点的有向图标记存起来了( 有边为1, 无边为0 ),并且又用另外一个二维数组将其权重存起来了; 首先, 通过双重for循环, 通过if语句判断, 如果标记为1, 并且相加的权重小于先前最优权重( 在初始化的时候, 对最优权重赋上一个最大值 ), 则求得最优权重, 并且用一维数组将权重存起来, 而且用一维数组将前驱结点存起来.你然后, 一直循环下去, 直到循环到目的结点.【程序代码】for (z=0; z<k; z++){scanf ("%d %d %d", &i, &j, &m);t[i][j] = m;ti[i][j] = 1;}for (i = 0; i < n; i++) //初始化数组{d[i] = 99; // 赋个最大值s[i] = -1;}}void fenzhi (int d[], int s[],int t[][MAX], int ti[][MAX], int n, int k) {int i, j, zi;d[0]=0; s[0]=-1;for (i=0; i<n; i++){printf ("当前扩展节点：%d，权重：%d : \n", i, d[i]);for (j=0; j<n; j++){if (ti[i][j] == 1 ){if ( d[j]>t[i][j]+d[i]){d[j]=t[i][j]+d[i]; //最短长度s[j]=i; //前驱结点}if (j != n /* && j != 6 */ )printf ("入队结点：%d ,最优权重：%d \n", j, d[j]);}}printf ("\n");}}void output (int d[], int s[], int n){int i, j=0, zi[MAX];printf ("从源点到各个结点的最短路径: \n");for (i=0; i<n; i++)printf ("dist[%d] = %d \n", i, d[i]);printf ("\n");printf ("从源点到终点的最短路径长度为: %d \n", d[n-1]);printf ("其路径为: %d ", n-1);zi[j] = s[n-1];printf ("----> %d ", zi[j]);while (zi[j] != 0){j++;zi[j] = s[zi[j-1]];printf ("----> %d ", zi[j]);}printf ("\n");}【运行结果】图1 输入数据图2 输出扩展结点图3 最终结果【算法分析】本程序的主要函数ShorestPaths的时间复杂度为: O ( n * (n-1) ), 最坏时间复杂度为: O ( n*n )【实验总结】。

拉斯维加斯算法结合分枝限界算法解决电路板布线问题一、算法说明：拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。

由于这个算法比较难懂，没有思路编写。

于是就先学习-- Las Vegas 算法解决N皇后问题，Las Vegas解决N皇后问题是采用随机放置位置策略和结合分枝限界相结合。

综合解决方案电路板布线问题采用了机放置位置策略和结合分枝限界相结合的方式来解决。

关键代码如下：* 标号①处：这里是当前点相邻四个点是否可以放置，如果可以放置用selectPostion保存下来，并用num记录有多少个位置可以放置。

* 标号②处：这里利用上面保存的可以放置的点，然后随机取其中一个加入队列。

这就是Las Vegas的精髓！* 标号③处：是初始化时间种子，是随机选择的关键，这个虽然简单，但是由于随机函数不了解，造成了很大伪随机。

srand( (unsigned)time( NULL ) );//初始化时间种子----------③int num=0;//方格未标记个数Position selectPostion[5]; //选择可以到达位置保存for(int i=0; i<NumNeighBlo; i++){//达到四个方向nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==-1){//该方格未标记grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;selectPostion[num].row=nbr.row; ----------①selectPostion[num].col=nbr.col;num++;}}if(num >0) //如果标记，则在这么多个未标记个数中随机选择一个位置//将这个邻居入队q_FindPath.push(selectPostion[rand()%(num)]); ---------- ②二、结果分析红色字表示输入蓝色字表示输出结果运行时间表示算法复杂度1）样例一：3*3 棋盘---------分支限界法之布线问题--------在一个m*n的棋盘上，请分别输入m和n,代表行数和列数，然后输入回车3 3 （回车）初始化棋盘格和加围墙--------------- -----------------2 -2 -2 -2 -2-2 -1 -1 -1 -2-2 -1 -1 -1 -2-2 -1 -1 -1 -2-2 -2 -2 -2 -2-------------------------------请输入已经占据的位置行坐标列坐标,代表此位置不能布线例如输入 2 2 表示坐标 2 2 不能布线;当输入的坐标为 0 0 表示结束输入2 1（回车）2 3（回车）3 3（回车）0 0（回车）布线前的棋盘格--------------------------------2 -2 -2 -2 -2-2 -1 -1 -1 -2-2 -3 -1 -3 -2-2 -1 -1 -3 -2-2 -2 -2 -2 -2-------------------------------请输入起点位置坐标1 1（回车）请输入终点位置坐标3 1（回车）没有找到路线,第1次尝试没有找到路线,第2次尝试没有找到路线,第3次尝试-------------------------------$ 代表围墙# 代表已经占据的点* 代表布线路线= 代表还没有布线的点-------------------------------$ $ $ $ $$ * * = $$ # * # $$ * * # $$ $ $ $ $-------------------------------路径坐标和长度(1,1) (1,2) (2,2) (3,2) (3,1)路径长度：5布线完毕,查找4次运行时间: 12 ms2）样例二：5*5 棋盘---------分支限界法之布线问题--------在一个m*n的棋盘上，请分别输入m和n,代表行数和列数5 5（回车）初始化棋盘格和加围墙--------------- -----------------2 -2 -2 -2 -2 -2 -2-2 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -2-2 -2 -2 -2 -2 -2 -2-------------------------------请输入已经占据的位置行坐标列坐标,代表此位置不能布线例如输入 2 2 表示坐标 2 2 不能布线;当输入的坐标为 0 0 表示结束输入3 1（回车）3 2（回车）3 4（回车）3 5（回车）4 5（回车）0 0（回车）布线前的棋盘格--------------------------------2 -2 -2 -2 -2 -2 -2-2 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -2-2 -3 -3 -1 -3 -3 -2-2 -1 -1 -1 -1 -3 -2-2 -1 -1 -1 -1 -1 -2-2 -2 -2 -2 -2 -2 -2-------------------------------请输入起点位置坐标1 1（回车）请输入终点位置坐标5 2（回车）没有找到路线,第1次尝试没有找到路线,第2次尝试没有找到路线,第3次尝试没有找到路线,第4次尝试没有找到路线,第5次尝试没有找到路线,第6次尝试-------------------------------$ 代表围墙# 代表已经占据的点* 代表布线路线= 代表还没有布线的点-------------------------------$ $ $ $ $ $ $$ * = = = = $$ * * * = = $$ # # * # # $$ = = * = # $$ = * * = = $$ $ $ $ $ $ $-------------------------------路径坐标和长度(1,1) (2,1) (2,2) (2,3) (3,3) (4,3) (5,3) (5,2) 路径长度：8布线完毕,查找7次运行时间: 16 ms3）样例三：10*10棋盘---------分支限界法之布线问题--------在一个m*n的棋盘上，请分别输入m和n,代表行数和列数10 10（回车）初始化棋盘格和加围墙--------------- -----------------2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2-------------------------------请输入已经占据的位置行坐标列坐标,代表此位置不能布线例如输入 2 2 表示坐标 2 2 不能布线;当输入的坐标为 0 0 表示结束输入5 1（回车）5 2（回车）5 3（回车）5 4（回车）5 5（回车）5 7（回车）5 8（回车）5 9（回车）0 0（回车）布线前的棋盘格--------------------------------2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -3 -3 -3 -3 -3 -1 -3 -3 -3 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2-2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -------------------------------请输入起点位置坐标1 1（回车）请输入终点位置坐标9 9（回车）没有找到路线,第1次尝试没有找到路线,第2次尝试没有找到路线,第3次尝试没有找到路线,第4次尝试没有找到路线,第5次尝试没有找到路线,第6次尝试没有找到路线,第7次尝试------------------------------- $ 代表围墙# 代表已经占据的点* 代表布线路线= 代表还没有布线的点------------------------------- $ $ $ $ $ $ $ $ $ $ $ $$ * = = = = = * * = = $$ * * * * * * * * * * $$ = = = = = = = = = * $$ = = = = = * * * * * $$ # # # # # * # # # = $$ = = = = = * = = = = $$ = = = = = * = = = = $$ = = = = = * = = = = $$ = = = = = * * * * = $$ = = = = = = = = = = $$ $ $ $ $ $ $ $ $ $ $ $-------------------------------路径坐标和长度(1,1) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (1,7) (1,8) (2,8) (2,9) (2,10) (3,10) (4,10) (4,9) (4,8) (4,7) (4,6) (5,6) (6,6) (7,6) (8,6) (9,6) (9,7) (9,8) (9,9)路径长度：27布线完毕,查找8次运行时间: 31 ms代码：#include<queue>#include<iostream>#include <time.h>#include<stdio.h>#include<stdlib.h>#include <windows.h>#include<math.h>using namespace std;//表示方格上位置的结构体struct Position{int row;int col;};//分支限界算法bool FindPath(Position start,Position finish,int& PathLen,Position *&path,int **grid,int m,int n){//找到最短布线路径，则返回真，否则返回假//起点和终点想同，不用布线if((start.row==finish.row) && start.col==finish.col){PathLen=0;return true;}//设置方向移动坐标值：东、南、西、北Position offset[4];offset[0].row=0;offset[0].col=1; //右offset[1].row=1;offset[1].col=0; //下offset[2].row=0;offset[2].col=-1; //左offset[3].row=-1;offset[3].col=0; //上//相邻的方格数int NumNeighBlo=4;Position here,nbr;//设置当前方格，即搜索单位here.row=start.row;here.col=start.col;//由于0和1用于表示方格的开放和封锁，故距离：2-0 3-1grid[start.row][start.col]=0; //-2 表示强 -1表示可行 -3表示不能当作路线//队列式搜索，标记可达相邻方格queue<Position> q_FindPath;do{int num=0;//方格未标记个数Position selectPostion[5]; //选择位置保存for(int i=0; i<NumNeighBlo; i++){//达到四个方向nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==-1){//该方格未标记grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row)&&(nbr.col==finish.col))break;selectPostion[num].row=nbr.row;selectPostion[num].col=nbr.col;num++;}}// printf("---------%lld\n",num);if(num >0) //如果标记，则在这么多个未标记个数中随机选择一个位置//随机选一个入队// printf("---------%d\n",rand()%(num));q_FindPath.push(selectPostion[rand()%(num)]);//是否到达目标位置finishif((nbr.row==finish.row)&&(nbr.col==finish.col))break;//活结点队列是否为空if(q_FindPath.empty())return false; //无解//访问对首元素出队here=q_FindPath.front();q_FindPath.pop();} while(true);//构造最短布线路径PathLen=grid[finish.row][finish.col];path=new Position[PathLen]; //路径//从目标位置finish开始向起始位置回溯here=finish;for(int j=PathLen-1; j>=0; j--){path[j]=here;//找前驱位置for (int i = 0; i <=NumNeighBlo; i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==j) //距离加2正好是前驱位置 break;}here=nbr;}return true;}int main(){cout<<"---------分支限界法之布线问题--------"<<endl;int path_len;int path_len1;int m,n;Position *path;Position *path1;Position start,finish;Position start1,finish1;cout<<"在一个m*n的棋盘上，请分别输入m和n,代表行数和列数，然后输入回车"<<endl;cin>>m>>n;//创建棋盘格int **grid = new int*[m+2];int **grid1 = new int*[m+2];for(int i=0; i < m+2; i++){grid[i] = new int[n+2];grid1[i] = new int[n+2];}//初始化棋盘格for(int i=1; i <= m; i++){for(int j=1; j <=n; j++){grid[i][j]=-1;}}//设置方格阵列的围墙for(int i=0; i<=n+1; i++){grid[0][i]=grid[m+1][i]=-2;//上下的围墙}for(int i=0; i<=m+1; i++){grid[i][0]=grid[i][n+1]=-2;//左右的围墙}cout<<"初始化棋盘格和加围墙"<<endl;cout<<"--------------- ----------------"<<endl;for(int i=0; i < m+2; i++){for(int j=0; j <n+2; j++){cout<<grid[i][j]<<" ";}cout<<endl;}cout<<"-------------------------------"<<endl;cout<<"请输入已经占据的位置行坐标列坐标,代表此位置不能布线"<<endl;cout<<"例如输入 2 2（然后输入回车），表示坐标 2 2 不能布线;当输入的坐标为 0 0（然后输入回车）表示结束输入"<<endl;//添加已经布线的棋盘格while(true){int ci,cj;cin>>ci>>cj;if(ci>m||cj>n){cout<<"输入非法";cout<<"行坐标 < "<<m<<" ,列坐标< "<<n<<" 当输入的坐标为0,0，结束输入"<<endl;continue;}else if(ci==0||cj==0){break;}else{grid[ci][cj]=-3;}}//布线前的棋盘格cout<<"布线前的棋盘格"<<endl;cout<<"-------------------------------"<<endl;for(int i=0; i < m+2; i++){for(int j=0; j <n+2; j++){cout<<grid[i][j]<<" ";}cout<<endl;}cout<<"-------------------------------"<<endl;cout<<"请输入起点位置坐标"<<endl;cin>>start.row>>start.col;cout<<"请输入终点位置坐标"<<endl;cin>>finish.row>>finish.col;DWORD startTime, stopTime;startTime = GetTickCount();//程序开始时间srand( (unsigned)time( NULL ) );int time=0; //为假设运行次数// 初始值值拷贝start1=start;finish1=finish;path_len1=path_len;path1=NULL;for(int i=0; i < m+2; i++){for(int j=0; j <n+2; j++){grid1[i][j]=grid[i][j];}}bool result=FindPath(start1,finish1,path_len1,path1,grid1,m,n); while(result==0 && time < 100 ){// 初始值值拷贝start1=start;finish1=finish;path_len1=path_len;path1=NULL;for(int i=0; i < m+2; i++){for(int j=0; j <n+2; j++){grid1[i][j]=grid[i][j];}}time++;cout<<endl;cout<<"没有找到路线,第"<<time<<"次尝试"<<endl;result=FindPath(start1,finish1,path_len1,path1,grid1,m,n); }stopTime = GetTickCount();//程序结束时间if(result){cout<<"-------------------------------"<<endl;cout<<"$ 代表围墙"<<endl;cout<<"# 代表已经占据的点"<<endl;cout<<"* 代表布线路线"<<endl;cout<<"= 代表还没有布线的点"<<endl;cout<<"-------------------------------"<<endl;for(int i=0; i <= m+1; i++){for(int j=0; j <=n+1; j++){if(grid1[i][j]==-2){cout << "$ ";}else if(grid1[i][j]==-3){cout << "# ";}else{int r;for(r = 0; r < path_len1; r++){if(i==path1[r].row && j==path1[r].col){cout << "* ";break;}if(i == start1.row && j == start1.col){cout << "* ";break;}}if(r == path_len1)cout << "= ";}}cout << endl;}cout<<"-------------------------------"<<endl;cout<<"路径坐标和长度"<<endl;cout<<endl;cout<<"("<<start1.row<<","<<start1.col<<")"<<" ";for(int i=0; i<path_len1; i++){cout<<"("<<path1[i].row<<","<<path1[i].col<<")"<<" "; }cout<<endl;cout<<endl;cout<<"路径长度："<<path_len1+1<<endl;cout<<endl;time++;cout<<"布线完毕,查找"<<time<<"次"<<endl;printf("运行时间: %lld ms\n", stopTime - startTime);}else{cout<<endl;cout<<"经过多次尝试，仍然没有找到路线"<<endl;}system("pause");return 0;}。

分支限界法是一种常用的解决组合优化问题的算法，它通过不断扩展当前解空间的分支节点，并通过限界函数对分支节点进行剪枝，最终找到最优解。

在本文中，我们将使用C++语言实现分支限界法来解决电路板排列问题。

电路板排列问题是一个经典的组合优化问题，其目标是将给定数量的电路板排列在一个给定大小的板子上，使得每块电路板之间不发生重叠。

假设每块电路板都是矩形形状，那么问题就是确定每块电路板在板子上的位置和角度，使得它们不重叠，并尽可能地节省空间。

现在让我们通过C++语言来实现分支限界法来解决电路板排列问题。

1. 设计电路板类我们首先需要设计一个电路板类，用来表示每块电路板的属性，包括长度、宽度、位置和角度等。

以下是电路板类的定义：```cppclass CircuitBoard {public:int length; // 电路板长度int width; // 电路板宽度int x; // 电路板左上角x坐标int y; // 电路板左上角y坐标float angle; // 电路板旋转角度};```2. 实现分支限界法接下来，我们需要实现分支限界法来解决电路板排列问题。

我们将通过递归的方式来搜索最优解，具体步骤如下：- 初始化一个优先队列，用来存储待扩展的分支节点。

- 将初始节点加入优先队列中。

- 当优先队列不为空时，循环执行以下步骤：- 从优先队列中取出一个节点。

- 判断该节点是否为叶子节点，如果是则更新最优解。

- 否则，对该节点进行扩展，计算每个子节点的限界值，并将其加入优先队列中。

- 继续循环直到找到最优解或者遍历完所有节点。

3. 编写C++代码现在让我们编写C++代码来实现上述算法。

```cpp#include <iostream>#include <vector>#include <queue>using namespace std;class CircuitBoard {public:int length; // 电路板长度int width; // 电路板宽度int x; // 电路板左上角x坐标int y; // 电路板左上角y坐标float angle; // 电路板旋转角度};bool isOverlap(const CircuitBoard board1, const CircuitBoard board2) {// 判断两块电路板是否重叠// ...}int boundingFunction(const vector<CircuitBoard>currentSolution, const vector<CircuitBoard> rem本人ningBoards) {// 计算限界值// ...}void branchAndBound(const vector<CircuitBoard> initialBoards, int boardCount, int boardWidth, int boardLength) {priority_queue<vector<CircuitBoard>,vector<vector<CircuitBoard>>,pare> pq;vector<CircuitBoard> currentSolution;vector<CircuitBoard> rem本人ningBoards = initialBoards;int bestSolution = INT_MAX;pq.push(initialBoards);while (!pq.empty()) {vector<CircuitBoard> currentNode = pq.top();pq.pop();if (currentNode.empty()) {bestSolution = min(bestSolution,calculateSolution(currentSolution));} else {vector<CircuitBoard> leftNode =expandNode(currentNode, true);vector<CircuitBoard> rightNode =expandNode(currentNode, false);int boundLeft = boundingFunction(leftNode, rem本人ningBoards);int boundRight = boundingFunction(rightNode, rem本人ningBoards);if (boundLeft < bestSolution) {pq.push(leftNode);}if (boundRight < bestSolution) {pq.push(rightNode);}}}}int m本人n() {// 读入电路板信息// ...// 调用分支限界法求解// ...return 0;}```4. 总结在本文中，我们使用C++语言实现了分支限界法来解决电路板排列问题。

布线问题（分⽀限界法）⼀、⾸先说⼀下分⽀限界法的思想：（1）⽐较：分⽀限界法和回朔法有相似之处，但是回朔法是搜索问题的所有解，采⽤深度优先搜索；⽽分⽀限界法是搜索问题的最优解，采⽤的是⼴度优先搜索；（2）核⼼思想：分⽀限界法中，每⼀个活节点都只有⼀次机会成为扩展节点。

活节点⼀旦成为扩展节点，就⼀次性产⽣所有的⼉⼦节点。

在这些⼉⼦节点中，导致不可⾏解或者导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活节点表中。

此后，从活节点表中取下⼀节点成为当前扩展节点，并重复上述节点的扩展过程。

这个过程⼀直在持续到找到所需要的最优解或者活节点表为空时为⽌；其中：选择扩展节点的⽅式可以分为：队列式分⽀限界法和优先队列式分⽀限界法。

后者相对于前者的改进是对活节点加⼊了优先级，优先级最⾼的成为扩展节点（通常通过最⼤堆最⼩堆实现）；⼆、布线问题描述：代码如下：//队列类 : LinkedQueue.h#ifndef LINKEDQUEUE_H#define LINKEDQUEUE_Htemplate <class Type>class LinkedQueue{public:LinkedQueue(){};explicit LinkedQueue(int Capacity); //创建队列bool IsEmpty(); //判断是否空bool IsFull(); //判断是否满bool Add(Type &cell); //向队列中加⼊元素bool Delete(Type &cell); //删除队列中的元素~LinkedQueue();private:Type cell;Type *ptr; //队列中的元素指针int QueueLen; //队列元素个数int QueueCapacity; //队列容量int Head;int Tail;};template <class Type>LinkedQueue<Type>::~LinkedQueue(){delete[]ptr;ptr = nullptr;}template <class Type>LinkedQueue<Type>::LinkedQueue(int Capacity){QueueCapacity = Capacity;Head = 0;Tail = 0;QueueLen = 0;ptr = new Type[QueueCapacity];}template <class Type>bool LinkedQueue<Type>::IsEmpty(){if (QueueLen == 0)return true;elsereturn false;}template <class Type>bool LinkedQueue<Type>::IsFull(){if (QueueLen == QueueCapacity)return true;elsereturn false;}template <class Type>bool LinkedQueue<Type>::Add(Type &cell){if (IsFull())return false;else{ptr[Tail] = cell;Tail++;QueueLen++;return true;}}template <class Type>bool LinkedQueue<Type>::Delete(Type &cell){if (IsEmpty())return false;else{cell = ptr[Head];Head++;QueueLen--;return true;}}#endif//使⽤分⽀限界法解决布线问题main.cpp//====================================================#include <iostream>#include "LinkedQueue.h"//#include <queue>using namespace std;int n, m; //布线盘是n * m⼤⼩class Position{public:int row;int col;};bool FindPath(int ** grid , Position start, Position finish, int &PathLen, Position * &path) {//计算从起始位置start到⽬标位置finish的最短布线路径//找到最短布线路径则返回true，否则返回flaseif ((start.row == finish.row) && (start.col == finish.col)){PathLen = 0;return true;}//设置⽅格阵列“围墙”for (int i = 0; i < m + 1; i++){grid[0][i] = grid[n + 1][i] = 1; //顶部和底部}for (int i = 0; i < n + 1; i++){grid[i][0] = grid[i][m + 1] = 1; //左翼和右翼}//初始化相对位移Position offset[4];offset[0].row = 0; offset[0].col = 1; //右offset[1].row = 1; offset[1].col = 0; //下offset[2].row = 0; offset[2].col = -1; //左offset[3].row = -1; offset[3].col = 0; //上int neigh_num = 4; //相邻⽅格数Position here, nbr;here.row = start.row;here.col = start.col;grid[start.row][start.col] = 2;//标记所有可以到达的⽅格位置LinkedQueue<Position> Q(n * m + 1); //队列//queue<Position> Q(); //队列//标记可到达的相邻⽅格do {for (int i = 0; i < neigh_num; i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if (grid[nbr.row][nbr.col] == 0) //该⽅格未被锁定{grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;if ((nbr.row == finish.row) && (nbr.col == finish.col)) //完成布线break;Q.Add(nbr); //压⼊队列称为活节点}}//是否到达⽬标位置finish?if ((nbr.row == finish.row) && (nbr.col == finish.col)) //完成布线,是否要加这⼀步？ break;//活节点队列是否⾮空if (Q.IsEmpty()) //⽆解return false;Q.Delete(here); //取下⼀个扩展节点} while (true);//构造最短布线路径PathLen = grid[finish.row][finish.col] - 2;path = new Position[PathLen];//从⽬标位置finish开始向起始位置回溯here = finish;for (int j = PathLen - 1; j >= 0; j--){path[j] = here;//找前驱位置for (int i = 0; i < neigh_num; i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if (grid[nbr.row][nbr.col] == j + 2)break;}here = nbr; //向前移动}return true;}int main(void){Position start, finish; //开始位置和⽬标位置int PathLen; //最短路径的长度Position *path; //记录的最短路径cout << "请输⼊布线盘的⼤⼩，n * m 规格： " << endl;cin >> n >> m;cout << "请输⼊开始位置(x , y) :" << endl;cin >> start.col >> start.row;cout << "请输⼊结束位置(x , y) :" << endl;cin >> finish.col >> finish.row;int ** grid = new int*[n + 2];for (int i = 0; i < n + 2; i++){grid[i] = new int[m + 2];}for (int i = 0; i < n + 2; i++){for (int j = 0; j < m + 2; j++){grid[i][j] = 0;}}FindPath(grid, start, finish, PathLen, path);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << grid[i][j] << " ";}cout << endl;}cout << "最短路径是： " << endl;cout << PathLen << endl;system("pause");return 0;}效果图类似：。

分支限界法典型例题分支限界法(Branch and Bound)是一种常见的算法分析技术,用于解决搜索问题和动态规划问题。

以下是一些分支限界法的典型例题:1. 最长公共子序列(LCS):求给定两个字符串的最长公共子序列。

可以使用分支限界法,首先找出两个字符串中的不同字符出现的次数,然后用哈希表存储这些计数器。

最后,遍历哈希表中的每个计数器,找到最大的计数器的值,即为最长公共子序列的长度。

2. 背包问题(Knapsack problem):给定一个背包,容量为64,有多个选项,每个选项的重量和容量不限。

求给定背包中可以放入的最大重量的背包物品。

可以使用分支限界法,首先列出所有可能背包容量的组合,然后用枚举法找出每个背包容量下可以放入的最大重量的物品,最后计算出可以放入的最大重量的物品数量。

3. 最短路径问题(Shortest Path problem):给定一个二维图,目标为找到从源点出发,到达所有目标点的路径。

可以使用分支限界法,首先找出图中的所有节点和它们之间的联系,然后用递归算法计算每个节点到源点的路径。

最后,通过剪枝,可以找到最短路径。

4. 最大子数组和问题(Maximum Subarray and Problem):给定一个数组,求出其中任意一个元素的最大值。

可以使用分支限界法,首先找出数组中的最小值和最大值,然后用递归算法计算每个元素的最大值。

最后,通过剪枝,可以找到最大子数组和问题。

5. 模拟退火问题(Simulated Annealing Problem):给定一个概率分布,求出在一定条件下,随机变量的取值分布。

可以使用分支限界法,首先找出概率分布中所有可能的取值,然后用模拟退火算法计算在这些取值中随机变量的取值分布。

最后,通过剪枝,可以找到最优解。

算法设计与分析实验指导书（计算机科学与技术系）编写兰州交通大学电子与信息工程学院2018年3月目录实验7 分支限界法-1 (3)一、实验目的 (3)二、实验仪器设备 (3)三、实验原理 (3)四、实验内容及注意事项 (3)五、实验步骤 (3)5.1 装载问题 (3)1）最基本的队列式分支限界法。

(3)2) 改进的队列式分支限界法 (4)3）队列式分支限界法，包含最优解 (5)4) 优先队列式分支限界法，包含最优解。

(8)六、实验数据整理与结果分析 (10)七、实验总结 (11)八、实验报告 (11)实验7 分支限界法-1一、实验目的（1）掌握分支限界法的各种不同的具体方法，包括队列式、改进的队列式以及优先队列式的区别。

（2）通过实验掌握分支限界法思想和方法；（3）培养学生的动手能力。

二、实验仪器设备（1）计算机；（2）C++编译调试环境。

三、实验原理掌握将算法转换为可运行程序的步骤。

四、实验内容及注意事项(1）装载问题。

五、实验步骤5.1 装载问题1）最基本的队列式分支限界法。

只计算最优值，没有计算最优解。

#include"stdafx.h"#include<cstdlib>#include<iostream>#include<queue>using namespace std;//子函数，将当前活节点加入队列template<class Type>void EnQueue(queue<Type> &Q, Type wt, Type &bestw, int i, int n){if (i == n) //可行叶结点{if (wt>bestw) bestw = wt;}else Q.push(wt); //非叶结点}//装载问题先尽量将第一艘船装满//队列式分支限界法，返回最优载重量template<class Type>Type MaxLoading(Type w[], Type c, int n){//初始化数据queue<Type> Q; //保存活节点的队列Q.push(-1); //-1的标志是标识分层int i = 1; //i表示当前扩展节点所在的层数Type Ew = 0; //Ew表示当前扩展节点的重量Type bestw = 0; //bestw表示当前最优载重量//搜索子集空间树while (true){if (Ew + w[i] <= c) //检查左儿子EnQueue(Q, Ew + w[i], bestw, i, n); //将左儿子添加到队列//将右儿子添加到队列即表示不将当前货物装载在第一艘船EnQueue(Q, Ew, bestw, i, n);Ew = Q.front(); Q.pop(); //取下一个节点为扩展节点并将重量保存在Ewif (Ew == -1) //检查是否到了同层结束{if (Q.empty()) return bestw; //遍历完毕，返回最优值Q.push(-1); //添加分层标志Ew = Q.front(); Q.pop(); //删除分层标志，进入下一层i++;}}return bestw;}int main(int argc, char* argv[]){int w[5] = { 0, 1, 2, 3 };int c = 5;int n = 3;int bestp = MaxLoading(w, c, n);cout << "best p=" << bestp << endl;return 0;}2) 改进的队列式分支限界法加入了进入右子树的上界函数。

第1篇一、实验目的1. 理解并掌握分枝限界法的基本原理和实现方法。

2. 通过实际编程，运用分枝限界法解决实际问题。

3. 比较分析分枝限界法与其他搜索算法（如回溯法）的优缺点。

4. 增强算法设计能力和编程实践能力。

二、实验内容本次实验主要涉及以下内容：1. 分支限界法的基本概念和原理。

2. 分支限界法在单源最短路径问题中的应用。

3. 分支限界法的实现步骤和代码编写。

4. 分支限界法与其他搜索算法的对比分析。

三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 算法描述：分支限界法是一种用于解决组合优化问题的算法，其基本思想是在问题的解空间树中，按照一定的搜索策略，优先选择有潜力的节点进行扩展，从而减少搜索空间，提高搜索效率。

2. 程序代码：下面是使用Python实现的分支限界法解决单源最短路径问题的代码示例：```pythonimport heapqclass Node:def __init__(self, vertex, distance, parent): self.vertex = vertexself.distance = distanceself.parent = parentdef __lt__(self, other):return self.distance < other.distancedef branch_and_bound(graph, source):初始化优先队列和已访问节点集合open_set = []closed_set = set()添加源节点到优先队列heapq.heappush(open_set, Node(source, 0, None))主循环，直到找到最短路径while open_set:弹出优先队列中最小距离的节点current_node = heapq.heappop(open_set)检查是否已访问过该节点if current_node.vertex in closed_set:continue标记节点为已访问closed_set.add(current_node.vertex)如果当前节点为目标节点，则找到最短路径if current_node.vertex == target:path = []while current_node:path.append(current_node.vertex)current_node = current_node.parentreturn path[::-1]遍历当前节点的邻居节点for neighbor, weight in graph[current_node.vertex].items():if neighbor not in closed_set:计算新节点的距离distance = current_node.distance + weight添加新节点到优先队列heapq.heappush(open_set, Node(neighbor, distance, current_node))没有找到最短路径return None图的表示graph = {0: {1: 2, 2: 3},1: {2: 1, 3: 2},2: {3: 2},3: {1: 3}}源节点和目标节点source = 0target = 3执行分支限界法path = branch_and_bound(graph, source)print("最短路径为：", path)```3. 调试与测试：在编写代码过程中，注意检查数据结构的使用和算法逻辑的正确性。

分支限界法c语言
分支限界法是一种解决最优化问题的算法，它通过将问题不断分解成子问题，每次只考虑其中一部分，从而逐步缩小搜索空间，最终得到最优解。

在c语言中，可以利用递归函数来实现分支限界法的搜索过程。

首先，需要定义一个结构体来表示每个状态，其中需要包含当前状态的值、已经选择的路径、以及当前状态所能达到的下一步状态。

然后，定义一个优先队列来存储当前状态的所有可能下一步状态，按照优先级从高到低进行排序，以便在搜索过程中优先考虑最优解。

接下来，开始搜索过程。

从初始状态出发，每次选取优先队列中优先级最高的状态进行扩展，即生成其所有可达的下一步状态，并将它们加入到优先队列中。

重复这个过程，直到找到最优解或者队列为空。

最后，输出最优解即可。

总之，分支限界法是一种非常实用的优化算法，在解决各种最优化问题时都有广泛的应用。

在c语言中，可以通过递归函数和优先队列来实现分支限界法的搜索过程，实现高效、可靠的最优解求解。

- 1 -。

摘要分支限界算法对很多实际问题是重要和有效的。

论文首先提出了一类电路布线问题，然后给出了解决该问题的分支限界算法并分析了所给出算法的复杂度。

实验结果验证了所提出方法的有效性。

关键字：分支限界算法电路布线问题复杂度ABSTRACTThe branch-and-bound algorithm is an important and efficient method to many problems．In this paper，a kind of circuit wiring problem is brought up firstly，and then an efficient algorithm based on branch—and-bound algorithm is presented．Finally，the complexity of the proposed algorithm is analyzedSimulation results show they are efective．Keywords：branch and bound algorithm，circuit wiring problem，complexit目录摘要 (1)ABSTRACT (1)1 引言 (3)2布线问题的提出 (3)3问题的算法选择 (3)4分支限界算法 (4)（1）FIFO搜索（2）LIFO搜索（3）优先队列式搜索5 布线问题的分支限界算法设计 (4)（1）初始化部分（2）用FIFO分支搜索的过程（3）可布线未知的识别（4）队列的结构类型和操作（5）实例与测试结果（6）复杂性分析6结束语 (6)7 致谢 (7)8 参考文献 (7)9 附录 (7)1 引言随着信息技术的发展和嵌入式设备的广泛使用．电路布线问题越来越受到人们的重视．要使电子电路获得最佳性能．不仅元器件的布置占有着重要的地位．而且导线的布设也是非常重要的．特别是在涉及到线路成本的布线方案中．一个好的布线算法就显得尤为重要本文首先对一类电路板低成本布线问题进行了分析．进而给出了解决这一问题的分支限界解法．并对所提出算法的时间复杂度进行了分析和讨论。

#include<iostream>#include<queue>#include<fstream>using namespace std;//import the grid data;ifstream fin("map.txt");//这个map是7行7列，请以这个为例子来理解这个程序typedef struct Position{int row;int col;} Posi;//find the shortest path for the gridbool FindPath(Posi start,Posi finish,int & PathLen,int **&grid,Posi *& path,int n,int m) {//if the start position is the finish positionif((start.row == finish.row) && (start.col == finish.col)){PathLen = 0;return true;}Position offset[4];offset[0].row = -1;//upoffset[0].col = 0;offset[1].row = 1;//downoffset[1].col = 0;offset[2].row = 0;//leftoffset[2].col = -1;offset[3].row = 0;//rightoffset[3].col = 1;Posi here,nbr;here.row = start.row;here.col = start.col;int NumOfNbrs = 4;//ajacent position;grid[start.row][start.col] = 2;//init the start position's length with value 2,queue<Posi> Q;do{for(int firdex = 0;firdex < NumOfNbrs;firdex++){nbr.row = here.row + offset[firdex].row;nbr.col = here.col + offset[firdex].col;if(grid[nbr.row][nbr.col] == 0)//this position haven't been visted{grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;if((nbr.row == finish.row) && (nbr.col == finish.col))//find the shortest path{break;}Q.push(nbr);}}if((nbr.row == finish.row) && (nbr.col ==finish.col)){break;//wiring was completed}if(Q.empty())//if queue is empty{return false;//no result}here = Q.front();Q.pop();}while(true);//traceback the shortest pathPathLen = grid[finish.row][finish.col]-2;path = new Posi[PathLen];here = finish;for(int firdex = PathLen-1;firdex >=0;firdex--){path[firdex] = here;for(int secdex = 0;secdex < NumOfNbrs;secdex++){nbr.row = here.row + offset[secdex].row;nbr.col = here.col + offset[secdex].col;if(grid[nbr.row][nbr.col] == firdex+2)//It is the nbr's grid that why the grid[nbr.row][nbr.col] can give index of "firdex+2"{break;}}here =nbr;//move to the previous node}return true;}//allocate memory for the gridvoid InitGrid(int **&grid,int n,int m){grid = new int*[n+2];for(int firdex = 0;firdex < n+2;firdex++)grid[firdex] = new int[m+2];//set the boundfor(int index = 0;index < m+2;index++)//top an bottom {grid[0][index] = grid[n+1][index] =1;}for(int index = 0;index < n+2;index++){grid[index][0] = grid[index][m+1] = 1;}for(int firdex = 1;firdex < n+1;firdex++){for(int secdex = 1;secdex < m+1;secdex++)fin>>grid[firdex][secdex];}}//destroy the resource for the gridvoid Destroy(int ** &grid,int n,int m){if(grid != NULL){for(int firdex = 0;firdex < n+2;firdex++){delete [] grid[firdex];grid[firdex] = NULL;}delete grid;grid = NULL;}}int main(void){int m = 0,n = 0;Posi start,finish;int PathLength = 0;Posi * path = NULL;int ** grid = NULL;cout<<"Please input the m and n of the grid:"<<endl;cin>>n>>m;cout<<"Please input the start position:"<<endl;cout<<"start:row =";cin>>start.row;cout<<"start:col =";cin>>start.col;cout<<"Please input the finish position:"<<endl;cout<<"finish:row =";cin>>finish.row;cout<<"finish:col =";cin>>finish.col;InitGrid(grid,n,m);cout<<"the map resource:"<<endl;for(int firdex = 1;firdex < n+1;firdex++){for(int secdex = 1;secdex < m+1;secdex++)cout<<grid[firdex][secdex]<<" ";cout<<endl;}cout<<endl;FindPath(start,finish,PathLength,grid,path,n,m);cout<<"The shortest path of wiring is :"<<PathLength<<endl;cout<<"The path if follow:"<<endl;for(int index = 0;index < PathLength;index++){cout<<"("<<path[index].row<<","<<path[index].col<<")";if(index < PathLength-1)cout<<"-->";}cout<<endl;//Destory the resource of gridDestroy(grid,n,m);//release the path's resourceif(path != NULL){delete [] path;path = NULL;}return 0;}。