精华内容
下载资源
问答
  • 首先,说明本次问题:本次问题是,构建一个有向哈密顿图,给出任意两个点,找到他们之间存在的哈密顿通路。哈密顿通路需要保证所有点被遍历到,同时不能有重复点。(由于比较习惯java,所以偷懒直接写java

    之前以自己一渣渣之身参加了一个比赛,果然连门槛都没摸到,虽然略有沮丧不过还是得到了很多思考哒,这里记一下。

    因为之前没有接触过算法,感觉这个可能也只是能够解决问题,效率极低,先记下来以后有兴致慢慢优化好了。

    首先,说明本次问题:

    本次问题是,构建一个有向哈密顿图,给出任意两个点,找到他们之间存在的哈密顿通路。哈密顿通路需要保证所有点被遍历到,同时不能有重复点。

    (由于比较习惯java,所以偷懒直接写java版的吧。还得好好学习c的说!)

    这里我考虑用递归的方式,求出存在的哈密顿通路。

    step1:构建图的方式

    HashMap<Integer,ArrayList<Integer>> myMap 
        = new HashMap<Integer, ArrayList<Integer>>();
        //其中,key值为点的ID值,value为与该点相连接的点的ID值

    step2:找到哈密顿通路

    int size = myMap.size();    //点的个数
    void findHamiltonianPath(int id,Integer[] edge){
            for(int pointID: myMap.get(id)){
                if(edge.length!=size-1 && pointID ==destinationID) continue;
                //提前到达目标点
                if(ifHavePassed(edge,pointID)) continue;
                //曾经经过此点,ifHavePassed函数用于检查路径中是否已含有该点
                Integer[] newEdge = new Integer[edge.length+1];
                System.arraycopy(edge,0,newEdge,0,edge.length);
                newEdge[edge.length] = pointID;
                //得到新的路径数组  
                if(pointID == destinationID){
                    System.out.println(Arrays.asList(newEdge));
                    continue;
                }
                findHamiltonianPath(pointID, newEdge);
            }
        }

    感觉原理还是蛮简单的,但是应该还能优化很多。
    希望明年能摸到比赛的门槛~

    展开全文
  • 哈密顿求解 C++实现 回溯法

    千次阅读 2015-05-21 14:38:19
    /* 函数功能:求解哈密顿环(无向图,有向图请自改)问题,输出全部不相同的环,即经过图中每个结点并且只经过一次的可行解。 * 作者 :王宇虹 * 时间 :2015年5月21日 13:23:00.000 * 编译环境:Dev-C++ 5.8.3 *...
    /*  函数功能:求解哈密顿环(无向图,有向图请自改)问题,输出全部不相同的环,即经过图中每个结点并且只经过一次的可行解。 
     *  作者    :王宇虹 
     *  时间    :2015年5月21日  13:23:00.000
     *  编译环境:Dev-C++ 5.8.3
     */
    #include<iostream>
    #include<cstring>
    using namespace std;
    int n,m,g,i;  //n表示无向图中结点个数,g表示结点关系个数 
    int a[10000][10000];  //只开到结点个数为10000的范围
    void NextValue(int k,int* x); 
    void Hamiltonian(int k,int *x);
    void Hamiltonian(int *x);
    
    int main()      //主函数
    {
    	memset(a,0,sizeof(a)); 
    	cout << "请输入无向图中结点的个数: ";
    	cin >> n;
    	cout << "请输入边的条数: ";
    	cin >> g;
    	int *x = new int[10000];
        int u, v;
        for(i = 0; i < n; i++) x[i] = 0;
        for(i = 0; i < g; i++)
    	{
    		cout << "请输入边:";
    		cin >> u >> v;
    	    a[u][v] = a[v][u] = 1;
    	}
    	cout << "可行解: " << endl; 
    	Hamiltonian(x);
    
        return 0;
    }
    
    void NextValue(int k,int* x)
    {
    	int j;
        do{
    		x[k] = (x[k]+1) % n;    		 	//下一个结点编号 
    		if(!x[k]) return;         		 
    		    if(a[x[k-1]][x[k]]){              //(x[k-1],x[k])是否是图中一条边 
    		    for(j = 0; j < k; j++)      //检查与前k个节点是否相同
    		        if(x[j] == x[k])	break;  //结点x[k]与前k个结点有重复 
    		    if(j == k)                      //x[k]是当前可取的结点编号 
    		        if((k < n-1)||(k == n-1) && a[x[n-1]][x[0]])
    			      return;
    			}
    	}while(1);
    }
    void Hamiltonian(int k,int *x)
    {
    	do{
    		NextValue(k, x);             //产生x[k]的下一个值 
    		if(!x[k])  return;               //x[k]=0表示x[k]已经没有可取值 
    		if(k == n - 1) {                //输出一个哈密顿环 
    			for(int i = 0; i < n; i++)  cout<<x[i]<<' ';
    			cout<< "0\n";
    		}
    		else
    			Hamiltonian(k+1,x);         //深度优先进入下一层 
    	}while(1);
    }
    void Hamiltonian(int *x)
    {
    	Hamiltonian(1, x);
    }
    展开全文
  • 代码里面有详细解释,包括独立函数,以及对函数的使用,有两个例子,可以鲜明得看出函数的调用过程。方便同学们日后使用。
  • 哈密顿回路与旅行商问题求解

    千次阅读 2019-02-28 15:17:43
    哈密顿图:图G的一个回路,若它...哈密顿回路之中的图并不要求是完全图,而当这个图的完全图也就是每个顶点之间都存在路径,并且是加权图的时候,哈密顿回路的问题就演变成了旅行商问题,因此上述两个问题求解方法...

    哈密顿图:图G的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.

    哈密顿回路之中的图并不要求是完全图,而当这个图的完全图也就是每个顶点之间都存在路径,并且是加权图的时候,哈密顿回路的问题就演变成了旅行商问题,因此上述两个问题的求解方法十分相似。

    首先来求哈密顿回路问题

    1.我们很容易想到用蛮力法,即对于给定的无向图(V,E) 依次考察图中所有顶点的全排列,而当满足相邻顶点之间存在边并且最后一个顶点与第一个顶点之间也存在边时就符合条件。

    2.采用dfs,并且适当减枝。 下面我们采用这种方法求解

    input:

    5
    0 1 1 1 0
    1 0 1 0 1
    0 1 0 1 1
    1 0 1 0 1
    0 1 1 1 0

     

    //哈密顿回路问题
    #include<stdio.h>
    int x[100];
    int visit[100];
    int arc[6	][6];
    int n;
    void dfs(int step)
    {
    	int i,j;
    	if(step==n&&arc[x[step-1]][0]==1) //最后一步到达的顶点与起点之间存在路径 
    	{
    		printf("路径:");
    		for(i=0;i<n;i++)
    			printf("%d ",x[i]+1);
    		printf("\n");
    			return ;
    			
    	}
    	else
    	{
    		for(j=0;j<n;j++)
    		{
    			if(visit[j]==0&&arc[x[step-1]][j]==1) //j未访问并且当前顶点与j顶点之间存在路径 
    			{
    				visit[j]=1;
    				x[step]=j;	//下一个访问的顶点为j 
    				dfs(step+1);
    				visit[j]=0;
    				x[step]=0;			
    			}
    			
    		}
    	}
    	
    } 
    int main(void)
    {
    	int i,j;
    	scanf("%d",&n);
     	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			scanf("%d",&arc[i][j]);
    	visit[0]=1;  //起点置为已经访问
    	x[0]=0;
    	dfs(1);
    	return 0;
    	
    }

     

    旅行商问题的求解 :有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次,最后回到出发的城市,问如何事先确定一条最短的线路已保证其旅行的费用最少?

    旅行商问题与哈密顿回路问题十分相似,都是经过每一个顶点一次最后回到出发的城市,不同的是旅行商问题对应的是完全图,即每个顶点之间都存在路径,并且路径长度已知。

     

    input:

    4
    0 2 5 7
    2 0 8 3
    5 8 0 1
    7 3 1 0
    output:

    11

    //旅行商问题,对应完全图
    //哈密顿回路问题 对应非完全图 
    #include<stdio.h>
    int x[100];
    int visit[100];
    int arc[6][6];
    int n,count,bestCount=9999999;
    void dfs(int step,int count)
    {
    	int i,j;	 
    	if(bestCount<count) //减枝,当然所经过的路径长度大于最小长度 
    		return;
    	if(step==n) //已经走过n个顶点 
    	{
    	 
    		count+=arc[x[step-1]][0];
    		bestCount=count;	 
    		return ;
    			
    	}
    	else
    	{
    		for(j=0;j<n;j++)
    		{
    			if(visit[j]==0) //j未访问
    			{
    				visit[j]=1;//置为已经访问 
    				x[step]=j;	//访问该顶点 
    				dfs(step+1,count+arc[x[step-1]][j]); 
    				visit[j]=0;
    				x[step]=0;			
    			}
    			
    		}
    	}
    	
    } 
    int main(void)
    {
    	int i,j;
    	scanf("%d",&n);
     	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			scanf("%d",&arc[i][j]);
    	visit[0]=1;
    	x[0]=0;
    	dfs(1,0);
    	printf("%d ",bestCount);	
    	return 0;
    	
    }

     

    展开全文
  • 哈密顿问题

    2015-01-09 10:43:10
    哈工大算法实验三,搜索算法(哈密顿问题求解哈密顿环 1.实现基于树的深度优先搜索算法,求解哈密顿问题 2.实现哈密顿环的爬山法 3.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析...
  • 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。 该程序用C语言编写(在VC++环境下运行即可),使用贪心算法求得最短哈密顿回路的近似解,简单易懂。
  • 通过哈密环问题,实现深度优先,广度优先,爬山法,分支限界法等树搜索策略。

    问题描述:

    (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<iomanip>
    #include<limits>
    #include<time.h>
    #include<stdlib.h>
    #include<iostream>
    #include<fstream>
    using namespace std;
    
    template<class E>  //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<class E>
    Graph<E>::Graph(int sz) { //创建SZ大小的基于邻接矩阵的图
    	maxWeight = std::numeric_limits<E>::max();
    	maxVertices = sz;
    	matrix = new E *[sz];
    	for (int i = 0; i<sz; i++) {
    		matrix[i] = new E[sz];
    		for (int j = 0; j<sz; j++) {
    			matrix[i][j] = maxWeight;
    		}
    	}
    }
    template<class E>
    Graph<E>::~Graph() {
    	for (int i = 0; i<maxVertices; i++) {
    		delete matrix[i];
    	}
    }
    template<class E>
    E Graph<E>::getWeight(int v1, int v2) { //取边(v1,v2)上的权值
    	if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
    		return matrix[v1][v2];
    	}
    	return 0;
    }
    template<class E>
    int Graph<E>::getFirstNeighbor(int v) { //取顶点v的第一个邻接顶点
    	if (!(v >= 0 && v<maxVertices))   //v不合法
    		return -1;
    	for (int col = 0; col<maxVertices; col++) {
    		if (matrix[v][col] != maxWeight) {
    			return col;          //找到
    		}
    	}
    	return -1;                   //未找到
    }
    template<class E>
    int Graph<E>::getNextNeighbor(int v, int w) { //取顶点v的邻接顶点W的下一个邻接顶点
    	if (!(v >= 0 && v<maxVertices) || !(w >= 0 && w<maxVertices))  //v或w不合法
    		return -1;
    	for (int col = w + 1; col<maxVertices; col++) {
    		if (matrix[v][col] != maxWeight) {
    			return col;         //找到
    		}
    	}
    	return -1;//未找到
    }
    template<class E>
    int Graph<E>::Init(istream &fin) { //根据输入文件,获得图的邻接矩阵
    	int v1, v2;
    	E edge;
    	while (fin >> v1 >> v2 >> edge) {
    		if (v1 >= 0 && v1<maxVertices&&v2 >= 0 && v2<maxVertices) {
    			matrix[v1][v2] = edge;
    			matrix[v2][v1] = edge;
    		}
    		if (edge == maxWeight) {  //当输入边值为无穷大时停止输入
    			break;
    		}
    	}
    	return 1;
    }
    
    template<class E>
    int Graph<E>::RandInitN() { //随机初始化图(无向图,非完全)
    	for (int i = 0; i<maxVertices; i++) {
    		for (int j = 0; j<maxVertices; j++) {
    			matrix[i][j] = maxWeight;
    		}
    	}
    	srand((int)time(0));
    //	int rnd = maxVertices*(maxVertices - 1) / 3;
    	int count = rand() / RAND_MAX*rnd / 4 + 3 * rnd / 4;
    //	int count = rnd / 2;
    //	int v1, v2;
    //	while (count) {
    //		v1 = rand() % maxVertices;
    //		v2 = rand() % maxVertices;
    //		if (v1 != v2&&matrix[v1][v2] == maxWeight) {
    //			matrix[v2][v1] = matrix[v1][v2] = rand();
    //			count--;
    //		}
    //	}
    	for(int v1=0;v1<maxVertices;v1++)
    		for(int v2=0;v2<maxVertices;v2++){
    			if (v1 != v2&&matrix[v1][v2] == maxWeight){
    				matrix[v2][v1] = matrix[v1][v2] = rand()%2;
    			}
    		}
    	return 1;
    }
    
    template<class E>
    int Graph<E>::RandInit() { //随机初始化图(无向完全图)
    	for (int i = 0; i<maxVertices; i++) {
    		for (int j = 0; j<maxVertices; j++) {
    			matrix[i][j] = maxWeight;
    		}
    	}
    	srand((int)time(0));
    	int count = maxVertices*(maxVertices - 1) / 2;
    	int v1, v2;
    	while (count) {
    		v1 = rand() % maxVertices;
    		v2 = rand() % maxVertices;
    		if (v1 != v2&&matrix[v1][v2] == maxWeight) {
    			if(v1-v2==1||v2-v1==1) matrix[v2][v1] = matrix[v1][v2] = rand()%2000;
    			else matrix[v2][v1] = matrix[v1][v2] = rand();
    			count--;
    		}
    	}
    	return 1;
    }
    
    template<class E>
    int Graph<E>::output(ostream &out) { //输出图的矩阵
    	for (int i = 0; i<maxVertices; i++) {
    		for (int j = 0; j<maxVertices; j++) {
    			out << setw(15) << matrix[i][j] << ",";
    		}
    		out << endl;
    	}
    	return 1;
    }
    template<class E>
    int Graph<E>::output() { //输出图的矩阵
    	for (int i = 0; i<maxVertices; i++) {
    		cout<<"\t";
    		for (int j = 0; j<maxVertices; j++) {
    			cout << setw(15) << matrix[i][j] << ",";
    		}
    		cout << endl;
    	}
    	return 1;
    }
    源码:

    Graph.cpp

    /*
    *Tree Search Strategy 15S103182 Ethan
    *2015.12.1
    */
    #include"Graph.h"
    #include<iostream>
    #include<fstream>
    #include<sstream>
    #include<stack>
    #include<queue>
    #include<limits>
    #include<memory.h>
    #include<string.h>
    using namespace std;
    
    template<class E>
    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<dep; i++) {
    			des[i] = vertices[i];
    		}
    	}
    	bool find(int v) {
    		for (int i = 0; i<dep; i++) {
    			if (vertices[i] == v)
    				return true;
    		}
    		return false;
    	}
    };
    
    
    template<class E>
    int dfs(int start, Graph<E> &myGraph) { //deepFirst 判断图中是否存在哈密顿回路
    	stack<int> 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<E>::max()) { //判断最后一个顶点有没有回到起点的边
    					myStack.pop();
    					visited[w] = false;
    				} else { //成功找到回路
    					return 1;
    				}
    			} else {
    				w = -1;
    			}
    		}
    	}
    	return 0;
    }
    
    template<class E>
    int ch(int start, Graph<E> &myGraph) { //climbingHill 爬山法判断图中是否存在哈密顿回路
    	stack<int> 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<E>::max()) { //判断最后一个顶点有没有回到起点的边
    					myStack.pop();
    					visited[w] = false;
    				} else { //成功找到回路
    					return 1;
    				}
    			} else {
    				w = -1;
    			}
    		}
    	}
    	return 0;
    }
    
    template<class E>
    int climbingHill(int start, Graph<E> &myGraph, ostream & fout) { //算法解决图的最小哈密顿回路问题  v为回路的起点和终点
    	stack<int> 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<E>::max()) { //判断最后一个顶点有没有回到起点的边
    					myStack.pop();
    					visited[w] = false;
    				} else { //成功找到回路
    					stack<int> 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<E>::max();
    }
    template<class E>
    int bfs(int start, Graph<E> & myGraph) { //broadFirst 判断图中是否存在哈密顿回路
    	stack<NODE<E> > myStack;  //队列
    	int s = myGraph.getFirstNeighbor(start);
    	for (s = myGraph.getNextNeighbor(start, s); s != -1; s = myGraph.getNextNeighbor(start, s)) {
    		NODE<E> n(2);
    		n.vertices[0] = start;
    		n.vertices[1] = s;
    		n.length = myGraph.getWeight(start, s);
    		myStack.push(n);
    	}
    	while (!myStack.empty()) { //队列不为空
    		NODE<E> 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)<std::numeric_limits<E>::max()) {
    					return 1;
    				}
    			}
    		}
    		for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
    			if (n.find(w) == false) {
    				NODE<E> 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<class E>
    int branchBound(int start, Graph<E> & myGraph, ostream & fout) {
    	stack<NODE<E> > myStack;  //队列
    	E minDistance = climbingHill(start,myGraph,fout);//爬山法获取首界限
    	int s = start;
    	for (s = myGraph.getFirstNeighbor(start); s != -1; s = myGraph.getNextNeighbor(start, s)) {//首次分支
    		NODE<E> n(2);
    		n.vertices[0] = start;
    		n.vertices[1] = s;
    		n.length = myGraph.getWeight(start, s);
    		myStack.push(n);
    	}
    	while (!myStack.empty()) { //队列不为空
    		NODE<E> 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)<std::numeric_limits<E>::max()) { //如果找到且存在路径
    					E tempDistance = n.length + myGraph.getWeight(v, w) + myGraph.getWeight(w, start);
    
    					if (minDistance>tempDistance) {
    //						形成回路
    						fout << "哈密顿回路为:";
    //						cout << "哈密顿回路为:";
    						for (int i = 0; i<n.dep; i++) {
    							fout << n.vertices[i] << "   ";
    //							cout << n.vertices[i] << "   ";
    						}
    						fout << w << "   " << start << endl;
    //						cout << w << "   " << start << endl;
    						fout << "总长度为:  " << tempDistance << endl;
    //						cout << "总长度为:  " << tempDistance << endl;
    						minDistance = tempDistance;
    					}
    				}
    			}
    		}
    		for (int w = myGraph.getFirstNeighbor(v); w != -1; w = myGraph.getNextNeighbor(v, w)) {
    			if (n.find(w) == false) {//存在未遍历顶点
    				NODE<E> ne(n.dep + 1);
    				ne.length = n.length + myGraph.getWeight(v, w);
    				if (ne.length<minDistance) {//剪枝
    					n.cpy(ne.vertices);
    					ne.vertices[ne.dep - 1] = w;
    					myStack.push(ne);
    				}
    			}
    		}
    	}
    	return minDistance;
    }
    
    int main(int argc, char** argv) {
    	for(int i=8; i<=20; i+=2) {
    		cout<<endl<<"节点数:"<<i<<endl;
    		Graph<int> myGraph(i);
    		Graph<int> myGraphN(i);
    		myGraph.RandInit();//随机初始化完全无向图
    		myGraphN.RandInitN();//随机初始化图
    		int a = clock();
    		cout<<"deepFirst:"<<dfs(0,myGraphN)<<"\t\t";
    		int b = clock();
    		int st = b - a;
    		cout<<"dfs time:"<<st<<endl;
    		int a1 = clock();
    		cout<<"broadFirst:"<<bfs(0,myGraphN)<<"\t\t";
    		int b1 = clock();
    		int st1 = b1 - a1;
    		cout<<"bfs time:"<<st1<<endl;
    		int a2 = clock();
    		cout<<"climbingHill:"<<ch(0,myGraphN)<<"\t\t";
    		int b2 = clock();
    		int st2 = b2 - a2;
    		cout<<"ch time:"<<st2<<endl;
    		char mat[20];
    		itoa(i,mat,10);
    		strcat(mat,"matrix.txt");
    		ofstream fout2(mat);
    		myGraph.output(fout2);
    		char matN[20];
    		itoa(i,matN,10);
    		strcat(matN,"matrixN.txt");
    		ofstream fout3(matN);
    		myGraphN.output(fout3);
    //		cout<<"Matrix["<<i<<"]["<<i<<"]:"<<endl;
    //		myGraph.output();
    		char bbn[20];
    		itoa(i,bbn,10);
    		strcat(bbn,"branchBound.txt");
    		ofstream fout1(bbn);
    		
    		int a3 = clock();
    		cout<<"branchBound:"<<branchBound(0,myGraph,fout1)<<"\t";
    		int b3 = clock();
    		int st3 = b3 - a3;
    		cout<<"branchBound time:"<<st3<<endl;
    	}
    	//手动输入图
    //	Graph<int> myGraphN(4);
    //	ifstream fin("input.txt");
    //	myGraphN.Init(fin);
    //	cout<<"deepFirst:"<<dfs(0,myGraphN)<<endl;
    //	cout<<"broadFirst:"<<bfs(0,myGraphN)<<endl;
    //	cout<<"climbingHill:"<<ch(0,myGraphN)<<endl;
    //	ofstream fout2("matrix.txt");
    //	myGraphN.output(fout2);
    //	cout<<"Matrix[4][4]:"<<endl;
    //	myGraphN.output();
    //	ofstream fout1("branchBound.txt");
    //	cout<<"branchBound:"<<branchBound(0,myGraphN,fout1)<<endl;
    	return 0;
    }

    BranchBound的性能曲线如下图:

    由性能曲线图可以看出,当输入完全图的点数增加时,算法的运行时间也会成倍增加,造成这种效果的原因主要是为了求解最优解,算法在最坏情况下复杂度是O(n!),虽然通过剪枝策略能够大大提高效率,但算法时间复杂度依旧很高。






    展开全文
  • 哈密顿问题

    2019-02-20 20:49:43
    哈密顿问题
  • 【算法笔记】哈密顿问题

    千次阅读 2020-10-09 17:06:18
    哈密顿问题 基本概念 哈密尔顿通路:经过图中每个结点且仅经过一次的通路。 哈密尔顿回路:经过图中每个结点且仅经过一次的回路。 哈密尔顿图:存在哈密尔顿回路的图。 竞赛图:每对顶点之间都有一条边相连的有向图...
  •  这是我写的第一个博客,仅作为参考,大牛们见了不要见笑哈。  本题首先就是要建立一个城市连接的地图,然后从起始位置开始深度优先遍历每一个城市找个满足条件的路径,给以打印。用以存储地图的开辟一个二维...
  • 哈密顿图 #include using namespace std; bool mp[107][107]; int n, m; int flag = 0; int ans[107]; void dfs(int x, int cnt) { if (flag) return ; if (cnt == m + 1) { flag = 1; for (int i = 1; i ; ++i) { ...
  • POJ2438-求解哈密顿回路

    千次阅读 2012-08-05 15:24:56
    /* 学习参考:http://imlazy.ycool.com/post.2072698.html http://blog.csdn.net/weiguang_123/article/details/7830047 */ #include #include #include using namespace std; const int NN=420;...b
  • 哈密顿控制

    2017-10-27 14:14:13
    永磁同步电机的哈密顿控制,采用能量成形和无源性的控制方法,将速度控制问题转化为带阻尼系数的一阶微分方程求解问题,解决电机的能量优化问题。
  • =2)阶竞赛图构造哈密顿通路 N阶竞赛图:含有N个顶点的有向图,且每对顶点之间都有一条边。对于N阶竞赛图一定存在哈密顿通路。 证明及原理 然后,又有题目中给出的就是一个竞赛图,所以我们可以直接推理哈密顿通路...
  • NP难问题求解综述

    万次阅读 2020-09-29 05:34:14
    为了解释NP难问题及P类问题,先介绍确定性算法和非确定性算法这两个概念,设A是求解问题Π的一个算法,如果在算法的整个执行过程中,每一步只有一个确定的选择,则称算法A是确定性(Determinism)算法。设A是求解...
  • TSP问题求解方法

    千次阅读 2017-09-02 00:52:28
    原文一名旅行商准备前往若干个城市推销他的产品,他想要从驻地出发,经过每个城市...改良圈算法改良圈算法的思想是首先求出一个哈密顿圈C,然后通过适当地修改哈密顿圈得到具有较小权值的另一个哈密顿圈。设初始圈C=v1
  • 蛮力法只是用遍历的技术,尝试所有可能的解,直到找到一条回路或者返回无解。所以先输入无向图,再得到全排列,最后遍历全排列即可。 代码如下: #include<iostream> #include<...void ml(int g[1000][100]...
  • 【状压DP】哈密顿回路问题 lzq同学在我准备午睡的时候发了一道蓝桥杯的题目给我,是哈密顿回路的,由于本人太弱了没参赛只能摸鱼赛后解题。 lzq的 #include<bits/sdc++.h> using namespace std; int gcd(int a...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,070
精华内容 828
关键字:

哈密顿问题求解