哈密顿回路算法分析 |
您所在的位置：网站首页 › 求使用回溯法求所有可能的哈密顿环 › 哈密顿回路算法分析 |
哈密顿回路算法分析
|
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言一、哈密顿回路问题分析二、问题的解决方案三、算法问题求解中所遇到的问题及解决方案四、算法测试总结 前言提示：这里可以添加本文要记录的大概内容： 例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。 提示：以下是本篇文章正文内容，下面案例可供参考 一、哈密顿回路问题分析问题描述：哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。从一张普通图的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。 哈密顿回路条件约束： 1.加入路径的节点与前一个加入路径的顶点一定是连通的； 2.加入路径的最后一个顶点和第一个顶点一定是连通的； 3.路径上不能出现重复的顶点。 问题要求：随机生成无向图，且图中部分顶点间无通路，设计算法找到一条哈密顿回路，实现可视化展示 二、问题的解决方案用回溯法求解哈密顿回路，首先把n元组的每一个分量初始化为0，然后深度优先搜索解空间树，如果满足约束条件，则继续进行搜索，否则，将引起搜索过程的回溯。回溯法从根节点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树种任一结点时，先判断该结点该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也急速判断该结点是否包含问题的最优解，如果肯定不包含，则跳过对以该结点为根的子树的搜索；否则进入以该结点为根的子树，继续按照深度优先策略搜索。 算法分析图如下 如何避免回溯时每次都从头结点开始遍历，定义一个新的头指针指向上一次遍历到的顶点， 代码如下： Node *tmp[n]; //避免回溯时每次都从头节点开始遍历，定义一个新的头指针指向上一次遍历到的顶点 for(int i=0;i printf("请输入节点个数："); scanf("%d",&n); for(int i=0;i printf("请输入与顶点%d相连的顶点个数：",i+1); scanf("%d",&num); printf("请输入与顶点%d相连的顶点，格式如（1 2 3）：",i+1); for(int j=0;j creat(); int result[n]; //存放路径的数组 bool visited[n]; //对在路径上的顶点进行标记 for(int i=0;i if(!visited[p->v]) { tmp[result[k]]=p; result[++k]=p->v; //相连顶点不在路径上，加入路径中 visited[p->v]=true; //标记已在路径上 break; } else p=p->next; } if(p==NULL) //与剩余顶点不相连，回溯 { visited[result[k]]=false; tmp[result[k]]=a[result[k]]; k--; } else { if(k==n-1) //对最后一个顶点进行验证，是否可以和起点形成回路 { Node *q=tmp[result[k]]->next; while(q!=NULL) { if(q->v==0) break; q=q->next; } if(q!=NULL) break; else //不能形成回路，回溯 { visited[result[k]]=false; tmp[result[k]]=a[result[k]]; k--; } } } } if(k==-1) printf("无解"); else { printf("满足条件的一个解路径为："); for(int i=0;i |
【本文地址】
今日新闻 |
推荐新闻 |