第4章 问题求解与计算思维

《第4章 问题求解与计算思维》由会员分享，可在线阅读，更多相关《第4章 问题求解与计算思维（39页珍藏版）》请在金锄头文库上搜索。

1、 第4章问题求解与计算思维 主讲教师 郑立垠 计算机与通信工程学院计算机应用技术系 中国自古就有喝茶的历史习俗 有同学知道泡茶的流程吗 烧水 温具 置茶 冲泡 奉茶 赏茶 续水 引入 有一个牧羊人带着一只羊 一匹狼和一颗大白菜准备过河 他找到一只很小的船 每次只能带一样东西过去 可是如果让狼与羊单独在一起 狼会吃羊 让羊与白菜单独在一起 羊会吃白菜 牧羊人应如何过河 过河的方案 第一步 人和羊过河 人返回 留下羊 第二步 人和狼过河 人和羊返回 留下狼 第三步 人和菜过河 人返回 留下菜 第四步 人和羊过河 人在解决问题时 要先对问题进行分析思考 然后确定解决问题的方法和步骤 这种解决问题的方

2、法和步骤就称为算法 引入 1 算法2 计算思维 本章内容 算法的由来 算法算法被誉为计算学科和计算机器的灵魂 算法 Algorithm 一词源于 公元825年 阿拉伯数学家阿科瓦里茨米 AlKhowarizmi 写了著名的 波斯教科书 PersianTextbook 书中概括了进行四则算术运算的法则 算法的定义 一个有穷规则的集合 规则规定了一个解决某一特定类型问题的运算序列 定义了任务执行 问题求解的一系列步骤 算法的特征 输入 有零个或多个的输入 输出 有一个或多个的输出 有穷性 一个算法在执行有穷步之后必须结束 确定性 算法的每一个步骤必须要确切地定义 不得有歧义性 可行性 算法原则上能

3、够精确地运行 算法的定义及特征 算法描述 自然语言容易引起歧义 造成误解 对较复杂的问题 难以表达准确流程图直观形象 但计算机不能识别和执行程序代码用计算机能理解和执行的程序设计语言把算法表示出来 然后由计算机按照预定的算法去解决问题 算法设计数学建模数据结构控制流程算法策略遍历搜索递归动态规划贪心 算法设计 算法的正确性 问题求解的过程 方法 算法是正确的吗 算法的输出是问题的解吗 20世纪60年代 美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中算法的效果评价 算法的输出是最优解还是可行解 如果是可行解 与最优解的偏差多大 两种方法 分析方法 利用数学方法证明仿真分析方法 产生

4、或选取大量的 具有代表性的问题实例 利用该算法对这些问题实例进行求解 并对算法产生的结果进行统计分析 算法分析 算法的效率 时间效率和空间效率时间复杂性 如果一个问题的规模是n 解这一问题的某一算法所需要的时间为T n 它是n的某一函数 T n 称为这一算法的 时间复杂性 大O记法 基本参数n 问题实例的规模把复杂性或运行时间表达为n的函数 O 表示量级 order 允许使用 代替 如n2 n 1 n2 算法的空间复杂度 算法在执行过程中所占存储空间的大小 算法效率 算法的复杂性 当算法的时间复杂度的表示函数是一个多项式 如O n2 时 计算机对于大规模问题可以处理算法的时间复杂度用一个指数函

5、数表示 如O 2n 当n很大 如10000 时计算机是无法处理的 在计算复杂性中将这一类问题称为难解性问题 算法效率 当n值增大时 各种时间复杂度存在下列关系 O log2n O n O nlog2n O n2 O 2n O n 旅行商问题 TravelingSalesmanProblem 威廉哈密尔顿爵士和英国数学家克克曼T P Kirkman于19世纪初提出有若干个城市 任何两个城市之间的距离都是确定的 现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次 最后回到原出发城市 问如何事先确定好一条最短的路线使其旅行的费用最少 城市之间的距离 AnoptimalTSPtour

6、throughGermany s15largestcities Itistheshortestamong43589145600possibletoursvisitingeachcityexactlyonce 旅行商问题 TSP是最有代表性的优化组合问题之一 在半导体制造 物流运输等行业有着广泛的应用TSP难于求解 2001年解决了德国15112个城市的TSP问题 使用了美国Rice大学和普林斯顿大学之间互连的 速度为500MHz的CompaqEV6Alpha处理器组成的110台计算机 所有计算机花费的时间之和为22 6年 建立数学模型是求解算法类问题的第一步数学模型 数学模型就是为了某种目的

