9、回溯法求解哈密尔顿回路

数学与计算机学院

课程设计说明书课程名称: 算法设计与分析-课程设计

课程代码: 7106620

题目: 回溯法求解一般哈密尔顿回路

年级/专业/班:

学生姓名:

学号:

开始时间:2010 年12 月27 日完成时间:2011 年01月07日课程设计成绩：

学习态度及平时成绩（30）技术水平与实际能

力（20）

创新（5）说明书撰写质量（45）

总分

（100）

指导教师签名：年月日

目录

1 引言 (1)

1.1问题的提出 (1)

1.2任务与分析 (1)

2 算法 (1)

2.1递归回溯法求解哈密顿尔回路算法 (1)

2.2非递归回溯法求解哈密顿尔回路算法 (2)

3 设计方案 (3)

3.1整体设计方案 (3)

3.2程序递归算法的主要代码 (3)

3.3程序非递归算法的主要代码 (4)

3.4程序的其他函数 (5)

4 系统测试 (6)

4.1测试数据 (6)

4.2程序的录入、编译和连接 (6)

4.3运行程序 (7)

4.4进入主界面 (7)

4.4测试递归回溯法求解图的所有哈密顿尔回路 (8)

4.5测试非递归回溯法求解图的所有哈密顿尔回路 (9)

4.6测试第二组数据 (9)

4.7测试退出模块 (10)

结论 (11)

致谢 (12)

参考文献 (13)

摘要

本次我的课程设计题目是“用回溯法求解一般哈密尔顿回路问题”，主要内容是给出用回溯法求解一般哈密尔顿回路问题的算法并编程实现。所涉及到的知识是《算法设计与分析》中的回溯法，以及《图论》中的哈密顿尔回路。回溯法：从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。哈密顿回路：从某顶点开始，经过图G全部顶点一次回到起点的回路。

关键词：回溯法哈密顿尔回路算法编程实现

1 引言

1.1 问题的提出

我所做的课程设计就是用回溯法求解一般哈密尔顿回路问题，即从某顶点开始，经过图G全部顶点一次回到起点的回路。

1.2任务与分析

本课程设计主要的目的是：

通过回溯的方法找出图的一般哈密顿尔回路，并且能够输出。

题目分析：

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

哈密顿回路：从某顶点开始，经过图G全部顶点一次回到起点的回路。

2 算法

2.1递归回溯法求解哈密顿尔回路算法

2.1.1递归求图的所有哈密顿尔回路算法

1）解向量用数组X[1...n]表示；X[k]=0 无合法顶点；X数组初始化为0；

2）若k=n时，需检查x[k]是否有边与x[1]相连（回到起点，构成回路）

3）用 k = 1 启动（指定哈密顿回路的起点）

由此可得以下算法：

status hamilton(int k )

if(k>n-1 && c[x[k-1]][0]==1)

{

output(x);

flag=1;

}

else

for(int i=k;i

{

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1)

hamilton(k+1);

swap(x[i],x[k]);

}

}

2.2非递归回溯法求解哈密顿尔回路算法

2.2.1非递归回溯法求图的所有哈密顿尔回路算法

假定图G=(V, E)的顶点集为V={1, 2, …, n}，则哈密顿回路的可能解表示为n元组X=(x1, x2, …, xn)，其中，xi∈{1, 2, …, n} ，并有如下约束条件：

(xi, xi+1)∈E (1≤i≤n－1)

(xn, x1)∈E

xi≠xj (1≤i, j≤n，i

≠j)

由此可得以下算法：

1．将顶点数组x[n]初始化为0，标志数组visited[n]初始化为0；

2．k=1; visited[1]=1; x[1]=1; 从顶点1出发构造哈密顿回路；

3．while (k>=1)

3.1 x[k]=x[k]+1，搜索下一个顶点;

3.2 若(n个顶点没有被穷举) 执行下列操作

3.2.1 若(顶点x[k]不在哈密顿回路上&&(x[k-1],x[k])∈E)，

转步骤3.3;

3.2.2 否则，x[k]=x[k]+1，搜索下一个顶点；

3.3 若数组x[n]已形成哈密顿路径，则输出数组x[n]，算法结束；

3.4 否则，

