计算机科学导论论文.doc

1.七桥问题Seven Bridges Problem1.1问题背景 18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。 有关图论研究的热点问题。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。这就是柯尼斯堡七桥问题。L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。 当Euler在1736年访问Konigsberg, Prussia(now Kaliningrad Russia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Pregel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。 Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。 后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成. 欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。 接下来，欧拉运用网络中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！1.2成果 问题提出后，很多人对此很感兴趣，纷纷进行试验，但在相当长的时间里，始终未能解决。而利用普通数学知识，每座桥均走一次，那这七座桥所有的走法一共有5040种，而这么多情况，要一一试验，这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因而形成了著名的“哥尼斯堡七桥问题”。 1735年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉在亲自观察了哥尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？ 1736年，欧拉在交给彼得堡科学院的哥尼斯堡7座桥的论文报告中，阐述了他的解题方法。他的巧解，为后来的数学新分支拓扑学的建立奠定了基础。 七桥问题和欧拉定理。欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧拉图。 如果通奇数座桥的地方不只两个，满足要求的路线是找不到的。如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。 2.旅行商问题2.1简介 “旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法，近来在大型计算机的帮助下才取得了一些进展。 TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。2.2研究历史 旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。2.3问题解法 旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种： 2.3.1途程建构法（Tour Construction Procedures） 从距离矩阵中产生一个近似最佳解的途径，有以下几种解法： 1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。 2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。 3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。 2.3.2途程改善法（Tour Improvement Procedure） 先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法： 1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。 2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。 2.3.3合成启发法（Composite Procedure） 先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法： 1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。 2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。 3.NP完全性问题3.1基本简介 数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等于P，还是NP不等于P。证明其中之一，便可以拿百万美元大奖。 这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。NP里面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 美国麻州的克雷(Clay)数学研究所于2000年5月24日在巴黎法兰西学院宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元。以下是这七个难题。 “千僖难题”之一： P (多项式算法)问题对NP (非多项式算法)问题 “千僖难题”之二： 霍奇(Hodge)猜想 “千僖难题”之三： 庞加莱(Poincare)猜想 “千僖难题”之四： 黎曼(Riemann)假设 “千僖难题”之五： 杨米尔斯(Yang-Mills)存在性和质量缺口 “千僖难题”之六：纳维叶斯托克斯(Navier-Stokes)方程的存在性与光滑性 “千僖难题”之七：贝赫(Birch)和斯维讷通戴尔(Swinnerton-Dyer)猜想 NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。3.2问题详解 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。 这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。 完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。 人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。 解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。 前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。 说到可怜的旅行商想找出走遍所有城市的最短路径。让我们用计算机帮他搜索一下。 这就需要用到本篇文章中要介绍的第一门学科了：人工智能。人类的许多活动，如解算题、猜谜语、进行讨论、编制计划和编写计算机程序，甚至驾驶汽车和骑自行车等等，都需要智能。如果机器能够执行这种任务，就可以认为机器已具有某种性质的人工智能。现在我们就要利用人工智能，用计算机模拟人的思维来搜索最短路径。 想像一下，我们人思考问题时，有两种方法：一种是精确搜索，就是试验所有的可能性，找出最精确的一个方案。但它在搜索过程中不改变搜索策略，不利用搜索获得的中间信息，它盲目性大，效率差，用于小型问题还可以，用于大型问题根本不可能；另一种叫做启发式搜索，它在搜索过程中加入了与问题有关的启发性信息，用以指导搜索向着一个比较小的范围内进行，加速获得结果。 4.哲学家共餐问题4.1简介 哲学家共餐问题是计算机科学家狄杰斯特拉提出的，问题是这样描述的：5位哲学家围坐在一张圆桌旁，每个人的面前有一碗面条，碗的两旁各有一只筷子（狄杰斯特拉原来提到的是叉子，因有人习惯用一个叉子吃面条，于是改为中国筷子），如图1所示，假设哲学家的生活除了吃饭就是思考问题（这是 一种抽象，即对该问题而言其他活动都无关紧要），吃饭的时候需要左手拿一只筷子，右手拿一只筷子，然后开始进餐。吃完后将两只筷子放回原处，继续思考问题。那么。哲学家的生活进程可表示为： 思考问题； 俄了停止思考，左手拿起一只筷子（如果左侧哲学家已持有它，则等待）； 右手拿起一只筷子（如果右侧哲学家已持有它，则等待）； 进餐； 放下左手筷子； 放下右手筷子； 重新回到状态思考问题。4.2进程同步 现在的问题是：如何协调5位哲学家的生活进程，使得每一位哲学家最终都可以进餐。考虑下面两种情况： 按哲学家的生活进程，当所有的哲学家都同时拿起左手筷子时，则所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