7、根据对研究对象所观察到的现象及其实践经验 用字母 数学及其它数学符号建立起来的等式或不等式以及图表 图象 框图等归结成的一套反映对象某些主要数量关系的数学公式 逻辑准则和具体算法 用来描述客观事物的特征 其内在联系和运动规律 旅行商问题 数学模型及求解思想 TSP问题的数学模型 数学模型及求解方法 求解方法 遍历搜索分治动态规划 TSP问题的求解方法 遍历 列出每一条可供选择的路线 计算出每条路线的总里程 最后从中选出一条最短的路线组合爆炸路径组合数目 n 1 20个城市 总数1 216 1017 计算机以每秒检索1000万条路线 需386年 所有路径组合及其长度 城市之间的距离 旅行商问题

8、问题求解中的数据组织及操纵 问题求解过程中需要组织及操作数据 TSP问题求解中的数据操纵问题 求解TSP问题需要组织和操纵的对象 数据输入 城市之间的距离关系输出 访问城市的路径中间结果 路径的距离之和 旅行商问题 数据结构 数据结构提供了问题求解 算法的数据操纵机制数据结构 逻辑结构 数据之间的关系存储结构 在反映数据逻辑关系的原则下 数据在存储器中的存储方式 有顺序存储结构和链式存储结构 基本运算 1 建立数据结构 2 清除数据结构 3 插入数据元素 4 删除数据元素 5 更新数据元素 6 查找数据元素 7 按序重新排列 8 判定某个数据结构是否为空 或是否已达到最大允许的容量 9 统计数

9、据元素的个数等 旅行商问题 数据结构 基本数据结构 变量向量 列表矩阵 表 向量实例 1 2 3 4 1 2 3 行 列 M 2 3 表实例 4 旅行商问题 TSP问题求解的数据结构 城市间距离关系表D访问路径 解一维数组S路径距离之和整数变量sum循环计数器i j k A D C B A 示例 旅行商问题 城市之间的距离 问题求解中的过程控制 问题求解过程中需要组织并控制操作 指令的过程和顺序 TSP问题求解的流程控制 求解TSP问题需要控制指令 基本操作的逻辑过程 流程遍历所有的组合路径判断某条路径的距离是不是比另外一条短 并据此作出不同的处理累加一条路径的距离之和 旅行商问题 算法策略

10、可行解与最优解遍历能够获得最优解 然而 由于组合爆炸 对于较大规模的某些问题 无法在可接受的时间内获得最优解退而求其次 在可接受的时间内获得足够好的 可行 解 TSP问题的可行解与最优解 旅行商问题 算法策略 贪心 贪心算法 今朝有酒今朝醉 一定要做当前情况下的最好选择 否则将来可能会后悔 故名 贪心 TSP问题的贪心求解示例 每次在选择下一个城市的时候 只考虑当前情况 保证迄今为止经过的路径总距离最短 城市之间的距离 旅行商问题 TSP问题贪心算法的模拟与分析 TSP问题贪心算法的正确性 直观上只需检查算法的输出结果中 每个城市出现且仅出现一次 该结果即是TSP问题的可行解 说明算法正确的求

11、解了这些问题实例TSP问题贪心算法的效果评价 如果实例的最优解已知 问题规模小或问题已被成功求解 利用统计方法对若干问题实例的算法结果与最优解进行对比分析 即可对其进行效果评价 对于较大规模的问题实例 其最优解往往是未知的 因此 算法的效果评价只能借助于与前人算法结果的比较 旅行商问题 TSP问题算法的效率 TSP问题遍历算法 列出每一条可供选择的路线 计算出每条路线的总里程 最后从中选出一条最短的路线组合爆炸 路径组合数目为 n 1 时间复杂度是O n 1 计算机不能处理TSP问题贪心算法 时间复杂度是O n3 计算机可以处理 旅行商问题 问题求解总结 1 科学与思维的含义 1 科学 达尔文

