目录

摘要... I

ABSTRACT.. II

第一章   图论相关的问题... 1

1. 图的基本知识... 1

2. 欧拉图与哈密尔顿图... 1

3. 哈密尔顿回路... 2

4. 本文选题的背景... 2

第二章  哈密尔顿算法及特点分析... 4

1. 算法思想的提出... 4

2. 算法的规则分析... 5

3. 算法... 5

3.1 优化方法... 5

3.2 几个概念... 6

4.算法的应用... 7

4.1赋权型Hamilton路问题的计算模型... 7

4.2算法步骤：... 8

4.3无向图中的Hamilton路问题... 8

第三章  运动会系统中的哈密尔顿算法... 9

1. 问题的提出... 9

2. 模型建立... 11

3．算法设计... 12

4．模型求解要点... 15

5. 算法合理性分析... 15

6. 合理安排比赛项目顺序结果... 16

7. 解决“运动员连续参加比赛”问题的建议及方案... 17

第四章  问题的推广... 19

第五章  结论与展望... 25

第六章  参考文献... 26

第七章  致谢... 27

附录... 28

1.    原文: 28

2.    译文... 34

摘要

随着时代的进步，社会生产力高速发展，新技术层出不穷信息量急剧膨胀，整个人类社会已成为信息化的社会,人们对信息和数据的利用和处理已经进入自动化、网络化和社会化的阶段。如在查找情报资料、处理银行帐目、仓库管理、科研生产等方面，无不需要利用大量的信息资源。因此，如何有效地进行数据信息的管理和利用，已经成为人们普遍关注的课题。

信息在不同的领域里有着不同的概念，在管理科学领域中，通常认为信息是经过加工处理后的一种数据形式，是一种有次序的符号排列，它是系统传输和处理的对象。处在信息时代的今天，信息的作用越来越为人们所重视。制定成绩计划，研究投资策略，都离不开对信息的充分利用。管理信息系统（Management  Information  System,缩写MIS）是一种“人机系统”，它以特定的模式支持一个组织内各级组织机构之间的通讯，对信息资源进行综合开发，管理和利用，实现对该组织的有效管理。它通过对数据的加工处理，及时为管理与决策分析提供信息。

     本文运用哈密尔顿路算法的无向完全图中的最短哈密尔顿路算法进行了研究，并得到了一个解决合理安排比赛项目顺序模型的好的算法。

 关键词：哈密尔顿路算法 无向完全图 最短路径 赛事安排

ABSTRACT

Along with the time progress, the social productive forces have been speedly developing, the new technology emerges one after another incessantly ,the information content to inflate suddenly, the human society has become the informationization social, people already entered automated, the network and the socialized stage to the information and the data use and processing. If in the search intelligence information, processes aspects and so on bank account, storage management, scientific research production, needs to use the massive information resource all. Therefore, how carries on the data message effectively the management and the use, already became the topic which the people paid attention generally.

The information has the different concept in the different domain, in the management science domain, after usually thought the information is the process processing processing one kind of data form, is one kind has the order mark arrangement, it is the system transmission and the processing object. Occupies the information age today, the information function more and more takes for the people. The formulation result plan, the research investment strategy, cannot leave to the information full use. Management information system (Management Information System,Condenses MIS) is one kind “the man-machine system”, it supports in an organization by the specific pattern between all levels of organizations and agencies communication, carries on the comprehensive development to the information resource, the management and the use, realizes to this organization's effective management. It through to data processing processing, promptly provides the information for the management and the decision analysis.

This article utilized the Hamilton road algorithm non-to conduct the research to the complete chart in shortest Hamilton road algorithm, and obtained a solution reasonable arrangement event order model good algorithm.

Key word: Hamilton road algorithm, No plans to complete ,Shortest path,Sports event arrangement

第一章   图论相关的问题

1. 图的基本知识

在日常生活,生产活动及科学研究中,人们常用点表示事物,用点与点之间是否有连线表示事物之间是否有某种关系,这样构成的图形就是图论中的图.其实,集合论中二元关系图都是图论中的图．在这些图中，人们只关心点之间是否有连线，而不关心点的位置，以及连线的曲直，这就是图论中的图与几何学中的图形的本质区别．

