哈密尔顿回路-广西大学计算机与电子信息学院

《哈密尔顿回路-广西大学计算机与电子信息学院》由会员分享，可在线阅读，更多相关《哈密尔顿回路-广西大学计算机与电子信息学院（72页珍藏版）》请在金锄头文库上搜索。

1、第2章 计算学科中的科学问题,李陶深 ,2.1 概述,2.1 科学问题的定义,科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。(例如IPv4IPv6） 能否在所从事的工作中提出关键和重要的科学问题，对我们每个人来说都是一个挑战。,2.1 科学问题的主要特征,时代性：每一个时代都有它自己的科学问题 混沌性：渴望对新知识的追求，追求开始的时候是模糊不清的。 可解决性 可变异性：能引出另外具有可解决性的科学问题 可待解性：绝非永远不可解决。,2.1 科学问题的方法论作用,科学问题的裂变式作用

2、如对“数学基础问题”的研究，导致了“形式系统相容性问题”的研究， 最后出现“能行性问题”的研究， 最终于20世纪30年代由图灵、哥德尔、丘奇和波斯特等人共同奠定了计算学科的理论基础 实现了人类对计算认识问题的重大突破。,2.1 科学问题的方法论作用,科学问题的聚变式作用殊途同归 对不同科学问题的研究最终导致同一科学问题的发现 科学问题的激励作用 它召唤和激励着人们为解决这些富有挑战性的问题而勇往直前。 本章仅对反映计算学科本质的根本问题、学科各领域的基本问题、在学科中起重要作用的典型问题，以及人工智能中的若干哲学问题进行分析。,CH02 计算学科中的科学问题,计算的本质 计算学科的定义及其根本

3、问题,2.2 计算本质的认识历史,康托尔的集合论和罗素悖论,形式化方法和理论的研究起源于对数学的基础研究。 康托尔（G.Cantor，18451918）从1874年开始，对数学基础作了新的探讨，发表了一系列集合论方面的著作，从而创立了集合论。 “罗素悖论”，从而导致了数学发展史上的第三次危机。,希尔伯特纲领,希尔伯特（D.Hilbert）在数学基础的研究中提出了一个设想 将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性。 目标是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给

4、定命题的真伪。,库尔特哥德尔（KGodel）,认为数学原理所定义的系统既是一致的，也是完备的 任何系统的完备和一致性，可以由系统本身得到证明。 1931年，“希尔伯特纲领”被奥地利逻辑学家Godel搠出一个大窟窿 Godel认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。 推翻“希尔伯特纲领”，还直逼数学原理，说它本身就是不一致的。,希尔伯特纲领,“希尔伯特纲领”的研究基础是逻辑和代数，即布尔代数 Gdel提出的关于形式系统的“不完备性定理”中指出 这种形式系统是不存在的，从而宣告了著名的“希尔伯特纲领”的失败。 表明形式系统不能穷尽全部数学命题，任何形式系统中都存

5、在着该系统所不能判定其真伪的命题。,希尔伯特纲领的历史意义,“希尔伯特纲领”是在保存全部古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机 希尔伯特纲领的提出使元数学得到了确立和发展 希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。,图灵对计算本质的揭示,“哥德尔定理”的提出使整个逻辑和数学领空中阴云四布。 天才的图灵在数理逻辑大本营的剑桥大学提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能在原则上一个接一个地解决所有的数学问题。 图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对

6、计算本质的真正认识。 图灵用形式化方法成功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。,现代计算机的产生以及计算学科的定义,图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型，而现代计算机正是这种模型的具体实现。 计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。 来源于对算法理论、数理逻辑、计算模型、自动计算机器的研究，并与存储式电子计算机的发明一起形成于20世纪40年代初期。,计算学科

7、的根本问题,计算学科的根本问题是：什么能被（有效地）自动进行。 “能行性”这个计算学科的根本问题决定了计算机本身的结构和它处理的对象都是离散型的，甚至许多连续型的问题也必须在转化为离散型问题以后才能被计算机处理。例如，计算定积分就是把它变成离散量，再用分段求和的方法来处理的。 计算学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。,从计算的角度认知思维、视觉和生命过程,以1975年图灵奖共同获得者西蒙（H.A.Simon）和纽厄尔（A.Newell）为代表的符号主义者认为：认知是一种符号处理过程。他们还提出了人类思维过程也可用某种符号来描述的思想，即思维就是计算（认知就是计算）的

8、思想。除了思维、认知之外，有关视觉认知理论的学者也把视觉看作是一种计算。 1994年11月美国科学家L.M.Adleman在 Science 上发表了论文“Molecular Computation of Solutions to Combinatorial Problems” ，论证了DNA（脱氧核糖核酸）计算技术的可行性，并用DNA计算机解决了一个简单的有向哈密尔顿路径问题,2002年，阿德勒曼教授应用DNA计算机可以解决具有100万种可能结果的有向哈密尔顿路径问题，阿德勒曼的工作从一个侧面探讨了生命过程就是一种计算的思想。,CH02 计算学科中的科学问题,计算学科中的典型问题 及其相关内

9、容,哥尼斯堡七桥问题,17世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。 通过这7座桥到各城区游玩，问题：寻找走遍这7座桥的路径，要求过每座桥只许走一次，最后又回到原出发点。,问题的抽象,1736年，大数学家列昂纳德欧拉（L.Euler）发表了关于“哥尼斯堡七桥问题”的论文。 他抽象出问题最本质的东西，忽视问题非本质的东西（如桥的长度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题了。,欧拉回路,欧拉给出了哥尼斯堡七桥问题 的证明，还用数学方

10、法给出了三条判定规则： 如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。 如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。,哈密尔顿回路问题,问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。 “哈密尔顿回路问题”与“欧拉回路问题”的不同点 “哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。 对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。,图论

11、的形成和发展,欧拉的论文为图论的形成奠定了基础。 图论已广泛地应用于 计算学科 运筹学 信息论 控制论等学科 图论已成为我们对现实问题进行抽象的一个强有力的数学工具。 图论在计算学科中的作用越来越大，图论本身也得到了充分的发展。,梵天塔问题,将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔，天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，既将整个塔迁移，同时定下3条规则： 每次只能移动一个盘子； 盘子只能在三根柱子上来回移动，不能放在他处； 在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。,算法：C语言描述,ha

12、noi(int n,char left,char middle,char right) if(n=1) move(1,one,_,three); else hanoi(n-1,left,right,middle); move(1,left,_,right); hanoi(n-1,middle,left,right); ,当n=64时，移动次数=？花费时间=？,h(n)=2h(n-1)+1 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 = 2n-1+22+2+1=2n-1 需要移动盘子的次数为： 264-1

13、=18446744073709551615,假定每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。 假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。 理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。,算法复杂性中的难解性问题、P类问题和NP类问题,空间复杂性问题 关于梵天塔问题算法的时间复杂度， 用O(2n)来表示 当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。 一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长， 以

14、致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。,时间复杂性问题 人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。 在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定PNP。,证比求易算法,艾述国王向邻国秋碧贞楠公主求婚。公主出了一道题： 求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主

15、便接受他的求婚。 国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。,公主说：“我再给你一次机会” 国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位， 他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。,顺序算法和并行算法,国

16、王最先使用的是一种顺序算法，其复杂性表现在时间方面， 后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。 直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。 当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。,P？NP,P类问题存在多项式时间的算法的一类问题； NP类问题非多项式时间算法解的一类问题。像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题。 PNP？如果P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。 要证明PNP，目前还无法做到这一点 。,在P?NP问题上，库克（S.A.Cook）等人认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个