12、曾给科学下过一个定义 科学就是整理事实 从中发现规律 作出结论 科学一般包含 自然科学 社会科学和思维科学 2 思维 思维是高级的心理活动 是认识的高级形式 思维是人脑对现实事物概括 加工 揭露本质特征 人脑对信息的处理包括分析 抽象 综合 概括等 2 人类文明进步和科学发现的三大科学 1 理论科学 实验科学和计算科学作为科学发现三大支柱 正推动着人类文明进步和科技发展 2 该说法已被科学文献广泛引用 并在美国得到国会听证 联邦和私人企业报告的承同 计算思维 3 科学思维 1 一般而论 三种科学对应着三种思维 理论科学 理论思维 理论思维又叫推理思维 以推理和演绎为特征 以数学学科为代表 实验

13、科学 实验思维 实验思维又叫实证思维 以观察和总结自然规律为特征 以物理学科为代表 计算科学 计算思维 计算思维又叫构造思维 以设计和构造为特征 以计算机学科为代表 2 科学思维的含义及重要性 一般指的是理性认识及其过程 也即经过感性阶段获得的大量材料 通过整理和改造 形成概念 判断和推理 以反映事物的本质和规律 国科发财 2008 197号文 关于创新方法工作的若干意见 认为 科学思维不仅是一切科学研究和技术发展的起点 而且始终贯穿于科学研究和技术发展的全过程 是创新的灵魂 计算思维 计算思维 计算思维 ComputationalThinking CT 是运用计算的基础概念 Fundamen

14、talConcept 去求解问题 设计系统和理解人类行为的一种方法 Approach CT的本质是抽象 Abstract 和自动化 Automation 它是如同所有人都具备 读 写 算 简称3R 能力一样 都必须具备的思维能力 基本概念 约简 嵌入 转化 仿真 递归 并行 多维分析 类型 抽象 分解 SoC 保护 冗余 容错 纠错 系统恢复 启发式 规划 学习 调度 折衷 程序设计课程中问题求解能力培养 问题表示 如何建立模型 问题求解 如何设计算法 效率 如何有效地求解 寻找两个正整数的最大公约数的欧几里德算法输入 正整数M和正整数N输出 M和N的最大公约数算法过程 Step1 将较大的数

15、赋给M 较小的数赋给N Step2 M除以N 记余数为RStep3 如果R不是0 将N的值赋给M R的值赋给N 返回Step2 否则 最大公约数是N 输出N 算法结束 欧几里德算法 求解两个数的最大公因子的算法 公元前300年 表述了最大公因子的求解过程表述了一个判定过程 即判定 m和n是互质的 即除1以外 m和n没有公因子 命题的真假 求最大公约数 乒乓球挑选 有13个乒乓球 其中有一个是坏的 其质量与其它球不同 请设计算法将其挑出 建模与设计 解答1 步骤1 将13个球分成4 4 4 1四份 分别记为a b c d组 步骤2 先比较a b两组的轻重 若a与b一样重 取c中任意4个球与a或b

16、比较 若都一样重 则d组为次品 若不一样重 则可知次品在c组取出的4个球中 并且可判断次品是轻还是重 若a与b不一样重 取c组与a或b进行称量对比 得出含有次品组为a组或者b组以及判断出次品是轻还是重 步骤3 从步骤2中得到含有4个球的次品组 将这4个球平分成2组称量 根据次品是轻或重得到含有次品组e 再将次品组e中2个球分别放置天平两端 根据次品轻重判断得到次品球 乒乓球挑选 解答2 1 将13个球分为三个部分 6 6 1 将6 6两部分进行称量 若平衡 则1所代表物品为次品 否则 2 2 取一组6 将其平分为两组计为a b 另一组6再平分为c d 取a b c两两称量 若都平衡则次品在d中 转到 3 若有一次不平衡 则次品在a b c之中 转到 3 3 将三个任取两个称量 若平衡 则次品为未称量的物品 若不平衡 则转到 4 4 若不平衡再测一次即可得次品 乒乓球挑选 解答3 将13个球记为1 2 3 4 5 5 6 7 8 9 10 11 12 13 1 6记为A 7 12号记为B 步骤1 将AB组球放在天平上 若天平平衡 则次品为13号球 若不平衡 则转向步骤2 步骤2 取较轻的