用回溯法求解一般哈密尔顿回路问题课程设计

目 录
引言 1
1 需求分析 2
11问题提出 2
12问题描述 2
13算法描述 3
2 概设计 4
21系统运行环境 4
22算法实现 4
23接口设计 12
24出错处理设计 12
25维护设计 13
3 详细设计 14
31算法分析 14
32程序思路 15
33程序实现 15
34设计环境 19
4 调试分析 20
41哈密尔顿回路连通图 20
42哈密尔顿回路连通图 22
5 总结 23
参考文献 25
附录 26


摘
回溯法种深度优先策略根结点开始搜索解空间树算法该算法带系统性带跳跃性包含问题解解空间树中深度优先策略根节点出发搜索解空间树算法搜索解空间树节点时总先判定该节点否肯定包含问题解果肯定包含跳该节点子树系统搜索逐层祖先节点回溯否进入该子树继续深度优先策略进行探索种深度优先方式系统搜索问题解算法称回溯法回溯法求出问题全部解求出问题解停止问题求解求该问题否解适解组合数较问题哈密尔顿回路路判断图中否存条通顶点次仅次路径文讲回溯法求解意图中否存条哈密顿通路问题具体算法实现






关键词：回溯法 哈密尔顿回路 空间树

引言
回溯法带系统性带跳跃性搜索算法包含问题解解空间树中深度优先策略根结点出发搜索解空间树[1]算法搜索解空间树结点时总先判断该结点否肯定包含问题解果肯定包含跳该结点根子树系统搜索逐层祖先结点回溯否进入该子树继续深度优先策略进行搜索回溯法求问题解时回溯根根结点子树已搜索遍结束 [2]回溯法求问题解时搜索问题解结束种深度优先方式系统搜索问题解算法称回溯法适解组合数较问题
1 需求分析
11问题提出
求解问题（走迷宫图着色等问题）时题目求求出原问题种解决方案类问题解步骤状态构成步骤干种决策方案没固定明确数学解析方法采搜索做法某初始状态出发断前（状态）搜索期终达目标状态原问题解解搜索程中问题身采取搜索方法特点（缺乏全局足够前瞻信息情况进行搜索等）[3]会导致走某状态走情况时必须回头（回步回初状态）尝试 性换方方法试试样断前探索回溯前回溯直终出问题解者路回溯出发点（出现种情况表示原问题解）[4] 注意种搜索程尝试搜索问题解空间中状态路径采深度优先方式着条路径深入前探索
12问题描述
1．设计容：
出存分类法种应出应应算法编程实现
2．设计求：
(1)出种分类法求解算法
(2)编程实现种分类法算法
(3)写算法出时空复杂性分析

13算法描述
该算法讲回溯法求解图中否存哈密尔顿回路问题谓哈密尔顿回路指图（图图）中顶点次仅次通路回溯法解哈密尔顿回路问题首先画出问题解空间树该解空间树棵度 n 树（中 n 图中顶点数）树中第结点度 n余结点度 n1（该结点身相连）编写算法时通判断该边图邻接矩阵中值剪枝果值 1 说明该边存剪枝搜索求图哈密尔顿回路时走顶点重复走已遍历顶点做标记果搜索时找带标记顶点该路径行应剪

2 概设计
算法设计回溯法求解般哈密尔顿回路问题设计容：出存分类法种应出类分类法求解算法编程实现种分类法算法写算法出时间空间复杂性分析
21系统运行环境
根目前市场够提供硬件设计系统硬件环境：
l IBM PC286档次微机便携机种品牌兼容机佳档次386微机
l 512M512M存具备扩展存
l EGAVGATVGASUPERVGA彩色显示器
l 20M硬盘
l 光电鼠机械鼠
软件环境：
l MS（PC）DOS33版
l 采VC++进行开发
22算法实现
1体类
class Cind
{
public
int& operator []( int index ){ return data[index] }

Cind & Cindoperator (Cind &a)
bool operator (Cind &ind)

void CrossWith(Cind &a)
void Mut()
void show()
void SetArc()
double fun()
Cind()
virtual ~Cind()
int * data
static int n
double fitness
}
indcpp implementation of the Cind class


