搜索
第4章问题求解与计算思维主讲教师：郑立垠计算机与通信工程学院计算机应用技术系中国自古就有喝茶的历史习俗，有同学知道泡茶的流程吗？烧水→温具→置茶→冲泡→奉茶→赏茶→续水引入有一个牧羊人带着一只羊,一匹狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？过河的方案:第一步：人和羊过河，人返回，留下羊；第二步：人和狼过河，人和羊返回，留下狼；第三步：人和菜过河，人返回，留下菜；第四步：人和羊过河。人在解决问题时，要先对问题进行分析思考，然后确定解决问题的方法和步骤，这种解决问题的方法和步骤就称为算法。引入1、算法2、计算思维本章内容算法的由来算法算法被誉为计算学科和计算机器的灵魂“算法”（Algorithm）一词源于：公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的《波斯教科书》（PersianTextbook），书中概括了进行四则算术运算的法则。算法的定义：一个有穷规则的集合，规则规定了一个解决某一特定类型问题的运算序列。定义了任务执行/问题求解的一系列步骤。算法的特征：输入：有零个或多个的输入。输出：有一个或多个的输出。有穷性：一个算法在执行有穷步之后必须结束。确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。可行性：算法原则上能够精确地运行。算法的定义及特征算法描述自然语言容易引起歧义，造成误解；对较复杂的问题，难以表达准确流程图直观形象，但计算机不能识别和执行程序代码用计算机能理解和执行的程序设计语言把算法表示出来，然后由计算机按照预定的算法去解决问题。算法设计数学建模数据结构控制流程算法策略遍历搜索递归动态规划贪心…….算法设计算法的正确性：问题求解的过程、方法——算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？两种方法：分析方法：利用数学方法证明仿真分析方法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析算法分析算法的效率：时间效率和空间效率时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。“大O记法”：基本参数n——问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“≈”，如n2+n+1=Ο(n2)算法的空间复杂度：算法在执行过程中所占存储空间的大小。算法效率算法的复杂性当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，计算机对于大规模问题可以处理算法的时间复杂度用一个指数函数表示，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题称为难解性问题。算法效率当n值增大时，各种时间复杂度存在下列关系：O(log2n)O(n)O(nlog2n)O(n2)…O(2n)O(n!)旅行商问题（TravelingSalesmanProblem）威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。城市之间的距离AnoptimalTSPtourthroughGermany’s15largestcities.Itistheshortestamong43589145600possibletoursvisitingeachcityexactlyonce.旅行商问题TSP是最有代表性的优化组合问题之一，在半导体制造、物流运输等行业有着广泛的应用TSP难于求解：2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。算法类问题算法类问题数学建模TSP问题数学建模与数学模型TSP问题模型数据结构求解TSP问题的数据结构控制结构算法的控制结构：顺序，分支，循环求解TSP问题的逻辑过程控制算法设计算法设计：动态规划，分治等TSP问题贪心算法程序设计语言及算法实现程序设计语言TSP贪心算法程序（C语言）算法的模拟与分析算法设计与分析TSP贪心算法分析算法的复杂性计算理论与计算复杂性TSP贪心算法复杂性问题求解的过程及思维方法Specific|one具体过程|具体方法General抽象过程方法与知识Many一般方法抽象具体数据结构：向量，二维数组等建立数学模型是求解算法类问题的第一步数学模型：数学模型就是为了某种目的，根据对研究对象所观察到的现象及其实践经验，用字母、数学及其它数学符号建立起来的等式或不等式以及图表、图象、框图等归结成的一套反映对象某些主要数量关系的数学公式、逻辑准则和具体算法，用来描述客观事物的特征，其内在联系和运动规律。旅行商问题数学模型及求解思想TSP问题的数学模型数学模型及求解方法求解方法：遍历搜索分治动态规划……TSP问题的求解方法遍历：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线组合爆炸路径组合数目：(n-1)!20个城市，总数1.216×1017，计算机以每秒检索1000万条路线，需386年所有路径组合及其长度城市之间的距离旅行商问题问题求解中的数据组织及操纵问题求解过程中需要组织及操作数据TSP问题求解中的数据操纵问题求解TSP问题需要组织和操纵的对象——数据输入：城市之间的距离关系输出：访问城市的路径中间结果：路径的距离之和.......旅行商问题数据结构数据结构提供了问题求解/算法的数据操纵机制数据结构：逻辑结构：数据之间的关系存储结构：在反映数据逻辑关系的原则下，数据在存储器中的存储方式，有顺序存储结构和链式存储结构。基本运算：(1)建立数据结构；(2)清除数据结构；(3)插入数据元素；(4)删除数据元素；(5)更新数据元素；(6)查找数据元素；(7)按序重新排列；(8)判定某个数据结构是否为空，或是否已达到最大允许的容量；(9)统计数据元素的个数等。旅行商问题数据结构基本数据结构：变量向量/列表矩阵/表向量实例11252225453984421280100348375161234123行列M[2,3]表实例4旅行商问题TSP问题求解的数据结构城市间距离关系表D访问路径/解一维数组S路径距离之和整数变量sum循环计数器i,j,k…{A-D-C-B-A}1432示例旅行商问题城市之间的距离问题求解中的过程控制问题求解过程中需要组织并控制操作、指令的过程和顺序TSP问题求解的流程控制求解TSP问题需要控制指令、基本操作的逻辑过程/流程遍历所有的组合路径判断某条路径的距离是不是比另外一条短，并据此作出不同的处理累加一条路径的距离之和……旅行商问题算法策略可行解与最优解遍历能够获得最优解，然而，由于组合爆炸，对于较大规模的某些问题，无法在可接受的时间内获得最优解退而求其次，在可接受的时间内获得足够好的（可行）解可行解最优解TSP问题的可行解与最优解旅行商问题算法策略——贪心贪心算法“今朝有酒今朝醉”一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”TSP问题的贪心求解示例每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短AABABCABCDABCDA026813(a)(b)(c)(d)(e)城市之间的距离旅行商问题TSP问题贪心算法的模拟与分析TSP问题贪心算法的正确性：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题实例TSP问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。旅行商问题TSP问题算法的效率TSP问题遍历算法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线组合爆炸：路径组合数目为(n-1)!时间复杂度是O((n-1)!)计算机不能处理TSP问题贪心算法：时间复杂度是O(n3)。计算机可以处理旅行商问题算法类问题算法类问题数学建模TSP问题数学建模与数学模型TSP问题模型数据结构求解TSP问题的数据结构控制结构算法的控制结构：顺序，分支，循环求解TSP问题的逻辑过程控制算法设计算法设计：动态规划，分治等TSP问题贪心算法程序设计语言及算法实现程序设计语言TSP贪心算法程序（C语言）算法的模拟与分析算法设计与分析TSP贪心算法分析算法的复杂性计算理论与计算复杂性TSP贪心算法复杂性问题求解的过程及思维方法Specific|one具体过程|具体方法General抽象过程方法与知识Many一般方法抽象具体数据结构：向量，二维数组等问题求解总结1.科学与思维的含义(1)科学①达尔文曾给科学下过一个定义：“科学就是整理事实，从中发现规律，作出结论”。②科学一般包含：自然科学、社会科学和思维科学。(2)思维①思维是高级的心理活动，是认识的高级形式。②思维是人脑对现实事物概括、加工、揭露本质特征。③人脑对信息的处理包括分析、抽象、综合、概括等。2.人类文明进步和科学发现的三大科学(1)理论科学、实验科学和计算科学作为科学发现三大支柱，正推动着人类文明进步和科技发展。(2)该说法已被科学文献广泛引用，并在美国得到国会听证、联邦和私人企业报告的承同。计算思维3.科学思维(1)一般而论，三种科学对应着三种思维：①理论科学←→理论思维：理论思维又叫推理思维，以推理和演绎为特征，以数学学科为代表。②实验科学←→实验思维：实验思维又叫实证思维，以观察和总结自然规律为特征，以物理学科为代表。③计算科学←→计算思维：计算思维又叫构造思维，以设计和构造为特征，以计算机学科为代表。(2)科学思维的含义及重要性：①一般指的是理性认识及其过程，也即经过感性阶段获得的大量材料，通过整理和改造，形成概念、判断和推理，以反映事物的本质和规律。②国科发财〔2008〕197号文《关于创新方法工作的若干意见》认为“科学思维不仅是一切科学研究和技术发展的起点，而且始终贯穿于科学研究和技术发展的全过程，是创新的灵魂”。计算思维计算思维计算思维(ComputationalThinking，CT)是运用计算的基础概念(FundamentalConcept)去求解问题、设计系统和理解人类行为的一种方法(Approach)。CT的本质是抽象(Abstract)和自动化(Automation)。它是如同所有人都具备“读、写、算”（简称3R）能力一样，都必须具备的思维能力。基本概念：约简、嵌入、转化、仿真、递归、并行、多维分析、类型、抽象、分解、SoC，保护、冗余、容错、纠错、系统恢复、启发式、规划、学习、调度、折衷。程序设计课程中问题求解能力培养问题表示(如何建立模型)问题求解（如何设计算法）效率（如何有效地求解）寻找两个正整数的最大公约数的欧几里德算法输入：正整数M和正整数N输出：M和N的最大公约数算法过程：Step1.将较大的数赋给M,较小的数赋给N;Step2.M除以N,记余数为RStep3.如果R不是0,将N的值赋给M,R的值赋给N,返回Step2;否则,最大公约数