3.4.1 若数组x[n]构成哈密顿路径的部分解，

则k=k+1，转步骤3；

3.4.2 否则，重置x[k]，k=k-1，取消顶点x[k]的访问标志，

转步骤3；

3 设计方案

3.1整体设计方案

这两个算法是通过C++语言编程实现的，在主菜单栏可以分成三块：1、递归求图的所有哈密顿回路2、非递归求图的所有哈密顿回路0、退出程序。

3.2 程序递归算法的主要代码

void hamilton(int k )

{//递归算法

if(k>n-1 && c[x[k-1]][0]==1)

{

output(x);

flag=1;

}

else

for(int i=k;i

{

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1)

hamilton(k+1);

swap(x[i],x[k]);

}

}

3.3程序非递归算法的主要代码

void hamilton(int n, int x[N], bool c[N][N])

{//非递归算法

int i, k;

bool*visited = new bool[n];

for(i =0; i

{

x[i] = 0;

visited[i] = false;

}

visited[0]=1;

x[0]=0;//默认以第一个城市开始

k =1; //搜索解空间树（子集树形式）直接从第二层开始

while(k >=1)

{

x[k]++;

while(x[k] < n)

if(visited[x[k]]==0 && c[x[k - 1]][x[k]]==1) break;

else

x[k]++;

if(x[k]

for(k=0;k

{

cout<

flag=1;

}

cout<

k--;

}

else if (x[k]

visited[x[k]]=1;

k++;

}

else

{

x[k]=0;

k--;

visited[x[k]]=0;

}

}

}

3.4程序的其他函数

3.4.1输出函数主要代码

void output(int x[])

{//输出函数

for(int i=0;i

cout<

cout<

}

3.4.2建立邻接矩阵函数 void Creat_M() {//建立邻接矩阵 memset(c, 0, sizeof(c)); int i=0;

cout<<"请输入图的结点数:"; cin>>n;

cout<<"请输入"<>c[i][j];

}

}

}

4 系统测试

首先进入VC++6.0，打开源程序文件 “哈密顿回路（递归与非递归）.cpp ”，然后进入源程序，接着选择Build 下的Execute person.exe 即可,也可以不打开工程，直接双击“哈密顿回路（递归与非递归）.exe ”也可以直接运行程序。

4.1测试数据

第一组数据位4阶完全图，第二组数据为3阶完全图。

4.2程序的录入、编译和连接

如图4.1所示。

第二组：0 1 1

1 0 1 1 1 0 第一组：0 1 1 1 1 0 1 1 1 1 0 1

1 1 1 0

图4.1 源程序的录入、编译和连接4.3运行程序

如图4.2所示。

图4.2 运行程序

从图中可见程序能够成功的运行。

4.4进入主界面

如图4.3所示。

图4.3 菜单界面

4.4测试递归回溯法求解图的所有哈密顿尔回路

首先输入操作1，显示如图4.4界面。

图4.5 递归回溯法求解哈密顿尔回路

从上图可见能够回溯法递归输出图的哈密顿尔回路功能。

4.5测试非递归回溯法求解图的所有哈密顿尔回路

在主界面下输入2号功能键，将显示读者所有已借图书信息。如图4.6所示。

图4.6非递归回溯法求解哈密顿尔回路

程序与递归的结果一样，正确显示出4阶完全图的哈密顿尔回路，模块测试完成。

4.6测试第二组数据

按照测试第一组数据的步骤，测试第二组3阶完全图邻接矩阵。测试结果分别如图4.7和4.8所示。

图4.7 递归测试第二组数据结果

图4.8 非递归测试第二组数据结果如图可以说明，成功地输出了3阶完全图的哈密顿尔回路。

4.7测试退出模块

在主界面下输入0号功能键，观察结果。图4.9所示。

图4.9 程序退出

结论

本次课程设计的题目是用回溯法求解一般哈密顿尔回路问题，旨在了解回溯法以及用这种方法求解图中的哈密顿尔回路回路，方便我们寻找某些复杂的图形的哈密顿尔回路。通过这次课程设计，使我了解了算法的设计与分析的重要性，使我明白了算法的设计和分析与当今社会的发展息息相关，并且提高了自身运用知识和变通知识的能力。

在这个课程设计中，我我首先通过课堂所学习的回溯法找出了简单的解哈密顿尔回路的方法，然后通过课后的资料使解法更加深入化，最后通过反复推敲得到了比较精确的解题算。由此，我写了递归版和非递归版两个算法，这两个算法各有各的特点，但是其宗旨是不变的，就是运用回溯法解题，只是通过不同的数据结构表达出来。最后，结合所学过的C++语言知识，编出来相对应的递归和非递归回溯法解哈密顿尔回路的程序，经测试我的算法和程序是正确的。但是这个程序尚且不够完善，由于本人的水平有限，暂时无法使用MFC来实现可视化的界面，程序中也存在着很多可以延伸的问题有待解决。

总之，通过这次课程设计，不仅提高了自己的算法设计与分析能力，而且提高了对c++编程语言的操作水平。虽然程序尚不完美，但是能将自己的知识运用到实际已经是很大的成功。

致谢

感谢谢春芝老师本学期对我课程设计的教导，感谢黄襄念老师辛勤栽培，他们给予了我莫大的支柱。感谢我身边的同学们，感谢所有帮助过我的人。如果没有你们的帮助，这次课程设计很难一个人完成，在此我致以衷心的谢意。

参考文献

[1] 严蔚敏吴伟民著. 《数据结构》（C语言版）(第三版). 北京：清华大学出版社2007.4

[2] 谭浩强著. 《C程序设计》(第三版).北京：清华大学出版社；2006.9

[3] Anany Levitin 著. 潘彦译《算法设计与分析基础》(第二版).北京：清华大学出版社；2010.1

[4] [美] S巴斯著.计算机算法：设计和分析引论. 朱洪等译上海：复旦大学出版社；1985.1

附录

#include

#include

using namespace std;

#define N 20

bool c[N][N];

int x[N];

int n;

bool flag =0;

void output(int x[])

{//输出函数

for(int i=0;i

cout<

cout<

}

void hamilton(int k )

{//递归算法

if(k>n-1 && c[x[k-1]][0]==1)

{

output(x);

flag=1;

}

else

for(int i=k;i

{

swap(x[k],x[i]);

if ( c[x[k-1]][x[k]]==1)

hamilton(k+1);

swap(x[i],x[k]);

}

}

void hamilton(int n, int x[N], bool c[N][N])

{//非递归算法

int i, k;

bool*visited = new bool[n];

for(i =0; i

{

x[i] = 0;

visited[i] = false;

}

visited[0]=1;

x[0]=0;//默认以第一个城市开始

k =1; //搜索解空间树（子集树形式）直接从第二层开始while(k >=1)

{

x[k]++;

while(x[k] < n)

if(visited[x[k]]==0 && c[x[k - 1]][x[k]]==1)

break;

else

x[k]++;

if(x[k]

{

for(k=0;k

{

cout<

flag=1;

}

cout<

k--;

}

else if (x[k]

{

visited[x[k]]=1;

k++;

}

else

{

x[k]=0;

k--;

visited[x[k]]=0;

}

}

}

void Creat_M()

{//建立邻接矩阵

memset(c, 0, sizeof(c));

int i=0;

cout<<"请输入图的阶数:";

cin>>n;

cout<<"请输入"<

for(i=0;i

{

for(int j=0;j

{

cin>>c[i][j];

}

}

}

void menu()

{

int order,i;

cout<<" ................................................................."<

cout<<" ....................... 菜单 ..............................."<

cout<<" ................................................................."<

cout<<" .... 1 回溯法求图的所有哈密顿回路（递

归） ...."<

cout<<" .... 2 回溯法求图的所有哈密顿回路（非递

归） ...."<

cout<<" .... 0 退出程

序...."<

cout<<" ................................................................."<

cout<<" ................................................................."<

cout<<"请输入您的操作:";

cin>>order;

switch(order)

{

case 1:

system("cls");

cout<<"\t"<<"..........................创建邻接矩阵............................."<

Creat_M();

cout<<"\t"<<"...............回溯法求图的所有哈密顿回路（递归）.................."<

for(i = 0; i < n; i++)

{

x[i] = i;

}

hamilton(1);

if(!flag)

cout<<"无哈密顿回路!"<

system("pause");

system("cls");

menu();

break;

case 2:

system("cls");

cout<<"\t"<<"..........................创建邻接矩阵............................."<

Creat_M();

cout<<"\t"<<"................回溯法求图的所有哈密顿回路（非递归）..............."<

hamilton(n, x, c);

if(!flag)

cout<<"无哈密顿回路!"<

system("pause");

system("cls");

menu();

break;

case 0:

system("cls");

cout<<"\t"<<"..........................谢谢使用............................."<

default:

cout<<"输入命令有误，请重新输入；"<

system("pause");

system("cls");

menu();

}

}

void main()

{

cout<<"\t"<<"....................欢迎进入哈密顿回路系统...................."<

cout<<"\t"<<".........................";

system("pause");

system("cls");

menu();

}

哈密尔顿回路问题

哈密尔顿回路算法比较 一、贪心法 贪心法通常用来解决具有最大值或最小值的优化问题。通常从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元素，以便尽快地构成问题的可行解。 贪心法通过一系列选择得到问题的解。其所做出的每一个选择都是当前状态下的局部最好选择，即贪心选择。贪心法并不总能得到问题的最优解。 利用贪心法解哈密尔顿回路的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

迷宫求解问题资料

迷宫求解问题 摘要：用矩阵表示迷宫，将矩阵表示的迷宫转换成无向图，用邻接表存储。对无向图从入口结点开始广度优先搜索，用一个一维数组存储各个结点的前驱结点的编号，通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2，依次类推直到找到出口结点。 关键字：矩阵迷宫求解 一、需求分析 1.程序题目： 迷宫求解问题。迷宫是一个如下所示的m行n列的0-1矩阵，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到周围8个方向的任意一个无障碍的单元，编写程序给出一条通过迷宫的路径或者报告一个“无法通过”的信息。 入口->(0，0，0，1，0，0，0，1，0，0，0，1，0，0，1) (0，1，0，0，0，1，0，1，0，0，0，1，1，1，1) (0，1，1，1，1，1，0，1，0，0，1，1，1，0，1)

(1，1，0，0，0，1，1，0，1，1，0，0，1，0，1) (1，0，0，1，0，1，1，1，1，0，1，0，1，0，1) (1，0，1，0，0，1，0，1，0，1，0，1，0，1，0) (1，0，1，1，1，1，1，0，0，1，1，1，1，0，0) (1，1，1，0，1，1，1，1，0，1，0，1，0，1，0) (1，0，1，0，1，0，1，1，1，0，1，0，0，0，1) (0，1，0，1，0，1，0，0，0，1，1，0，0，1，0)->出口 2．程序说明及任务： 迷宫问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图C。 计算机走迷宫的方法是，采取一步一步试探的方法。每一步都从东开始，按顺时针对8个方向进行试探，若某方向上maze（x，y）=0，表示可以通行，则走一步；若maze（x，y）=1，表示不可以通行，须换方向再试，直到8个方向都试过；若maze （x，y）均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此，需设置一个栈，用于记录所走过的位置和方向（i,j,dir）。当退回一步时，从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和方向重新进栈，并走到新的位置。

算法实验 递归回溯解八皇后问题

深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制

一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i0 do X(k)←X(k)+1 //移到下一个位置 while X(k)<=n and not Judge(k) do //判断能否放置皇后 X(k)←X(k)+1 repeat if X(k)<=n //找到一个位置 then if k=n //是一个完整的解吗

回溯法之N皇后问题(C语言)

//回溯法之N皇后问题当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include #include int n,stack[100]; //存当前路径 int total; //路径数 void make(int l) //递归搜索以stack[l]为初结点的所有路径 { int i,j; //子结点个数 if (l==n+1) { total=total+1; //路径数+1 for(i=1;i<=n;i++) printf("%-3d",stack[i]); //输出第i行皇后的列位置stack[i] printf("\n"); exit; //回溯（若试题仅要求一条路径，则exit改为halt即可）} for (i=1;i<=n;i++) { stack[l]=i; //算符i作用于生成stack[l-1]产生子状态stack[l]; if (!att(l,i)) make(l+1); } //再无算符可用，回溯 } int att(int l,int i) { int k; for (k=1;k

算法实验报告：罗密欧与朱丽叶迷宫求解

河南科技大学 课程设计报告 课程名称：算法设计与分析 设计题目：罗密欧与朱丽叶迷宫求解问题 院系：电子信息工程学院 专业：计算机科学与技术 班级：计算机092班 学生姓名: 学号:09************ 起止日期: 2011年5月28日 - 2011年6月3日指导教师:孙士保、张明川、冀治航

课程设计题目罗密欧与朱丽叶的迷宫问题 姓名*** 学号091040602** 班级092班系别电子信息工程学院专业计算机科学与技术 组别1人组长*** 组员*** 指导教师姓名孙士保、张明川、冀治航 课程设计目的 进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。 设计环境1. PC兼容机 2．Windows 2000/XP操作系统3．TC集成开发环境或其他C语言开发环境 课程设计要求和任务要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题； 2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存 到文件中； 3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 4．对系统进行功能模块分析、画出总流程图和各模块流程图； 5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单； 6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块； 7．所有程序需调试通过。 任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括： 1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线； 2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。 课程设计工作进度计划 序号起止日期工作内容 1 下发任务书，分组，选定课题，查阅相关资料 2 总体设计，划分模块 3 编制源程序 4 上机调试，修改、完善系统 5 程序检查 6 撰写说明书

哈密尔顿图的充分必要条件

哈密尔顿图的充分必要条件 摘要 图论在现实生活中有着较为广泛的应用, 到目前为止,哈密尔顿图的非平凡充分必要条件尚不清楚,事实上,这是图论中还没解决的主要问题之一,但哈密尔顿图在实际问题中,应用又非常广泛,因此哈密尔顿图一直受到图论界以及运筹学学科研究人员的大力关注. 关键词:哈密尔顿图;必要条件;充分条件;

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)。

迷宫问题

算法设计与分析课程设计罗密欧与朱丽叶的迷宫问题设计分析测试报告 程序算法设计说明书

一、前言 1、题目：罗密欧与朱丽叶的迷宫问题。 罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这些道路。 2、程序编制环境相关说明 硬件：装有windows操作系统的计算机 软件：Visual C++ 2008

二、程序主要算法设计分析说明 1、算法设计思路 用回溯法解迷宫问题时，用排列树表示其解空间比较合适。可行性约束函数减去不满足约束条件（x,y,z）已越界的子树。在排列树的第i+1层节点z处用board[z][x][y]记载所在的房间。当bool stepok(int x,int y,int z)返回为false时，以z为根的子树中所有子树都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪枝。 算法调用递归方法void backtrack(int dep,int x,int y,int di)实现回溯搜索。void backtrack (int dep,int x,int y,int di)搜索排列树中第dep层子树。数组board[0][x][y]记录排列树中的节点信息。dirs记录当前节点对应的转弯数， best记录最少转弯数。 在算法void backtrack (int dep,int x,int y,int di)中，当i>n时，算法搜索至叶节点，其相应的转弯数dirs。如果dirs>best,则表示当前解优于最优解，此时更新best。当i≤n时，当前扩展节点位于是排列树的第i-1层。此时算法选择下一个要搜索的方向，以深度优先的方式递归地对相应子树进行搜。对于不满足上界约束的节点，则减去相应子树。 算法void backtrack (int dep,int x,int y,int di)动态地生成问题的解空间树。 时间复杂度为整个状态空间，即迷宫大小，O(m*n)

八皇后问题及解答

八皇后问题 问题描述： 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突 （在每一横列，竖列，斜列只有一个皇后）。 求解： 标题: 八皇后问题的解（回溯法程序代码） 发信站: 网易虚拟社区(Fri Jul 14 10:06:52 2000),站内信件 以前上学的时候，写8皇后程序的时候偷懒用最笨的算法，在8086上计算十皇后的时候，我放了张纸条，说明计算机正在运行，然后去吃饭，吃完以后，才看到结果。前几天，刚好有空，所以重写了一次，以补当年的遗憾。 #include "stdio.h" int attacked(int *array,int position){ int flag=-1; float step; if(position==1) return flag; for(step= 1.00;step

(array+(int)step)-*(array+position))/(step-position))==-1){ flag=1; break;}} return flag;}void main(void){ int countSum,queenSum,printCount,*queenArray,queenPosition=0; int tempArray[20]={66,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; countSum=1; queenArray=tempArray; printf("input you queenSum here: "); scanf("%d",&queenSum); fflush(stdin); if(queenSum<4){ printf("the %d queen's sum is 0\n",queenSum); return;}for(;;){ if(countSum=queenSum){ if(*(queenArray+countSum-1)

回溯法实验(n皇后问题)

算法分析与设计实验报告第六次实验

附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include #include #include #include"math.h" using namespace std; class Queen

{ friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："<

哈密顿回路算法

哈密顿回路算法 概念：哈密顿图：图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，即形成了

罗密欧与朱丽叶迷宫求解问题

课程设计说明书 课程名称＿＿软件专题训练＿＿＿＿ 题目罗密欧与朱丽叶迷宫求解问题＿ 院系＿电子信息工程学院计算机系＿ 班级＿计算机科学与技术103班＿＿ 学生姓名＿＿＿＿＿＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿

课程设计任务书 课程名称＿＿算法设计与分析＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系＿电子信息工程学院计算机系＿ 班级＿＿＿计算机103班＿＿＿＿＿ 学生姓名＿＿＿＿魏鹏超＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿

河南科技大学 课程设计报告 课程名称＿＿软件专题训练＿＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系：电子信息工程学院计算机系 专业：计算机科学与技术 班级：计算机10级 学生姓名:学号: 起止日期: 2012年5月21日~ 2012年5月27日指导教师:孙士保、冀治航

目录 第一章需求分析 (4) 1.1课程设计题目 (4) 1.2 课程设计任务及要求 (4) 1.3运行环境及开发工具 (4) 第二章概要设计 (5) 2.1系统流程图 (5) 第三章详细设计 (6) 3.1函数划分 (6) 3.2函数之间的关系 (6) 第四章系统调试与操作说明 (7) 4.1系统调试及操作说明 (7) 第五章课程设计总结体会 (8) 5.1课程设计总结 (8) 5.2致谢 (8) 5.3参考文献 (8)

第一章需求分析 1.1课程设计题目 罗密欧与朱丽叶的迷宫问题 1.2 课程设计任务及要求 1、对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽 叶的所有最少转弯道路 2、程序能够演示一条罗密欧找到朱丽叶的路线过程等 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。 1.3运行环境及开发工具 硬件：装有windows操作系统的计算机 软件：Visual C++6.0

回溯算法与八皇后问题N皇后问题Word版

回溯算法与八皇后问题(N皇后问题) 1 问题描述 八皇后问题是数据结构与算法这一门课中经典的一个问题。下面再来看一下这个问题的描述。八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？ 2 回溯算法 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。 下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘： 1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列 2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没 有两个皇后)，若不满足，跳到第4步 3) 在当前位置上满足条件的情形： 在当前位置放一个皇后，若当前行是最后一行，记录一个解； 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；

若当前行是最后一行，当前列不是最后一列，当前列设为下一列； 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置； 以上返回到第2步 4) 在当前位置上不满足条件的情形： 若当前列不是最后一列，当前列设为下一列，返回到第2步; 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。 为了便于将上述算法编程实现，将它用另一种形式重写： Queen() Loop: if check_pos(curr_row, curr_col) == 1 then put_a_queen(curr_row, curr_col); if curr_row == N then record_a_solution(); end if; if curr_row != N then curr_row = curr_row + 1; curr_col = 1; else if curr_col != N then curr_col = curr_col + 1; else backtrack(); end if; end if; else if curr_col != N then

n皇后问题算法实验报告

算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013.12.3 姓名：杜茂鹏 班级：计科1101 学号：0909101605

一、实验内容及要求 在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法中的应用 三、算法分析 1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。 2.算法模块简要分析 用数组存储皇后的位置，将i设置为0. Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。 Int print(*x,n):打印皇后解的空间。 Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。 Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时，

sum++；输出该组可行解的个数和位置的矩阵。并且i--，回溯到上一层继续搜索可行解。 四、运行结果及分析 1、三皇后没有可行解 2、 2.4个皇后有2个可行解 3.5皇后有10个可行解 五、源代码 #include static int n, sum=0;//可行解个数 static int locate[20]; int place(int k) {//判断是否在一条线上并返回0,1 for(int i=1;in){

回溯法解八皇后问题

回溯法解八皇后问题 在N * N 格的棋盘上放置彼此不受攻击的N 个皇后。N个皇后问题等价于在N * N 格的棋盘上放置N 个皇后，任何2个皇后不在同一行或同一列或同一斜线上。当N等于8，就是著名的八皇后问题。 此问题是通过C语言程序编写的，在Turboc环境下完成实现的。输出结果见（输出结果。TXT文件） 详细代码为： /*///////////////////////////////////////////////////////////////////// /// /////The programming is a complex problem about the ways of queens./////// /////Programmer: Luo Xiaochun /////// /////Completed date: 2007.12 //////// /////V ersion number: Turboc 2.0 //////// /////////////////////////////////////////////////////////////////////// /*/ #include #include #define false 0 #define true 1 #define quesize 8 int gx[quesize+1]; int sum=0; int place( int k ); void print( int a[] ); void nqueens( int n ); FILE *fp; int main( ) { system("cls"); fp = fopen("outfile.txt", "w");

哈密尔顿回路问题

海南大学硕士研究生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，则表明图不存在哈密尔顿回路。

回溯法解迷宫问题

算法分析与设计论文论文题目：回溯法解迷宫问题 作者姓名陈相艺 任课教师王松 学院班级计算机学院计自1101班 学号201126100404 提交日期2013年6月10日

回溯法解迷宫问题 陈相艺 （计算机+自动化1101 201126100404） 摘要：迷宫的存储结构以二维数组来存储，用0，1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法，其实迷宫问题是一种特殊形式图的问题，因此，迷宫总量可转化为图的问题来解决。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.本文采用回溯法求解迷宫路径，算法用到数据结构中的栈。 关键词：迷宫；二位数组；回溯法；栈；矩阵。 1.前言 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子放入,在盒中设立了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口处放置一快奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走通迷宫的线路.设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 2.迷宫问题的算法思想及研究 迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷宫路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。 为了表示迷宫，设置一个数组，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，数组如下所示： int mg[10][10] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,1,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; （可根据自己喜好，改变迷宫的大小和通道安排。） 对于迷宫中每个方块，都有上下左右四个方块相邻，第i行第j列的当前方块的位置为(i,j)，

八皇后问题(回溯法)

八皇后问题（回溯法）2009-08-11 12:03问题描述： 求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局，这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向互相捕捉。 解题思路： 总体思想为回溯法。 求解过程从空配置开始。在第1列~的m列为合理配置的基础上，再配置第m+1列，直至第n列也是合理时，就找到了一个解。在每列上，顺次从第一行到第n行配置，当第n行也找不到一个合理的配置时，就要回溯，去改变前一列的配置。 为使在检查皇后配置的合理性方面简易方便，引入一下4个工作数组： ?数组col[i],表示在棋盘第i列，col[i]行有一个皇后； ?数组a[],a[k]表示第k行上还没有皇后； ?数组b[],b[k]表示第k列右高左低斜线上没有皇后； ?数组c[],c[k]表示第k列左高右低斜线上没有皇后； 代码： #include #include void queen(int N) { //初始化N+1个元素，第一个元素不使用int col[N+1]; //col[m]=n表示第m列，第n行放置皇后 int a[N+1]; //a[k]=1表示第k行没有皇后 int b[2*N+1]; //b[k]=1表示第k条主对角线上没有皇后 int c[2*N+1]; //c[k]=1表示第k条次对角线上没有皇后 int j,m=1,good=1;char awn; for(j=0;j<=N;j++) {a[j]=1;} for(j=0;j<=2*N;j++) {b[j]=c[j]=1;} col[1]=1;col[0]=0; do { if(good) { if(m==N) //已经找到一个解

回溯法实验(n皇后问题)(迭代法)

算法分析与设计实验报告第三次附加实验

附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include #include #include #include"math.h" using namespace std; class Queen

{ friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："<

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;icost[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;icost[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)