#include stdafxh
#include GrWndapph
#include shapelisth
#include indh
#include nodeh
#include arch
#include mathh

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]__FILE__
#define new DEBUG_NEW
#endif
int Cindn
extern CShapeList node_listarc_list
ConstructionDestruction
CindCind()
{
data new int[n]
bool * flag new bool[n]

for ( int i0 iflag true

int k0

for ( int mn m>0 m )
{
int t rand()m
int j 0

for ( i 0 iif ( flag )
{
if ( j t )
{
data[k++] i
flag false
break
}
j++
}
}

delete[] flag
}

Cind~Cind()
{
delete[] data
}

double Cindfun()
{
double v 0
CNode * pn1*pn2
for ( int i0 i{
pn1 (CNode *)node_listGetShape(data)
pn2 (CNode *)node_listGetShape(data[i+1])

v + sqrt((pn1>x pn2>x)*(pn1>x pn2>x)+
(pn1>ypn2>y)*(pn1>ypn2>y))
}
pn1 (CNode *)node_listGetShape(data[0])
v + sqrt((pn1>x pn2>x)*(pn1>x pn2>x)+
(pn1>ypn2>y)*(pn1>ypn2>y))

return v
}

void CindSetArc()
{
arc_listClear()
CArc * parc
for ( int i0 i{
parc
new CArc((CNode *)node_listGetShape(data)
(CNode *)node_listGetShape(data[i+1]))
arc_listAdd(parc)
}

parc
new CArc((CNode *)node_listGetShape(data)
(CNode *)node_listGetShape(data[0]))
arc_listAdd(parc)
}

void Cindshow()
{
TRACE(The ind＼n)
for ( int i0 iTRACE ( d>data )
TRACE(＼n)
}
void CindMut()
{
int p1 rand() n
int p2 rand() n
int t data[p1]
data[p1]data[p2]
data[p2]t
}
void CindCrossWith(Cind &a)
{
int pos rand() (n1)
pos ++

int * t1 * t2
t1 new int[n]
t2 new int[n]

int k0
for ( int i0 i{
for ( int j0 j{
if ( data a[j] )
break
}
if ( j pos ) find none
t1[k++] data
}
for ( i0 it1[k++] a

k0
for ( i0 i{
for ( int j0 j{
if ( data[j] a )
break
}
if ( j pos ) find none
t2[k++] a
}
for ( i0 it2[k++] data

for ( i0 i{
data t1
a t2
}

delete[] t1
delete[] t2
}

Cind & Cindoperator (Cind &a)
{
if ( this &a )
return * this

for ( int i0 idataa

fitnessafitness
return * this
}

bool Cindoperator (Cind &ind)
{
for ( int i0 iif ( data ind )
return false
return true
}
2群体类
#include indh

class CGroup
{
public
void Reserve()
void Grow()
Cind * GetBest()
void Select()
void CalFitness()
CGroup()
virtual ~CGroup()

int nmml

Cind * group
Cind * pool

int nres
static int gn group length
static double miu
static double gg gerneration gap
static double pmut probability of mutant
static double pres
}
Groupcpp implementation of the CGroup class


#include stdafxh
#include GrWndapph
#include Grouph
#include shapelisth

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]__FILE__
#define new DEBUG_NEW
#endif

extern CShapeList node_listarc_list

int CGroupgn
double CGroupgg
double CGroupmiu
double CGrouppres
double CGrouppmut

ConstructionDestruction

CGroupCGroup()
{
gn100 group length
pmut03
pres 01

srand( (unsigned)time( NULL ) )
Cindn node_listn

group new Cind[gn]
pool new Cind[gn]
nres gn*pres
}

CGroup~CGroup()
{
delete[] group
delete[] pool
}

void CGroupCalFitness()
{
double maxfst0
for ( int i0 i{
groupfitnessgroupfun()
maxfst__max(maxfstgroupfitness)
}

for ( i0 igroupfitnessmaxfstgroupfitness
}

void CGroupSelect()
{
CalFitness()
calculate the sum of fitness of the individul
double sum0
for ( int i0 isum + groupfitness

create a position
for ( i0 i{
double pos rand()*sumRAND_MAX
double tgroup[0]fitness
for ( int j0 jif ( pos < t )
{
poolgroup[j]
break
}
else
t + group[j+1]fitness
}
}
Cind * CGroupGetBest()
{
double vgroup[0]fun()
Cind * pind &group[0]

for ( int i1 iif ( groupfun() < v )
{
pind &group
v groupfun()
}
return pind
}

void CGroupGrow()
{
Select()
Reserve()
cross over
for ( int i0 i{
poolCrossWith(pool[i+1])
grouppool
group[i+1]pool[i+1]
}
mutant
int num gn * pmut 变异体数
for ( i0 i{
int ind rand()gn random select
group[ind]Mut()
}
}
void CGroupReserve()
{
Cind t
for ( int i0 ifor ( int j0 jif ( group[j]fitness > group[j+1]fitness )
{
tgroup[j]
group[j]group[j+1]
group[j+1]t
}
}
23接口设计
1外部接口
(1) 户界面
采图形户界面（GUI）包含菜单钮话框等元素
(2) 软件接口
软件运行windows XP极版
(3) 硬件接口
运行IBM PC386兼容机
24出错处理设计
1系统应具相健壮性避免降低系统错误造成损坏
2关键性操作
25维护设计
系统严格设计规范进行设计保持阶段文档完整性软件维护基础

3 详细设计
工作基础根务求编程实现回溯法求解般哈密尔顿回路问题输出求全部数进行分析进步研究整算法实现

31算法分析
函数功简分析：函数 FirstAdjVex（）求出图邻接矩阵某行存第条边应第顶点函数 NextAdjVex（）求出第顶点解空间树中行相邻顶点函数 initStatus（）初始化踪栈已遍历前已符合条件点放里面函数 backtrack（）进行回溯函数 bool testHami（）判断该图没哈密顿通路函数 Hami（）该算法入口点通调函数 backtrack（）
实现层层递根程序中判断哈密尔顿回路条件——节点访问次仅仅次visitTag[0N]等 1 Hami(G)函数简分析：
1．判断连通图
2．节点进行操作
(1) 初始化访问标志 visitTag
(2) 调试探节点出发找哈密顿通路 果立输出跳出程序
3．时候说明存哈密尔顿回路
32程序思路
创建N节点连通图
输入顶点N值
输入连通图边数
创建条边构成完整连通图
求出哈密尔顿回路解

33程序实现
#include
#include
#include
全局变量声明
int m1 标志哈密尔顿回路总数
int n
int x[128]
int graph[128][128]

void nextvalue(int k)
{
int j
while(1)
{
x[k](int)fmod(x[k]+1n+1)
if(x[k]0) return
if(graph[x[k1]][x[k]])
{
for(j1j {
if(x[j]x[k]) break
}
if(jk)
{
if(k return
}
}
}
}
void print(int x[]int n)
{
int i1
printf(回路dm)
for(i printf(d x[i])
printf(＼n)
m++
}
void hamiltonian(int k)
{
while(1)
{
nextvalue(k)
if(x[k]0) return
if(kn)
print(xn)
else
hamiltonian(k+1)
}
}
void main()
{
int ijeab
printf(***********哈密顿回路递回溯算法***********＼n)
printf(********************************************＼n)
printf(请先创建n结点连通图graph[n][n]＼n)
printf(请输入顶点n值)
scanf(d&n)
printf(图中条边？请输入便创建图)
scanf(d&e)
for(i1i for(j1j graph[i][j]0
for(i1i {
printf(＼n创建第d条边＼ni)
printf(构成边顶点号(1~d)n)
scanf(d&a)
printf(顶点号(1~d)n)
scanf(d&b)
graph[a][b]graph[b][a]1
}

x[1]1
for(i2i x[i]0
printf(＼n求hamiltonian回路解＼n)
hamiltonian(2)
}
34设计环境
操作系统：Windows XP
设计工具：Microsoft Visual C++

4 调试分析
41哈密尔顿回路连通图
1
4
3
2
5
6



42哈密尔顿回路连通图
1
2
3
5
4



5 总结
通次课程设计算法设计分析基础更深认识基掌握回溯法求解般哈密尔顿回路算法思路编程原理提高程序开发力切实体会算法编程程中指导作通课程设计学会课程设计务求完成项程序开发提高身编程力项目理力重现实意义
次课程设计中回溯法哈密尔顿回路熟悉走弯路花时间解相关知识终完成课程设计觉较成感时发现回溯法求解般哈密尔顿回路问题 np 问题时间复杂度 O（n ）空间复杂度 O（2 ）
通次课程设计学东西：
1． 交流毕竟想东西限通交流发现更东西例：程序实现程中没注意程序运行程中会产生异常交流程中发现异常促捕获开发系统更健壮性
2． 程序开发需开发员心完成阶段工作样会出现开发半忽然发现某方出现致命错误需重新开发严重错误想编程时候需避免回溯道理前期做工作期开发会水渠成缩短开发周期

致谢
完成课程设计首先感谢指导老师XX老师严格监督细心指导中够坚持完成课程够较实现求务书求功感谢班学帮助指点没帮助提供资料编程知识精通说想短短时间里完成算法设计事情
表示诚挚感谢

参考文献

[1]算法设计分析 宋 文等编 重庆学出版社2001
[2]算法设计分析 周培德 电子工业出版社2000
[3]算法设计分析 王晓东 电子工业出版社2004
[4] 李登信关 Cayley 图 Hamilton 性猜想[J]渝州学学报(然科学版)1999 年 04 期
[5] 百度网站


附录
该算法具体实现代码：
int FirstAdjVex(const MGraph& Gint v){查找 v 第邻接点
for(int i0iif(Garcs[v][i]adj0){
return i
}
}
return 1
}
int NextAdjVex(const MGraph& Gint vint w){查找 v （相 w ）邻接点
for(int iw+1iif(Garcs[v][i]adj0){
return i
}
}
return 1
}
void initStatus(){
for(int i0ivisitTag[i]0
x[i]1初始化踪栈已遍历前已符合条件点放里面
}
}
bool testHami(const MGraph& G){测试 Hami
for(int i0iif(visitTag[i]){
return 0
}
}
return 1
}
void backtrack(const MGraph& Gint tint idxsum){
int i
visitTag[t]1
x[idxsum]t节点坐标放前栈里
for(iFirstAdjVex(Gt)i>0iNextAdjVex(Gti)){
if(visitTag[i])backtrack(Gi++idxsum)
}
if(testHami(G)){找 HAMI 通路
cout<<图中存条哈密顿通路：<for(i0iif(x[i]>0&&x[i]cout<}
cout<exit(0)提前结束
}
visitTag[t]0回朔访问标志 0次访问
x[idxsum]1清空说明前点符合条件
}
void Hami(const MGraph& G){
if(Garcnumcout<<非连通图<return
}
for(int i0iinitStatus()设置状态
backtrack(Gi0)试探 Gvexs[i]出发通路
}
cout<<没找通路<}
void main()
{
MGraph G
CreatUDN(G)
dispMGraph(G)
Hami(G)
}

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档