计算机科学导论.pdf

《计算机科学导论.pdf》由会员分享，可在线阅读，更多相关《计算机科学导论.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第 17 页 计算机科学导论 1、1.七桥问题 SevenBridgesProblem1.1 问题背景 18 世纪出名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块动身，恰好通过每座桥一次，再回到起点？欧拉于 1736 年争辩并解决了此问题，他把问题归结为如下右图的“一笔画问题，证明上述走法是不行能的。有关图论争辩的热点问题。18 世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有 7 座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。这就是柯尼斯堡七桥问题。

2、L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们 2、的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成推断连通网络能否一笔画的问题。他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为 0 或 2。当Euler 在 1736 年访问 Konigsberg,Prussia(nowKaliningradRussia)时，他觉察当地的市民正从事一项特殊好玩的消遣活动。Konigsberg城中有一条名叫Pregel的河流横经其中，这项好玩的消遣活动是在星期六作一次走过全部七座桥的闲逛 ，每座桥只能经过一次而且起点与终点必需是同一地点。

3、Euler 把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。后来推论出此 3、种走法是不行能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地或点时，他或她同时也由另一座桥离开此点。所以每行经一点时，计算两座桥或线，从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成.欧拉的这个考虑特殊重要，也特殊奇异，它正说明白数学家处理实际问题的独特之处把一个实际问题抽象成适宜的“数学模型。这种争辩方法就是“数学模型方法。这并不需要运用多么浅显的理论，但想到这一点，却是解决难题的关键

4、。接下来，欧拉运用网络中的一笔画定理为推断准那么，很快地就推断出 4、要一次不重复走遍哥尼斯堡的 7 座桥是不行能的。也就是说，多少年来，人们费脑费劲查找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！1.2 成果问题提出后，很多人对此很感爱好，纷纷进展试验，但在相当长的时间里，始终未能解决。而利用一般数学学问，每座桥均走一次，那这七座桥全部的走法一共有 5040 种，而这么多状况，要一一试验，这将会是很大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？因此形成了出名的“哥尼斯堡七桥问题。1735 年，有几名高校生写信给当时正在俄罗斯的彼得斯堡

5、科学院任职的天才数学家欧拉，请他挂念解决这一问题。欧拉在亲自观看了哥尼斯堡七桥后 5、，认真思考走法，但始终没能成功，于是他疑心七桥问题是不是原来就无解呢？1736 年，欧拉在交给彼得堡科学院的?哥尼斯堡 7 座桥?的论文报告中，阐述了他的解题方法。他的巧解，为后来的数学新分支拓扑学的建立奠定了根底。七桥问题和欧拉定理。欧拉通过对七桥问题的争辩，不仅圆满地答复了哥尼斯堡居民提出的问题，而且得到并证明白更为广泛的有关一笔画的三条结论，人们通常称之为欧拉定理。对于一个连通图，通常把从某结点动身一笔画成所经过的路线叫做欧拉路。人们又通常把一笔画成回到动身点的欧拉路叫做欧拉回路。具有欧拉回路的图叫做欧

6、拉图。假设通奇数座桥的地方不只两个，满足要求 第 18 页 的路线是找不到的。假设只有两个地方通 6、奇数座桥，可以从这两个地方之一动身，找到所要求的路线。假设没有一个地方是通奇数座桥的，那么无论从哪里动身，所要求的路线都能实现。2.旅行商问题 2.1 简介“旅行商问题常被称为“旅行推销员问题，是指一名推销员要拜见多个地点时，如何找到在拜见每个地点一次后再回到起点的最短路径。规那么虽然简洁，但在地点数目增多后求解却极为冗杂。以个地点为例，假设要列举全部路径后再确定最正确行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法，近来在大型计算机的关怀下才取得了

