从哈密尔顿图到旅行货郎问题
http://www.newdu.com 2024/12/04 03:12:21 人民教育出版社 佚名 参加讨论
从哈密尔顿图到旅行货郎问题 1979年11月7日《纽约时报》出现一篇引人注目的文章，它的标题是：《苏联的发现震动数学界》（Soviet Discovery Rocks World of Mathematics），这文章介绍一个本是默默无闻的年青数学家卡倩（L．G．Khachian），他在线性规划理论上的一个发现使到美国数学界为之轰动。由于记者在询问一些著名数学家时对数学问题了解不深，文章报导是有一些失实，但由这文章引起的轰动及误导是相当严重。我以后会讨论这问题。该文中说：“俄国人的发现建议用电子计算机处理一类和‘旅行货郎问题’（Travelling Salesman Problem）有关的数学上一个著名及难处理的问题。‘旅行货朗问题’目的是决定一个货郎（或推销员或销货员）所要跑的最短路程──他要走遍市镇，但是不能再回到走过的地方。表面上，这问题看来简单，事实上为了要解决这问题的实际应用，人们需要电子计算机来解决。” 在这点上这记者是说对了。“旅行货郎问题”目前是许多国家（如西德、日本、苏联、英国、美国、法国）的运筹学工作者研究的热烈课题。为了要了解这问题，我们可要知道目前在图论（Graph Theory）上许多人正在研究一种图──哈密尔顿图（Hemilton graphs）。 一、哈密尔顿图的由来 在17—18世纪时，欧洲宫庭及一些贵族很喜欢玩西洋象棋，西洋象棋中的骑士（knight）是对应我们中国象棋的“马”，而它通常是刻成一个马头，跑法也是和中国象棋的“马”一样，走“日”线──即从日的一角沿着对角线跃到另一角。 在1771年，就有一位名叫范德蒙（A．Vandermonde）的法国数学家，写了一篇文章研究所谓“棋盘的骑士问题”。这问题是这样：在8×8的棋盘格的随意一个位置，我放一个骑士，然后我想法子使他跑遍棋盘的所有的格子，走过的不许再走，我能不能使骑士最后回到原来的位置？ 这个问题并不简单，许多象棋爱好者及数学家曾坐下来研究这个问题。我这里列出一个情形的解（见图一），我将棋盘的左下角的格选为起始位置，把它定为1，读者可以验证根据图一的跑法，骑士最后是能跑回1的。
图一 “棋盘骑士问题”的一个解法 18世纪的大数学家欧拉（Euler），在1759年就系统地研究过这个问题，也得到了一些结果。以后德国数学家高斯也曾对这问题发生兴趣，花过一些时间研究它及另外一个棋盘的“皇后问题”。 我们现在把棋盘上的格子对应在一个平面上的一个小圆点，这样我们在平面上就有64个小圆点。从一个格子用骑士的走法我们可以抵达不同数目的格子：如果是处在棋盘的四个角，只能有两种跑法；在其他边缘的格子就有三种跑法；一般当中的格子，就有四种可能的跑法。我们把平面上的点用弧线连接，两个点有一条弧线连起当且仅当（if and only if）我们可以从它们所对应的格子将骑士移动。我们得到了一个图（ graph）。 在图中取一个顶点v0，如果我们有一个弧线把它和另外一个点v1联起来，我们就用（v0，v1）来表示这个弧线。假定我有一系列点v0，v1，v2，…，vn其中没有两个相同以及一序列的弧线存在（v0，v1），（v1，v2），…，（vn-1，vn），（vn，v0），使到我从v0出发可以经过v1，v2，…，vn最后由vn回到v0，我就说这些弧线组成一个回路（circuit），为了方便，我们用下面的记号表示这回路：（v0，v1，v2，…，vn，v0）。 如果我有一个图G有n+1个顶点（vertices）{v0，v1，v2，…，vn}，而我能找到一个回路（v0，v1，v2，…，vn，v0），那么我就说这个图是哈密尔顿图（Hamilton graph），这个回路称为哈密尔顿回路（Hamilton circuit）。 因此，“棋盘的骑士问题”实际上就是要判断它所对应的图是否是哈密尔顿图的问题。 为什么叫哈密尔顿图？哈密尔顿是谁呢？ 哈密尔顿是爱尔兰的一位数学家和天文学家。他的一生是多姿多彩的，我在《数学和数学家的故事》第一集里有详细介绍他的工作和生平，读者可以找来一读。 自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“The Icosian Calculus”的代数系统，这系统有加和乘的运算子（operators），可是乘法不满足交换律（Commutative law即xy=yx这个规律）。 他发现这代数系统是和正则20面体（regularicosion polybedron）有关系。他想到一个游戏，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。在1857年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。这25英镑在124年前是很好用，在今天拿去伦敦的“唐人区”买“牛腩面”吃可能连十碗都吃不到。 这玩具商把这游戏制造出来了（见图二），在圆盘上有20个代表城市的圆孔，你必须把20个上面标有1，2，3，…，20的木条顺序插进去，代表你经过不同的城市，最后回到原出发点。这个游戏叫“环游世界”，很可惜玩具商人没有从这游戏上赚到钱。 以后人们因这游戏就称这类图为哈密尔顿图。 THE ICOSIAN GAME  二、怎么样的图是哈密尔顿图 给你一个图，你怎么知道它是否是哈密尔顿图呢？当然如果图的顶点不多，你可以试试找哈密尔顿回路就可以解决和判断。你用的是最古老的“尝试和错误”的方法，但是数学家并不满意这样的碰得焦头烂额后才找到真理的方法。是否存在一组必要和充分的条件，使到我们能简单轻易地判断一个图是否哈密尔顿图？许多聪明人去试过了，很可惜到现在这问题还未解决，因此读者可以试试自己来找寻一下。 英国数学家G．A．狄拉克（Dirac）在1952年给出一个充分条件使得一个图会是哈密尔顿图。他的定理是只要检查每一个顶点x，看它的上面有多少个弧通过，把这个数目用d（x）来表示，只要每一个点的d（x）是相当大的话，这图就会是哈密尔顿图。 狄拉克定理 给定一个图G，如果其顶点集V的元素数是n≥3，  由于我们可以看到以下的两个图G1，G2都是哈密尔顿图（见图三）。   到了1960年，美国著名的图论专家奥斯坦·奥勒（ Oystein Ore）推广狄拉克的工作，得到以下的结果。 奥勒定理 给定一个图G，如果其顶点集V是有n≥3点，而对于任意两点x，y我们有d（x）+d（y）≥n，那么G一定是哈密尔顿图。 在1962年，匈牙利有一个少年发表了一篇只有一页长的论文，他的结果却是推广了以上奥勒的定理，他的工作是这么重要引起许多人谈论，并且在图论的教科书上登他的证明。以后几年来许多人想要改进这工作，最后才由一个捷克青年数学家得到比他更好的结果。 这个少年名叫博萨（Posa），我在《数学和数学家的故事》第一集的一篇文章就有介绍他的事迹，读者想要知道他的故事可以看看该文。 为了能更容易看清博萨的结果，我这里引进几个记号：对于每一个图G，我们用d（G）来表示序列如（d（x1），d（x2），…，d（xn）），这里x1，…，xn是G的所有顶点，而序列的数是从小排到大去排列。比方说在图三里我们有 d（G1）=（3，3，3，3） d（G2）=（4，4，4，4，4，4） 假定我们有两个序列具有相同个数的数字： X=（x1，x2，x3，…xn）； Y=（y1，y2，y3，…，yn） 我们用X≤Y表示当且仅当对于每个i=1，2，…，n，我们都有xi≤yi。 比方说，X=（1，2，3，4，5），Y=（2，3，5，7，9），Z=（4，2，1，3，5），我们就有X≤Y，而X≤Z是不对的。 现在对于每个n≥3的整数，我们定义这样的整数序列P（n） （1）如果n是偶数，我们有n个数照底下由小到大的排法：   （2）如果n是奇数，我们有n个数照底下的由小到大的排法：   根据定义我们有 P（3）=（1，2，2）， P（4）=（2，2，2，2）， P（5）=（2，2，3，3，3）， P（6）=（2，3，3，3，3，3）以及 P（7）=（2，3，3，4，4，4，4） 〔读者请注意我们是怎样定义这序列〕 现在我们可以叙述博萨的重要发现： 博萨定理 如果一个有n≥3个顶点的图，它的d（G）满足不等式d（G）≥P（n），那么G是哈密尔顿图。 让我们看以下的图四（a）及（b），读者很容易地看出  d（G5）=（2，2，3，3，4）， d（G4）=（3，3，3，3，3，3，3，3）。 它们都是哈密尔顿图。G3不满足奥勒的条件，因为d（x）+d（y）=2+2=4 并不大过5。 可是我们却看到d（G3）=（2，2，3，3，4）≥（2，2，3，3，3）=P（5） 因此由博萨定理知道它是哈密尔顿图。由这个例子说明了博萨的结果是比奥勒的强。然而我们却由G4看到它并不满足博萨的不等式。因此人们尝试想找比博萨更好的不等式以判别更多的哈密尔顿图。 到目前来说，比较好的工作是捷克青年数学家萨瓦达（V. Chvátal）在1972年的发现，他的结果如下： 萨瓦达定理 如果图G的顶点数n是大过2，而其d（G）=（a1，a2，…，an）满足底下的条件：  ai≥i+1，an-i≥n-i最少有一个成立，那么G一定是哈密尔顿图。对数学有兴趣的读者可以试证明博萨的结果是包含在萨瓦达定理。我们的G4图显示它不满足萨瓦达的条件，因此我们相信会存在比萨瓦达还要好的条件，这个问题就留给读者自己去寻找。 三、旅行货郎问题 如果我现在有一个图G，而这图的每一条弧上都算上一个数字，我要怎样才能找到这图的哈密顿回路具有所有的弧上数字的和是最小值的性质，这个问题就是数学上大名鼎鼎的难题：“旅行货郎问题”。 这问题在1932年由德国著名数学家K．Menger提出，这29年来是许多人废寝忘食研究的对象。 我们在日常生活中就会遇到这问题，比方说： （1）你是学校校车的司机，你从学校开车出来，到不同的街道去接孩子，你要怎样安排使走的路程最短，可以接到所有的孩子回到学校去？ （2）春假到了，你想驾车在北美几个城市旅行，可是现在汽油是这么昂贵，你想要尽量省用油，汽油的消耗是和路程成正比，因此你想法子找一个回路具有最短的路程。 （3）你为了商业业务，需要乘飞机飞几个城市，不同的飞机公司提供不同的票价，你要怎样安排行程，使到你能走遍你要去的城市，最后又回来原出发地，而又能省钱？ “旅行货郎问题”是这么容易明白，可是要找出一个行之有效及能迅速提供解答的方法，目前并不存在。在28年前，美国的《管理科学》（Management Science 1963）一篇讨论“旅行货郎问题”的文章就说道：“人类由于他的运算能力的限制在解决旅行货郎问题上并不好。”人们现在对于这问题的实际情形都是借助高速的电子计算机来运算。 我在以下会介绍一种直观而又容易明白的树的搜索法来寻找最优解，目前解“旅行货郎问题”有很多种方法，由于大部分要牵涉到较深的数学知识，因此我不在这里介绍。我最后会通过例子说明为什么这个看来小学生都能明白的问题却是数学难题。 德国人很喜欢精确的数学，在1978年，波恩大学有一位数学家想要知道在西德的120个有铁路穿过的城市要安排一个最短路程的回路，应该怎么样跑。他从铁路局找到了准确的城市间铁路的长度，整个问题变成一个有7140个变数，120个方程及96个不等式的线性规划问题，用电子计算机去算得到最短的回路是6942公里。（见图五）。  四、树的搜索法 我这里举一个例子说明这个方法，假定我现在有四个城市A，B，C，D，它们之间的路程是由下面的表给出（见图六）：  我要找从A出发回到A的最短回路。 我从A出发，我写：（A）0。0是表示最初没有出发路线长是0，然后我列下所有可能的下一个站：B，C，D，然后我得到三个节点（node）：（AB）1，（AC）3，（AD）2。 这时我就把（A）0划掉，然后找节点具有最小的数值，这里是（AB）1。从B我可以走的站是C和D，我就划掉（AB）1，用（ABC）1+4及（ABD）1+7来取代。为什么（ABC）旁的数字是1+4呢？因为它是（AB）加上（BC）的长。（见图七）。   我们把没划掉的节点中有最小长度的找出，这是（AD）2D的下一个可能的站是B和C，因此我们划掉（AD）2补上两个节点（ADB）2+7及（ADC）2+5。 我们继续找具有最小长度的节点，这时看到是（AC）3从C出发可以到达B或D，于是我们划掉（AC）3，补上（ACB）3+4，（ACD）3+5。（见图七（e）） 我们再搜索有最小长度的节点，看到是（ABC）5，于是划掉它，补上（ABCD）5+5，得图七（f）。 我们再搜索没有被划的节点，看到有最小长度的是（ACB）7及（ADC）7，我就先划掉（ACB）7补上（ACBD）7+7，得图七（g）。 然后我再划掉（ADC）7补上（ADCB）7+4得图七（h）。 这时候我看剩下没划线的最小长度的节点是：（ABD）8及（ACD）8，我划掉了比方说（ABD）8，补上（ABDC）8+5。 我再寻找最小长度的节点得（ACB）8，划掉之后补上了（ACDB）8+7，得图七（j）。 现在变成（ADB）9是最小长度的节点，我们划掉补上（ADBC）9+4，得图七（k），我们划去（k）的最小长度节点（ABCD）10，补上（ABCDA）10+2。我们已得到一个回路了，这时我们把（1）图中所有长度大过12，节点全划掉，因为这些节点所产生的回路肯定要大过12，我们可以不考虑，我们只剩下（ADCB）11，划掉它之后补上（ADCBA）11+1，我们得（k）。 谢天谢地，到此时我们再没有什么节点可以划了，我们得到两个回路（ABCDA）及（ADCBA），它们的长都是12。这种方法在数学上有一个名称叫 uniformcost Search。为了说明整个搜索的程序，我画了许多像树枝分叉的图，实际上读者只需在一个图上划线及向下发展不必画这么多树。通常哈密尔顿回路找到之后，我们选取最少的长度，那就是我们所要的答案。 五、为什么数学家和电脑专家对货郎问题发生兴趣 我们前面介绍的方法在城市数目字比方说不超过十个还不显得可怕。如果现在有21个城市用以上的方法去搜索最短的回路，我们最少要找超过九十万个以上的路线，这是多么巨大的数字呀！ 现在请想一想，如果我们要处理的是五百个城市，或者一千个城市，或者就拿像中国这么大的国家，这么多的县城，要处理这问题，用目前最快速的电子计算机来协助，也会使电子计算机挂投降的白旗，宣称：“我的记忆不够处理这些问题产生出来的数值，对不起哥哥，我不能替你效劳。” 我前面介绍的树的搜索法是一个比较简单但并不是太好的方法，这20年来，许多人想出一些方法想要改进，希望能找到一个较理想的方法，可以快速的找到结果。目前来说这样理想的方法还没有找到。 什么样的方法算是理想呢？我们这里给一个粗略的解释：比方说我们要用电子计算机来帮我们工作，例如处理n个城市的旅行货郎问题，当我把n个城市的距离表喂给电子计算机之后，它就会一步一步的去找。如果它要得到答案，所要花费的步骤数目是可以用n的函数f（n）来表示。我们说这方法是“理想”，当f（n）是一个n的多项式。 目前我们的方法都不是理想的。如果你真能找到一个理想的方法，你的成果会轰动全世界。你的方法可以转化用来解决许多数学的难题及电子计算机理论的一些著名难题。 旅行货郎问题是许多国家的运筹学研究中心的工作者深入研究的问题。在美国的华籍数学工作者在这方面有很好的结果的有 Lin Shen及Hong Saman等人。在1977年Hong先生和Padberg 合作用电子计算机处理有318个城市的“旅行货郎问题”，这个问题化成线性规划问题就要处理有50403个变数（variables）的方程式，及不等式，如果不借助电子计算机的快速计算，我想就是请一位能笔算及心算很快的数学家，让他穷十年的时间也是不能解决。以上的问题他们用IBM 370-168式的电子计算机，只花28.38分钟就得到一个最优解。 “玩物丧志”，这是以前老一辈的人骂儿童或少年不读书只喜欢游戏所爱用的一句话。其实游戏和玩具可以引导大发现。如果有青少年肯对哈密尔顿图及旅行货郎问题下点苦功研究，我会说他们是“玩物立志”，很可能以后会出一些在这些问题上作出大贡献的中国人。 六、动脑筋想想看： 1．寻找下面几个图的哈密尔顿回路：  2．在下面的3×3方格里，如果我在最左上角放一只马，然后让马依以下的数值跑（中国象棋的马跑日的跑法）最后会有一个空位不能跑，但它能走回原来出发的位置。  试证明除了中间的方格不许放马外，任何其它方格放马出去它最后又能跑回原先出发的位置──我们要求跑过的位置不能再回去。 3．对于4×4及5×5的方格，你研究在什么样的位置放马可以无重复的跑遍全部的方格。研究在什么情况下有多过一组的解答。你可以把找到的解答寄来编辑部。 4．给出任何两个正整数m、n，我们可以构造一个特别的图： X=｛x1，x2，…，xm｝， Y=｛y1，y2，…，yn｝， 任何在X里的x要和在Y里的每一个y用弧联结；而任何在Y里的y也要和每一个在X里的x相连，X之间的点及Y之间的点不要连结。证明只有当m=n时我们才能找到哈密尔顿回路。 5．下面的图不可能存在哈密尔顿回路（见图九）：  (责任编辑：admin) |