爬山法、分支限界法求解哈密顿环问题

问题描述: （1）哈密顿环问题：输入是一个无向连通图G=(V,E)；如果G中存在哈密顿环则输出该环。 （2）最小哈密顿环问题：输入是一个无向连通图G=(V,E)，每个节点都没有到自身的边，每对节点间都有一条非负加权边；输出一个权值代价和最小的哈密顿环。注意：事实上输入图是一个完全图，因此哈密顿环是一定存在的。 实现哈密顿环搜索算法 （1）哈密顿环问题：(a)实现基于树的基本搜索算法(BFS,DFS) (b)爬山法 （2）最小哈密顿环问题：(a)实现求解最小哈密顿环问题的分支界限算法。 1.DFS 算法的主要步骤:  2.BFS 算法的主要步骤:  3.ClimbingHill 算法的主要步骤:  4.BranchBound 算法的主要原理:  源码： Grap.h ~~~ /* *Tree Search Strategy 15S103182 Ethan *2015.12.1 */ #include #include #include #include #include #include using namespace std; template //E为图中边的权值的数据类型 class Graph { private: int maxVertices; //图中最大顶点数 E **matrix;//邻接矩阵 public: E maxWeight; //代表无穷大的值 Graph(int sz);//创建SZ大小的基于邻接矩阵的图 ~Graph();//析构函数 int NumberOfVertices() { return maxVertices; //返回最大顶点数 } E getWeight(int v1, int v2); //取边（v1,v2)上的权值 int getFirstNeighbor(int v);//取顶点v的第一个邻接顶点 int getNextNeighbor(int v, int w);//取顶点v的邻接顶点W的下一个邻接顶点 int Init(istream &in);//根据用户输入，获得图的邻接矩阵 int RandInitN();//随机初始化图(无向图) int RandInit();//随机初始化图(完全无向图) int output(ostream &out); //输出图的矩阵到文件 int output(); //输出图的矩阵到控制台 }; template Graph::Graph(int sz) { //创建SZ大小的基于邻接矩阵的图 maxWeight = std::numeric_limits::max(); maxVertices = sz; matrix = new E *[sz]; for (int i = 0; i Graph::~Graph() { for (int i = 0; i E Graph::getWeight(int v1, int v2) { //取边（v1,v2)上的权值 if (v1 >= 0 && v1= 0 && v2 int Graph::getFirstNeighbor(int v) { //取顶点v的第一个邻接顶点 if (!(v >= 0 && v int Graph::getNextNeighbor(int v, int w) { //取顶点v的邻接顶点W的下一个邻接顶点 if (!(v >= 0 && v= 0 && w int Graph::Init(istream &fin) { //根据输入文件，获得图的邻接矩阵 int v1, v2; E edge; while (fin >> v1 >> v2 >> edge) { if (v1 >= 0 && v1= 0 && v2 int Graph::RandInitN() { //随机初始化图(无向图,非完全) for (int i = 0; i int Graph::RandInit() { //随机初始化图(无向完全图) for (int i = 0; i int Graph::output(ostream &out) { //输出图的矩阵 for (int i = 0; i int Graph::output() { //输出图的矩阵 for (int i = 0; i #include #include #include #include #include #include #include using namespace std; template struct NODE { int dep; //表示该结点在搜索树的第几层 int *vertices; //该节点包含的各个顶点 E length; //从根到当前结点已经走过的路径长度 NODE(int depth) { dep = depth; vertices = new int[dep]; }; void cpy(int *&des) { for (int i = 0; i int dfs(int start, Graph &myGraph) { //deepFirst 判断图中是否存在哈密顿回路 stack myStack; myStack.push(start); int numVertices = myGraph.NumberOfVertices(); bool *visited = new bool[numVertices]; memset(visited, false, numVertices); int v; int w = -1; while (!myStack.empty()) { //栈不为空 v = myStack.top(); visited[v] = true; if (w == -1) { w = myGraph.getFirstNeighbor(v); } else { w = myGraph.getNextNeighbor(v, w); } for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {} if (w == -1) { //未找到可行的下一个顶点,子节点都在栈中 myStack.pop(); //回溯 w = v; visited[v] = false; } else { //找到可行的下一个顶点 myStack.push(w); //放入栈中 if (myStack.size() == numVertices) { //走过所有的顶点 if (myGraph.getWeight(start, w) == std::numeric_limits::max()) { //判断最后一个顶点有没有回到起点的边 myStack.pop(); visited[w] = false; } else { //成功找到回路 return 1; } } else { w = -1; } } } return 0; } template int ch(int start, Graph &myGraph) { //climbingHill 爬山法判断图中是否存在哈密顿回路 stack myStack; myStack.push(start); int numVertices = myGraph.NumberOfVertices(); bool *visited = new bool[numVertices]; memset(visited, false, numVertices); int v; int w = -1; while (!myStack.empty()) { //栈不为空 v = myStack.top(); visited[v] = true; if (w == -1) { w = myGraph.getFirstNeighbor(v); } else { w = myGraph.getNextNeighbor(v, w); } for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {} int greedy = w;//贪心选择子顶点 for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) { if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) { greedy = w; } } w = greedy; if (w == -1) { //未找到可行的下一个顶点 myStack.pop(); //回溯 w = v; visited[v] = false; } else { //找到可行的下一个顶点 myStack.push(w); //放入栈中 if (myStack.size() == numVertices) { //走过所有的顶点 if (myGraph.getWeight(start, w) == std::numeric_limits::max()) { //判断最后一个顶点有没有回到起点的边 myStack.pop(); visited[w] = false; } else { //成功找到回路 return 1; } } else { w = -1; } } } return 0; } template int climbingHill(int start, Graph &myGraph, ostream & fout) { //算法解决图的最小哈密顿回路问题 v为回路的起点和终点 stack myStack; myStack.push(start); int numVertices = myGraph.NumberOfVertices(); bool *visited = new bool[numVertices]; memset(visited, false, numVertices); int v; int w = -1; while (!myStack.empty()) { //栈不为空 v = myStack.top(); visited[v] = true; if (w == -1) { w = myGraph.getFirstNeighbor(v); } else { w = myGraph.getNextNeighbor(v, w); } for (; w != -1 && visited[w] == true; w = myGraph.getNextNeighbor(v, w)) {} int greedy = w;//贪心选择子顶点 for (; w != -1 && visited[w] == false; w = myGraph.getNextNeighbor(v, w)) { if(myGraph.getWeight(v, w) < myGraph.getWeight(v, greedy)) { greedy = w; } } w = greedy; if (w == -1) { //未找到可行的下一个顶点 myStack.pop(); //回溯 w = v; visited[v] = false; } else { //找到可行的下一个顶点 myStack.push(w); //放入栈中 if (myStack.size() == numVertices) { //走过所有的顶点 if (myGraph.getWeight(start, w) == std::numeric_limits::max()) { //判断最后一个顶点有没有回到起点的边 myStack.pop(); visited[w] = false; } else { //成功找到回路 stack temp; while (!myStack.empty()) { int n = myStack.top(); temp.push(n); myStack.pop(); } fout << "哈密顿回路 : "; E distance = 0; int n = temp.top(); myStack.push(n); temp.pop(); int last = n; fout << n << "--"; while (!temp.empty()) { n = temp.top(); myStack.push(n); temp.pop(); distance += myGraph.getWeight(last, n); last = n; fout << n << "--"; } fout << start << endl; distance += myGraph.getWeight(last, start); fout << "总长度为:" << distance << endl; return distance; } } else { w = -1; } } } return std::numeric_limits::max(); } template int bfs(int start, Graph & myGraph) { //broadFirst 判断图中是否存在哈密顿回路 stack > myStack; //队列 int s = myGraph.getFirstNeighbor(start); for (s = myGraph.getNextNeighbor(start, s); s != -1; s = myGraph.getNextNeighbor(start, s)) { NODE n(2); n.vertices[0] = start; n.vertices[1] = s; n.length = myGraph.getWeight(start, s); myStack.push(n); } while (!myStack.empty()) { //队列不为空 NODE n = myStack.top(); myStack.pop(); int v = n.vertices[n.dep - 1]; if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路 int w; for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) { if (n.find(w) == false) break; } if (w != -1) { if (myGraph.getWeight(w, start)::max()) { return 1; } } } for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) { if (n.find(w) == false) { NODE ne(n.dep + 1); ne.length = n.length + myGraph.getWeight(v, w); n.cpy(ne.vertices); ne.vertices[ne.dep - 1] = w; myStack.push(ne); } } } return 0; } //分支限界法求解最短哈密顿回路问题 template int branchBound(int start, Graph & myGraph, ostream & fout) { stack > myStack; //队列 E minDistance = climbingHill(start,myGraph,fout);//爬山法获取首界限 int s = start; for (s = myGraph.getFirstNeighbor(start); s != -1; s = myGraph.getNextNeighbor(start, s)) {//首次分支 NODE n(2); n.vertices[0] = start; n.vertices[1] = s; n.length = myGraph.getWeight(start, s); myStack.push(n); } while (!myStack.empty()) { //队列不为空 NODE n = myStack.top(); myStack.pop(); int v = n.vertices[n.dep - 1]; if (n.dep + 1 == myGraph.NumberOfVertices()) { //到了最后一层 判断是不是哈密顿回路 int w; for (w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) { if (n.find(w) == false)//确定最后一个节点 break; } if (w != -1) { if (myGraph.getWeight(w, start)::max()) { //如果找到且存在路径 E tempDistance = n.length + myGraph.getWeight(v, w) + myGraph.getWeight(w, start); if (minDistance>tempDistance) { // 形成回路 fout << "哈密顿回路为:"; // cout << "哈密顿回路为:"; for (int i = 0; i ne(n.dep + 1); ne.length = n.length + myGraph.getWeight(v, w); if (ne.length myGraph(i); Graph myGraphN(i); myGraph.RandInit();//随机初始化完全无向图 myGraphN.RandInitN();//随机初始化图 int a = clock(); cout<<"deepFirst:"< myGraphN(4); // ifstream fin("input.txt"); // myGraphN.Init(fin); // cout<<"deepFirst:"< ';