7、一些进展。TSP 问题在物流中的描述是对应一个物流配送公司，欲将 n 个客户的订货沿最短路线全部送到。如何 7、确定最短路线。TSP 问题最简洁的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的冗杂解的空间，搜寻空间是 n 个点的全部排列的集合，大小为n-1。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解 TSP，那么是在此不能穷尽的丘陵地带中攀登以到达山顶或谷底的过程。2.2 研争辩究历历史史旅行商问题字面上的理解是：有一个推销员，要到 n 个城市推销商品，他要找出一个包含全部 n 个城市的具有最短路程的环路。TSP 的历史很久，最早的描述是

8、 1759 年欧拉争辩的骑士周游问题，即对于国际象棋棋盘中的 64 个方格，走访 64 个方格一次且仅一次，并且最终返回到起始点。TSP 由美国 8、RAND 公司于 1948 年引入，该公司的声誉以及线性规划这一新方法的消灭使得 TSP 成为一个知名且流行的问题。2.3 问问题题解解法法旅行推销员的问题，我们称之为巡行Tour，此种问题属于 NP-Complete 的问题，所以旅行商问题大多集中在启发式解法。Bodin1983等人将旅行推销员问题的启发式解法分成三种：2.3.1 途程建构法TourConstructionProcedures从距离矩阵中产生一个近似最正确解的途径，有以下几种解

9、法：1最近邻点法NearestNeighborProcedure：一开场以查找离场站最近的需求点为起始路线的第一个顾客，此后查找离最终参与路线的顾客最近 9、的需求点，直到最终。2节省法ClarkandWrightSaving：以效劳每一个节点为起始解，依据三角不等式两边之和大于第三边之性质，其起始状况为每效劳一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最终。3插入法Insertionprocedures：如最近插入法、最省插入法、任凭插入法、最远插入法、最大角度插入法等。2.3.2 途程改善法TourImprovementProcedure先给定一个可

10、行途程，然后进展改善，始终到不能改善为止。有以下几种解法：1K-Opt(2/3Opt)：把尚未参与路径的 K 条节线临时取代目前路径中 K 条节线，并 10、计算其本钱或距离，假设本钱降低距离削减，那么取代之，直到无法改善为止，K 通常为 2 或 3。2Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其本钱或距离，假设本钱降低距离削减，那么取代之，直到无法改善为止。2.3.3 合成启发法CompositeProcedure先由途程建构法产生起始途程，然后再使用处程改善法去寻求最正确解，又称为两段解法twophasemethod。有以下几种解法：1起始解

11、求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。2起始解求解+3-Opt：以途程建构法建立一个起 11、始的解，再用 3-Opt 的方式改善途程，直到不能改善为止。3.NP 完完全 第 19 页 全性性问问题题 3.1 基根本本简简介介数学上出名的 NP 问题，完好的叫法是 NP完全问题，也即“NPCOMPLETE问题，简洁的写法，是 NP=P？的问题。问题就在这个问号上，到底是 NP 等于 P，还是 NP 不等于 P。证明其中之一，便可以拿百万美元大奖。这个奖还没有人拿到，也就是说，NP 问题到底是 Polynomial，还是 Non-Poly

12、nomial，尚无定论。NP 里面的 N，不是 Non-Polynomial 的 N，是Non-Deterministic，P 代表 Polynomial 倒是对的。NP 就是Non-deterministicPolyn 12、omial 的问题，也即是多项式冗杂程度的非确定性问题。美国麻州的克雷(Clay)数学争辩所于 2000 年 5 月 24 日在巴黎法兰西学院宣布了一件被媒体炒得酷热的大事：对七个“千僖年数学难题的每一个悬赏一百万美元。以下是这七个难题。“千僖难题之一：P(多项式算法)问题对 NP(非多项式算法)问题“千僖难题之二：霍奇(Hodge)猜想“千僖难题之三：庞加莱(Poin

13、care)猜想“千僖难题之四：黎曼(Riemann)假设“千僖难题之五：杨米尔斯(Yang-Mills)存在性和质量缺口“千僖难题之六：纳维叶斯托克斯(Navier-Stokes)方程的存在性与光滑性“千僖难题之七：贝赫(B 13、irch)和斯维讷通戴尔(Swinnerton-Dyer)猜想 NP 完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。3.2 问题详解 NP 就是Non-deterministicPolynomial 的问题，也即是多项式冗杂程度的非确定性问题。什么是非确定性问题呢？有些计算问题是确定性的，比方加减乘除之类，你只要依据公式推导，按部就班一步步来，就可以得

