C语言哈密尔顿回路
/********************此程序是用来进行无向图的哈密尔顿回路寻找所用*****/
/**********************欢迎使用*********************************************/
#include
#include
#define Max 100
#define INF 6666
/********************邻接矩阵的结构体的定义******************/
typedefstruct node
{
int cost[Max][Max]; //用来标记俩个顶点之间的权值
int edges[Max][Max]; //用来标记俩个顶点之间是否有边
}list,*MG;
int n; // 顶点数全局变量
int a[2000][2000]; //用来存储每次寻找到的哈密尔顿回路
/***********************无向图初始化函数*******************/
MG chushihua()
{
ints,i,j,e;
int weight;
MG p;
p=(MG)malloc(sizeof(list));
for(i=0;i for(j=0;j { p->cost[i][j]=INF; //初始点的所有路径中各点到其他点的距离为无穷大 p->edges[i][j]=0; //初始化每2个顶点之间没有边} printf("\n请输入无向图的顶点数n，和其边数e,格式：n e \n\n"); scanf("%d %d",&n,&e); printf("\n请输入边与边之间的关系，格式：顶点序号-权值-顶点序号\n"); //初始化矩阵for(i=0;i { scanf("%d %d %d",&s,&weight,&j); p->cost[s][j]=weight; p->cost[j][s]=weight; p->edges[s][j]=1; //当俩个顶点之间距离小于INF，则标记有边 p->edges[j][s]=1; } return p; } /***********************哈密尔顿回路寻找函数*******************/ int search(MG p) inti,k=0,l=0; //l用来用来计回路总数 int s[n],b[n]; //s[n]用来标记是否遍历的顶点，b[n]标记顶点标号 for(i=0;i { s[i]=0; b[i]=-1; //对s[n],b[n]进行初始化 } s[0]=1; //从0号开始遍历寻找 b[k]=0; b[k+1]=b[k]+1; //顶点号累加 k++; do //主循环 { while(b[k] { if(k==0) { s[b[k]]=1; break; } else if(s[b[k]]==0&&p->edges[b[k]][b[k-1]]==1) //当顶点未被遍历且与刚遍历的顶点之间有边，则退出当下循环 { s[b[k]]=1; break; } else b[k]++; //条件不满足，则顶点号累加继续寻找 } if(b[k]>=n) //当顶点号大于N，则对回路数统计，输出 { if(k==0) { printf("\n 图中所含回路个数为:"); printf("%d\n",l); return l; } else //如果不满足前一个条件，则退回前一个顶点进行重新遍历 { s[b[k-1]]=0; b[k-1]=b[k-1]+1; } } else if(k==n-1&&p->edges[b[k]][b[0]]!=1) //当最后一个顶点与起始顶点没有路径，则退回前一个顶点重新寻找 { s[b[k-1]]=0; b[k-1]=b[k-1]+1; k--; } else if(k==n-1&&p->edges[b[k]][b[0]]==1) //当寻找成功时，存储顶点，然后退回一步进行再遍历 { for(i=0;i { a[l][i]=b[i]; } a[l][i+1]=b[k]; l++; s[b[k]]=0; s[b[k-1]]=0; b[k-1]=b[k-1]+1; k--; } else //当顶点号不大于N，则继续按照之间思路进行寻找 { i=0; while(i i++; b[k+1]=i; k++; } }while(1); } /**************************对遍寻的结果进行筛选，判断是否有哈密尔顿回路，如有求取最短回路************/ voidshaixuan(intl,MG p) { int min[Max]; int sum=0; inti,j,r; int r1,r2; if(l==0) printf("\n 此无向图不存在哈密尔顿回路\n"); } else { for(j=0;j { sum=0; for(i=0;i { r1=a[j][i]; if(i==n-2) { r2=a[j][i+2]; } else { r2=a[j][i+1]; } printf("%d %d\n",r1,r2); sum=sum+p->cost[r1][r2]; } r2=a[j][n]; r1=a[j][0]; sum=sum+p->cost[r1][r2]; min[j]=sum; //存储路径长} sum=min[0]; r=0; for(j=1;j { sum=min[j]; r=j; } printf("\n 无向图所有哈密尔顿回路如下：\n\n"); for(i=0;i { printf(" 哈密尔顿回路%d 路径长是%d\n\n",(i+1),min[i]); printf(" 其经由的点为："); for(j=0;j printf("%d->",a[i][j]); printf("%d\n",a[i][j+1]); printf("\n"); } printf("\n 此无向图的最短哈密尔顿回路路径长是%d\n",sum); printf("\n 其经由的点为："); for(j=0;j printf("%d->",a[r][j]); printf("%d\n",a[r][j+1]); } } /*****************主函数*******************/ int main() { MG p; int l; printf("※※※※※※※此程序用于低于100个顶点以下的无向图寻找哈密尔顿回路※※※※※※※\n"); printf("\n \(^o^)/ 欢迎使用\(^o^)/\n"); p=chushihua(); l=search(p); shaixuan(l,p); printf("\n\n\n 预祝老师师兄师姐：\n"); printf(" 新春快乐\(^o^)/ OYER\n\n"); printf(" 来年财源滚滚啊！\(^o^)/ OYER\n"); system("PAUSE"); return 0; } /*测试数据 顶点数、边数 11 17 邻边关系 0 18 1 0 3 2 0 7 3 0 2 5 1 7 2 1 5 5 2 6 3 2 4 4 3 8 5 3 2 6 3 3 9 3 6 10 4 3 6 5 6 8 6 2 7 7 12 10 8 9 9 */ 哈密尔顿回路算法比较 一、贪心法 贪心法通常用来解决具有最大值或最小值的优化问题。通常从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元素，以便尽快地构成问题的可行解。 贪心法通过一系列选择得到问题的解。其所做出的每一个选择都是当前状态下的局部最好选择，即贪心选择。贪心法并不总能得到问题的最优解。 利用贪心法解哈密尔顿回路的C++算法如下： #include "stdio.h" int G[8][8]={{0,2,8,1,9}, {2,0,5,10,9}, {8,5,0,5,3}, {1,10,5,0,5}, {9,9,3,5,0}}; struct Edge //记录边的信息 { int x; int y; int value; //边的权值 }; typedef struct Edge Weight; int T[5]={0}; //用于标识节点是否被遍历过 int P[6]={0}; //存放路径 int sum_value=0; //计算总路径长度 Weight min_value(int r) //找出当前节点具有最小权值的相邻边 { int i,j=0,min; Weight W[5]; //用于存放相邻边的信息 for(i=0;i<5;i++) { if((T[i]==0)&&(i!=r)) //当节点未被遍历且不是自己到自己 { W[j].x=r; W[j].y=i; W[j].value=G[r][i]; //记录相邻边的信息 j++; } } min=W[0].value; for(i=0;i 哈密尔顿图的充分必要条件 摘要 图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注. 关键词:哈密尔顿图;必要条件;充分条件; 1 引言 (3) 2 哈密尔顿图的背景 (3) 3 哈密尔顿图的概念 (4) 4 哈密顿图的定义 (5) 4．1定义 (5) 4．2定义 (5) 4．3哈密顿路是遍历图的所有点。 (6) 4 哈密尔顿图的充分条件和必要条件的讨论 (7) 5 结论 (8) 参考文献 (8) 指导老师 (9) 1 引言 图论是一门既古老又年轻的学科,随着科学技术的蓬勃发展,它的应用已经渗透到自然科学以及社会科学的各个领域之中,利用它我们可以解决很多实际生活中的问题,给你一个图,你怎么知道它是否是哈密尔顿图呢?当然如果图的顶点不多,你可以用最古老的”尝试和错误”的方法试试找哈密尔顿回路就可以解决和判断.但是,数学家们并不满足这样的碰得焦头烂额后才找到的真理方法.是否存在一组必要和充分的条件,使得我们能够简单轻易地判断一个图是否是哈密尔顿图?有许多智者通过各种方式去尝试过了,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件.虽然有些充分非必要或必要非充分条件,但大部分还是采用尝试的办法,不过这些条件也是非常有用的. 2 哈密尔顿图的背景 美国图论数学家奥在1960年给出了一个图是哈密尔顿图的充分条件：对于顶点个数大于2的图，如果图中任意两点度的和大于或等于顶点总数，那这个图一定是哈密尔顿图。闭合的哈密顿路径称作哈密顿圈，含有图中所有顶的路径称作哈密顿路径. 1857年，哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示(如图1)。 哈密顿回路算法 概念：哈密顿图：图G的一个回路，若它通过图的每一个节点一次，且仅一次，就是哈密顿回路。存在哈密顿回路的图就是哈密顿图。哈密顿图就是从一点出发，经过所有的必须且只能一次，最终回到起点的路径。图中有的边可以不经过，但是不会有边被经过两次。 与欧拉图的区别：欧拉图讨论的实际上是图上关于边的可行便利问题，而哈密顿图的要求与点有关。 判定：一：Dirac定理（充分条件） 设一个无向图中有N个顶点，若所有顶点的度数大于等于N/2，则哈密顿回路一定存在。（N/2指的是?N/2?，向上取整）二：基本的必要条件 设图G=《V，E》是哈密顿图，则对于v的任意一个非空子集S，若以|S|表示S中元素的数目，G-S表示G中删除了S中的点以及这些点所关联的边后得到的子图，则W（G-S）《=|S|成立。其中W（G-S）是G-S中联通分支数。 三：竞赛图（哈密顿通路） N（N》=2）阶竞赛图一点存在哈密顿通路。 算法：一：在Dirac定理的前提下构造哈密顿回路过程： 1：任意找两个相邻的节点S和T，在其基础上扩展出一条尽量长的没有重复结点的路径。即如果S与结点v相邻，而且v不在路径S -》T上，则可以把该路径变成v -》S -》T，然后v成为新的S.从S和T分别向两头扩展，直到无法继续扩展为止，即所有与S或T 相邻的节点都在路径S -》T上。 2：若S与T相邻，则路径S -》T形成了一个回路。 3：若S与T不相邻，可以构造出来一个回路。设路径S -》T上有k+2个节点，依次为S，v1，v2，。。。，vk，T.可以证明存在节点vi（i属于［1，k］），满足vi与T相邻，且vi+1与S相邻。找到这个节点vi，把原路径变成S -》vi -》T -》vi+1 -》S，即形成了 海南大学硕士研究生2010 —2011学年度第一学期算法设计与分析课程考试论文 学院（中心、所）：信息科学技术学院专业： 计算机应用技术研究方向班级 学生姓名王磊学生证号10081203210008 课程名称：算法设计与分析 论文题目：哈密尔顿回路问题 任课老师：钟声 （以上由学生填写） 教师评阅： 阅卷教师（签名）：年月日 哈密尔顿回路问题 一前言 1857年，英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上著名的难题。 所谓赋权汉密尔顿回路最小化问题是指，给定n个点及n个点两两之间的距离(或权数)，求一条回路，使之经过所有的点，且经过每个点仅一次，而整条回路(也称路径或边界)的总距离(或总权数)最小。理论上讲，这一问题总是可以通过枚举法求出其解的，但由于枚举法的计算量过大，达到(n－1)!的数量级，因而，不是可行的方法。 二哈密尔顿回路问题的最优解 回朔法求解哈密尔顿回路的最优解： 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根 的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 2.1 思想 本问题采用回溯法求解最优解： 回溯法求解：首先把回路中的所有顶点的编号初始化为0，然后，把顶点1当作回路中的第1个顶点，即x0=1，搜索与1邻接的编号最小的顶点，作为它的后续顶点，判断是否满足约束条件，是则到达该顶点，x1取值为满足条件的顶点编号。然后再同样的方式搜索下面的顶点。依次继续下去。 假设在搜索过程中已经生成了通路l=x0x1,…,xi-1，在继续搜索某个顶点作为通路中的xi顶点时，根据约束条件，在V中选择与xi-1邻接的并且不属于l的编号最小的顶点。如果搜索成功，则把该顶点作为通路中的顶点xi，然后继续搜索通路中的下一个顶点。如果搜索失败，就把l中的xi-1删去(回溯)，从xi-1的顶点编号加1的位置开始，继续搜索与xi-2相邻接的且不属于l的编号最小的顶点。这个过程一直继续下去。当搜索到l中的顶点xn-1时，如果xn-1与x0相邻接，就得到了一条哈密尔顿回路；否则，把l中的顶点xn-1删去，继续回溯。最后，在回溯过程中，l中只剩下一个顶点x0，则表明图不存在哈密尔顿回路。 /********************此程序是用来进行无向图的哈密尔顿回路寻找所用*****/ /**********************欢迎使用*********************************************/ #include 回溯法求哈密尔顿回路 2014211053谭富林 一.实验目的和算法分析 试验目的： 通过回溯的方法找出图的一般哈密顿尔回路，并且能够输出结果。 算法分析： 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 哈密顿回路是从某顶点开始，经过图全部顶点一次回到起点的回路。 二.实验内容 1.编写实现算法：给定n点，m条变，找出所有哈密尔顿回路。 2.将输出数据显示在控制台窗体中。 3.对实验结果进行分析。 三.实验开发工具 操作系统：windows8 开发工具:Microsoft visual studio 2010 开发语言:C++ 四.实验操作 程序的思路： 程序的实现： #include 一．简要介绍： 哈密顿回路：哈密顿图是一个无向图，由指定的起点前往指定的终点，途径过所有的其他节点且只经过一次。哈密顿回路即从一指定顶点出发，经历所有点后回到起点。 最短哈密顿回路：在一个有向网中，分别计算每条哈密顿回路上的权值之和，找出其中最小的权值之和。 二．算法： （1）.列出有向网中的所有边，并按权值建立邻接矩阵。 （2）取前n条边，判断它是否构成哈密顿回路。（条件：1.n个顶点全出现；2.定点出现的次数等于2并且每一个顶点在弧头和弧尾各出现一次；3.不存在小于n个顶点的回路即小回路。） 三．描述： （1）.用邻接矩阵存放有向网； （2）用队列存放结点； （3）用指针指向要访问的点。 四．算法流程： 分析：本题是一个典型的哈密顿环算法题。主要思想是用回溯法求所有的方法数，再通过所有方法数的比较得到相应于题目的最优解。（1）.首先有十一个城市，为十一个城市分别标号，以便方便准确索 引和准确定位，建立了三个邻接矩阵分别用来是一个bool 型和两个double型。Bool 型用1来表示两个城市之间相通，0表示不相通。Double型分别用来存放与bool型相对应的经过两个城市的时间和价格。 （2）列出有向网中所有的边，为了简化题目，在遇到两点间既可以走水路又可以走陆路的情况时，据已知条件可以分别算出价钱较低和时间较短的路径，这样就保证了任意两个点之间只存在一条路径，也就符合了哈密顿环的算法成立的要求。 （3）统计不同顶点出现的个数和顶点出现的次数，联系上述描述中所说的条件添加限制条件。、 （4）输出最后所求的最优解。 五．复杂度： （1）因为没有实现路径的权值的有序排列，所以每次都要等遍历完所有的方法数，通过不断与min值比较替换，才能得出最终的min 值，（m+1）*m*(m-1)*^1=(m+1)!,即时间复杂度为n!; 六：说明： （1）本题中所有可行的两做城市之间的连线是双向的，即既可以从A城市到B城市，又从B城市到A城市，所以最后的结论最短路该有两个方向的走法，可以忽略方向，这样可以大大节省空间。（已在图示中用箭头表现）； //递归方法实现哈密顿回路问题 //指定一个城市为出发城市 #include int i; for (i = 1; i < 6 ; ++ i) x[i] = i; output(x); return 0; int n = 5; memset(c, 0, sizeof(c)); c[1][2] = true; c[2][1] = true; c[1][4] = true; c[4][1] = true; c[2][4] = true; c[4][2] = true; c[2][3] = true; c[3][2] = true; c[3][5] = true; c[5][3] = true; c[4][5] = true; c[5][4] = true; c[2][5] = true; c[5][2] = true; c[3][4] = true; c[4][3] = true; for(int i = 1; i <= n; i++) { x[i] = i; } //swap(x[1],x[5]); hamilton(2); //默认以第一个城市开始,搜索解空间树（子集树形式）直接从第二层开始cout << endl; return 0; } 回溯算法的应用 课程名称：算法设计与分析院系： 学生姓名： 学号： 专业班级： 指导教师： 年月日 回溯算法的应用 摘要：回溯法是在包含问题的所有解的解空间树（或森林）中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。 回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。这就是以深度优先的方式系统地搜索问题解的回溯算法，它适用于解决一些类似n皇后问题等求解方案问题，也可以解决一些最优化问题。关键词：回溯法解空间树深度优先搜索 目录 第1章绪论 (1) 1.1 回溯算法的背景知识 (1) 1.2 回溯法的前景意义 (1) 第2章回溯算法的理论知识 (2) 2.1 回溯算法的基本思想 (2) 2.2 回溯算法设计过程 (2) 2.3回溯算法框架 (2) 2.4 回溯算法的一般性描述 (4) 第3章哈密尔顿问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3 算法设计 (5) 3.4 测试结果与分析 (7) 第4章结论 (11) 参考文献 (12)哈密尔顿回路问题
哈密尔顿图的充分必要条件
哈密顿回路算法
哈密尔顿回路问题
C语言哈密尔顿回路
回溯法求哈密尔顿回路试验报告
哈密顿回路
递归方法实现哈密顿回路问题
算法设计与分析--回溯法哈密尔顿回路问题