引进图的概念，用Ｇ表示无向图，Ｄ表示有向图，有时也用Ｇ泛指图（无向的或有向的），可是Ｄ只以表示有向图．

2. 欧拉图与哈密尔顿图

通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路. 具有欧拉回路的图称为欧拉图, 具有欧拉通路而无欧拉回路的图称为半欧拉图.

经过图（无向图或有向图）中所有边一次且仅一次的通路称为哈密尔顿通路.经过图中所有顶点一次且仅一次的回路称为哈密尔顿回路. 具有哈密顿回路的图称为哈密尔顿图.

图G=(V,E)表示n阶简单图, 哈密尔顿路是阶为n的路Pn。如果n阶图G有长为n的圈Cn，则称图G是哈密尔顿(hamilton或简记H)图。如果n阶图G的任两点x,y均有以它们为端点的阶为n的路，称n阶图G是哈密尔顿连通图。如果n阶图G的每两点有以它们为端点的阶为m至n的每个长度的路。称图G是[m;n]泛连通图。

3. 哈密尔顿回路

1857年，英国数学家哈密尔顿(Hamilton)提出了著名的哈密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权哈密尔顿回路最小化问题：这两个问题成为数学史上著名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权哈密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋哈汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权哈密尔顿问题进行解决；因此，赋权哈密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权哈密尔顿问题的最优解总可以用枚举法求出；但在实际工作中，枚举法的计算量巨大，对于n个点的问题存在(n－1)!条哈密尔顿回路，当n比较大时，枚举法显然是行不通的，为此，优化专家们提出了启发式算法[1]，以期求得该问题的近似最优解。而不同算法之目的是共同的，即在多项式的运算量内，尽可能提高其解的精度。其中应用比较广泛的有Clarke和Wright的C－W算法，Norback和Love的几何算法[2]，在此，称这些算法为经典启发式算法，简称经典算法，这些算法的一个共同特点就是非优化性。针对这一特点，本文提出一种局部优化的算法，对业已求得的哈密尔顿回路进行优化。这种算法的结果是以经典算法结果为起点的局部优化解，因此，该算法极大改进了经典启发式算法的性能，且在目前可考证的情况下，均能求得最优解；但是，是否在任何情况下都能求得最优解则尚待证明。

4. 本文选题的背景

运动会管理系统的发展历史可以追溯到20世纪60年代末期。由于当时计算机技术已经进入实用阶段，同时大型运动会用手工来计算既费时费力又非常容易出差错，为了解决这个矛盾，运动会管理系统应运而生。当时由于技术条件和需求的限制，用户非常少，而且那种系统充其量也只不过是一种自动计算工具，几乎没有报表生成功能和薪资数据分析功能。但是，它的出现为运动会管理的管理展示了美好的前景，即用计算机的高速度和自动化来替代手工的巨大工量，用计算机的高准确性来避免手工的错误和误差，使大规模集中处理大型运动会成为可能。

目前，计算机及网络技术在国内外举办的大型综合运动会和专项比赛已广泛使用，近几届奥运会，使用了上千台微机联网进行赛事管理；国内的重大比赛也都使用计算机管理，但绝大多数都是联机运行，仅进行文书处理工作和简单的成绩数据统计分析，多数是为某一次运动会而开发，通用性差，更无实时性。20世纪90年代前后，国内出现了一个运动会管理系统开发的热潮，从权威机构联机检索的材料上看，主要是单机版系统或是简单的网络系统，受当时计算机软硬件技术发展，以及当时网络、数据库水平的限制，应用层次低，实时性差。近两年国内发展较快，但还不能满足大型综合运动会的需要。运动会电子信息系统被称为大型综合运动会的"神经系统"。对于一个小型运动会管理系统来说，可以满足基本数据录入，数据处理从而得出合理的比赛安排顺序，打印各种报表等等即可，如学校运动会管理系统。