14、到结果。但是，有些问题是无法按部就班直接地计算出来。比方，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应当是多少呢？这样的公式是没有的。再比方，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以 14、算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告知你答案是什么，但可以告知你，某个可能的结果是正确的答案还是错误的。这个可以告知你“猜算的答案正确与否的算法，假设可以在多项式时间内算出来，就叫做多项式非确定性问题。而假设这个

15、问题的全部可能答案，都是可以在多项式时间内进展正确与否的验算的话，就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的冗杂程度，是指数关系，因此计算的时间随问题的冗杂程度成指数的增 15、长，很快便变得不行计算了。人们觉察，全部的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的规律运算问题。既然这类问题的全部可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是出名的 NP=P？的猜想。解决这个猜想，无非两种可能，一种是找到一个这样的

16、算法，只要针对某个特定 NP 完全问题找到一个算法，全部这类问题都可以迎刃而解了，由于他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以 16、在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。说到可怜的旅行商想找 第 20 页 出走遍全部城市的最短路径。让我们用计算机帮他搜寻一下。这就需要用到本篇文章中要介绍的第一门学科了：?人工智能?。

17、人类的很多活动，如解算题、猜谜语、进展商量、编制打算和编写计算机程序，甚至驾驶汽车和骑自行车等等，都需要“智能“。假设机器能够执行这种任务，就可以认为机器已具有某种性质的“人工智能“。如今我们就要利用人工智能，用计算机模拟人的思维来搜寻最短路径。想像一下，我们人思考问题时，有两种方法 17、：一种是精确 搜寻，就是试验全部的可能性，找出最精确 的一个方案。但它在搜寻过程中不转变搜寻策略，不利用搜寻获得的中间信息，它盲目性大，效率差，用于小型问题还可以，用于大型问题根本不行能；另一种叫做启发式搜寻，它在搜寻过程中参与了与问题有关的启发性信息，用以指导搜寻向着一个比较小的范围内进展，加速获得结果。

18、4.哲哲学学家家共共餐餐问问题题 4.1 简简介介哲学家共餐问题是计算机科学家狄杰斯特拉提出的，问题是这样描述的：5 位哲学家围坐在一张圆桌旁，每个人的面前有一碗面条，碗的两旁各有一只筷子狄杰斯特拉原来提到的是叉子，因有人习惯用一个叉子吃面条，于是改为中国筷子，如图 1 所示，假设哲学家的生活除了吃饭 18、就是思考问题这是一种抽象，即对该问题而言其他活动都无关紧要，吃饭的时候需要左手拿一只筷子，右手拿一只筷子，然后开场进餐。吃完后将两只筷子放回原处，连续思考问题。那么。哲学家的生活进程可表示为：思考问题；俄了停顿思考，左手拿起一只筷子假设左侧哲学家已持有它，那么等待；右手拿起一只筷子假设右侧

19、哲学家已持有它，那么等待；进餐；放下左手筷子；放下右手筷子；重新回到状态思考问题。4.2 进进程程同同步步如今的问题是：如何协调 5 位哲学家的生活进程，使得每一位哲学家最终都可以进餐。考虑下面两种状况：按哲学家的生活进程，当全部的哲学家都同时拿起左手筷子时，那么全部哲学家都将拿不到右手筷子 19、，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，全部的哲学家都同时拿起左手筷子，那么自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下去，那么全部的哲学家都将无法进餐。以上两个问题反映的是程序并发执行时进程同步的两个关键问题：死锁和饥饿。为了提高系统的处理力量和机器的利用率，并发程序被广泛地使用，因此，必需彻底解决并发程序执行中的死锁和饥饿问题。于是，哲学家问题推广为更一般性的 n 个进程和 m 个共享资源的问题，并在争辩过程中给出了解决这类问题的不少方法和工具，如 Petri 网、并发程 20、序设计语言等。