实验报告测试.docx

PAGE  PAGE 17 【摘要】中国邮政问题是算法中的金典问题。该问题是哈密尔顿回路问题的变种，同时该问题在很多问题中有所体现。本报告将描述如何利用哈密尔顿回路完成中国邮政问题，然后分析该算法需要的时间代价和空间代价。 【关键词】中国邮政问题、哈密尔顿回路  目录  TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc390078434 1. 设计内容和要求  PAGEREF _Toc390078434 \h 2  HYPERLINK \l _Toc390078435 1.1设计内容  PAGEREF _Toc390078435 \h 2  HYPERLINK \l _Toc390078436 1.2设计要求  PAGEREF _Toc390078436 \h 2  HYPERLINK \l _Toc390078437 2. 问题分析  PAGEREF _Toc390078437 \h 2  HYPERLINK \l _Toc390078438 2.1中国邮路问题  PAGEREF _Toc390078438 \h 2  HYPERLINK \l _Toc390078439 2.2解决问题的方案  PAGEREF _Toc390078439 \h 2  HYPERLINK \l _Toc390078440 3. 概要设计  PAGEREF _Toc390078440 \h 2  HYPERLINK \l _Toc390078441 3.1建立相关数据模型  PAGEREF _Toc390078441 \h 2  HYPERLINK \l _Toc390078442 3.2主要函数算法描述  PAGEREF _Toc390078442 \h 2  HYPERLINK \l _Toc390078443 3.3相关算法性能分析  PAGEREF _Toc390078443 \h 2  HYPERLINK \l _Toc390078444 4. 详细设计及代码实现  PAGEREF _Toc390078444 \h 2  HYPERLINK \l _Toc390078445 4.1代码实现  PAGEREF _Toc390078445 \h 2  HYPERLINK \l _Toc390078446 5. 系统实现  PAGEREF _Toc390078446 \h 2  HYPERLINK \l _Toc390078447 5.1系统操作  PAGEREF _Toc390078447 \h 2  HYPERLINK \l _Toc390078448 5.2 测试数据  PAGEREF _Toc390078448 \h 2  HYPERLINK \l _Toc390078449 6. 总结  PAGEREF _Toc390078449 \h 2  HYPERLINK \l _Toc390078450 1. 设计要求和内容  PAGEREF _Toc390078450 \h 4  HYPERLINK \l _Toc390078451 1.1 设计内容  PAGEREF _Toc390078451 \h 4  HYPERLINK \l _Toc390078452 1.2 设计要求  PAGEREF _Toc390078452 \h 5 设计要求和内容 1.1 设计内容 邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每房屋只一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。 编程要求： 层次一：只求解用户输入的图形的中国邮路问题 要求用户输入图形，求解输入的图形的中国邮路问题，要求能显示图形和最终结果。 层次二：加入图形编辑器 系统自动生成图形，系统求解生成的图形的中国邮路问题，要求能显示图形和最终结果。 层次三：附加要求 能够图形显示求解过程。 设计要求 问题分析 2.1中国邮路问题 思路:对一个指定的无向图如下图型,要求一个邮递员经过每个不重复的房屋,每个房屋只能走一遍.送到他所管辖的客户中，再返回邮局,要求走过的路径最短. 从规则中可以很容易的发现:路径回路是由这张无向图的哈密顿回路的结果.同时在这几个回路中找出权最短路径.只要通过