实验报告测试.docx

实验报告测试.docx【摘要】中国邮政问题是算法中的金典问题。该问题是哈密尔顿回路问题的 变种，同时该问题在很多问题中有所体现。本报告将描述如何利用哈密尔顿 回路完成中国邮政问题，然后分析该算法需要的时间代价和空间代价。
【关键词】中国邮政问题、哈密尔顿回路
1.
2.
3.
设计内容和要求


问题分析

.... 概要设计


详细设计及代码实现..
4.

目录
错误! 错误! 错误! 错误! 错误! 错误! 错误! 错误! 错误! 错误! 错误! 错误!
未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。 未定义书签。
错误！未定义书签。 错误！未定义书签。 错误！未定义书签。 错误！未定义书签。
系统实现


总结
1. 设计要求和内容


设计要求和内容

邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返 回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮 件的每房屋只一次。问怎样的走法使他的投递总行程为最短？这个问题就称
为中国邮路问题。
R13
lW——7 曦1 房取3
R6 &
■BE
房屋
8
H R15
R8
/房屋、1) 房屋F'屈All
编程要求: 层次一：只求解用户输入的图形的中国邮路问题
要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和 最终结果。
层次二：加入图形编辑器
系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图 形和最终结果。
层次三：附加要求
能够图形显示求解过程。
设计要求
问题分析

思路:对一个指定的无向图如下图型，要求一个邮递员经过每个不重复的房屋， 他所管辖的客户中，再返回邮局，要求走过的路径最短.
E15
加”肆
11
RU
5
is.
R8
从规则中可以很容易的发现:路径回路是由这张无向图的哈密顿回路的结果•同时在这几个回路中找 出权最短路径•只要通过哈密顿最短路径回路就可以解决相应问题.

解决该问题的程序需要提供一下输入输出
输入参数：
输入数据有多组数据组成。每组数据仅有一行，不超过100个字符，表示一个无向图顶点和顶点的距离。 输出参数：
对于输入的数据，进行运算找出最短的回路。
例如图1
输入的顶点数和边数分别为3和3
顶点序号-权值-顶点序号为：0 1 1
0 1 2
122
输出：最短哈密尔顿回路为6路径为0-1-2
该问题的解决必须能够建立一棵状态空间是一棵完全树，在求解过程中求所访问的节点数。因此必须使 用哈密尔顿回路算法来完成相关操作。所谓哈密尔顿回路是指在一个无向图中，有一条回路起点和终点 一样且每一个顶点在该回路中出现且仅出现一次。
该问题需要解决两个主要问题，找出回路和最短路径。设计编制两个函数。
函数
功能
注意条件及限制规则
search(p)
哈密尔顿回路寻找函数
当顶点未被遍历且与刚遍历的顶 点之间有边，则退出当下循环；当 顶点号大于N,则对回路数统计， 输出；如果不满足前一个条件，则 退回前一个顶点进行重新遍历。
shaixuanQ
对遍寻的结果进行筛选
对回路求路径长； 存储路径长； 对路经长比较


哈密尔顿回路寻找函数
遍寻的结果进
行筛选
c结束
对遍寻的结果进行筛选，判断是否有哈密尔顿回路


#include <>
#include <>
#include <iostream>
#include <>
#define Max 100
#define INF 6666
using namespace std ;
typedef struct node
{ int cost[Max][Max];