Chapter3-问题求解

1、计算机文化基础,计算机与通信工程学院,2010.,计算机的诞生, 标志着用纸和笔进行手工求解(数学)问题的时代结束了。 那么，如何使用计算机进行问题求解?,问题有大小之分，解决有简繁之别,第3章 问题求解,3.1 算法类问题 3.2 系统类问题,算法,算法被誉为计算学科和计算机器的灵魂 “算法”（Algorithm）一词源于数学家的名字：公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书（Persian Textbook），书中概括了进行四则算术运算的法则。,3.1 算法类问题,算法,算法的定义： 一个有穷规则的集合，规则规定了一个解决某一特定类型问题的运算

2、序列。 算法定义了任务执行/问题求解的一系列步骤。 算法的特征： 输入：算法有零个或多个的输入。 输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量 有穷性：一个算法在执行有穷步之后必须结束。 确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。 可行性：算法中有待执行的运算和操作必须是能够精确执行的。,3.1 算法类问题,3.1 算法类问题,寻找两个正整数的最大公约数的欧几里德算法 输入：正整数M和正整数N 输出：M和N的最大公约数 算法过程： Step 1. 将较大的数赋给M,较小的数赋给N; Step 2. M除以N,记余数为R Step 3. 如果R不是0, 将N的值赋

3、给M, R的值赋给N, 返回Step 2; 否则, 最大公约数是N, 输出N, 算法结束,欧几里德算法：求解两个数的最大公因子的算法（公元前300年） 表述了最大公因子的求解过程 表述了一个判定过程，即判定“m和n是互质的”（即除1以外，m和n没有公因子）命题的真假。,欧几里德算法,算法类问题,算法类问题： 由一个算法可以解决的问题 算法(类)问题：寻找一个（唯一的）方法（算法）以解决同一类型的无穷多个单个问题系列的问题。 典型算法类问题： 背包问题 梵天塔问题 哥尼斯堡七桥问题 旅行商问题 ,3.1 算法类问题,3.1 算法类问题,旅行商问题（Traveling Salesman Probl

4、em，TSP） 威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出 有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。,城市之间的距离,An optimal TSP tour through Germanys 15 largest cities. It is the shortest among 43 589 145 600 possible tours visiting each city exactly once.,3.1 算法类问

5、题,旅行商问题,TSP是最有代表性的优化组合问题之一，在半导体制造、物流运输等行业有着广泛的应用 TSP难于求解：2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。,算法类问题求解的过程及思维方法,3.1 算法类问题,数学模型及求解思想,TSP问题的数学模型,3.1 算法类问题,建立数学模型是求解算法类问题的第一步 数学模型：数学模型就是为了某种目的，根据对研究对象所观察到的现象及其实践经验，用字母、数学及其它数学符号建立起来

6、的等式或不等式以及图表、图象、框图等归结成的一套反映对象某些主要数量关系的数学公式、逻辑准则和具体算法，用来描述客观事物的特征，其内在联系和运动规律。,数学模型及求解方法,3.1 算法类问题,所有路径组合及其长度,城市之间的距离,遍历：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线 组合爆炸 路径组合数目：(n-1)! 20个城市，总数1.2161017 ，计算机以每秒检索1000万条路线，需386年,TSP问题的求解方法,求解方法： 遍历 搜索 分治 动态规划 ,TSP问题求解中的数据操纵问题,求解TSP问题需要组织和操纵的对象数据 输入：城市之间的距离关系 输

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

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

9、的过程和顺序,算法的流程控制,控制结构提供了问题求解/算法的过程控制机制 控制结构： 顺序结构： “执行A，然后执行B” 分支结构： “如果Q成立，那么执行A，否则执行B” ，Q是某些逻辑条件 循环结构：控制指令的多次执行迭代（iteration） 有界循环： “执行A指令N次”，其中N是一个整数。 条件循环：某些时候称为无界循环， “重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。,3.1 算法类问题,控制结构的流程图描述,3.1 算法类问题,欧几里德算法,算法策略,可行解与最优解 遍历能够获得最优解，然而，由于组合爆炸，对于较大规模的某些问题，无法在可接受的时间内获得最

10、优解 退而求其次，在可接受的时间内获得足够好的（可行）解,3.1 算法类问题,TSP问题的可行解与最优解,算法策略贪心,贪心算法 “今朝有酒今朝醉” 一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”,3.1 算法类问题,城市之间的距离,TSP问题的贪心求解示例,每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短,3.1 算法类问题,TSP问题贪心算法的流程图,算法与程序,3.1 算法类问题,程序是算法的一种机器相容（Compatible）的表示 程序是利用计算机程序设计语言对算法描述的结果 程序可在计算机上执行 程序设计语言：C、Java、 程序设计过程

11、： 编辑 编译 连接 执行,TSP问题贪心算法程序,3.1 算法类问题,算法的模拟与分析,算法的正确性： 问题求解的过程、方法算法是正确的吗？算法的输出是问题的解吗？ 20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中 算法的效果评价： 算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大？ 两种方法： 分析方法：利用数学方法证明 仿真分析方法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析,3.1 算法类问题,TSP问题贪心算法的模拟与分析,TSP问题贪心算法的正确性： 直观上只需检查算法的输出结

12、果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题实例 TSP问题贪心算法的效果评价： 如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价， 对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。,3.1 算法类问题,算法的复杂性,算法的效率：时间效率和空间效率 时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。 “大O记法”： 基本参数 n问题

13、实例的规模 把复杂性或运行时间表达为n的函数。 “O”表示量级 (order)，允许使用“=”代替“”，如n2+n+1=(n2) 。 算法的空间复杂度：算法在执行过程中所占存储空间的大小。,3.1 算法类问题,TSP问题算法的复杂性,TSP问题遍历算法： 列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线 组合爆炸：路径组合数目为(n-1)! 时间复杂度是O(n-1)!) TSP问题贪心算法： 时间复杂度是O(n3)。,3.1 算法类问题,算法的复杂性,当算法的时间复杂度的表示函数是一个多项式，如O(n2)时，计算机对于大规模问题可以处理 例如，TSP问题的贪心算法

14、算法的时间复杂度用一个指数函数表示，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题称为难解性问题。 例如，TSP问题的遍历算法,3.1 算法类问题,计算复杂性的概念,计算复杂性理论： 所有可以在多项式时间内求解的问题称为P类问题 所有在多项式时间内可以验证的问题称为NP类问题，PNP。 Open problem: P=NP? 美国克雷数学研究所百万大奖难题,3.1 算法类问题,算法类问题求解总结,3.1 算法类问题,系统,系统的概念： 系统是指由相互联系、相互作用的若干元素构成的，具有特定功能的统一整体。 一个大系统往往是复杂的，通常可划分为一系列较小的

15、系统，称为子系统。 系统的特性： 系统是有结构的：系统内各组成部分（元素和子系统）之间相互联系、相互作用的框架。 系统是处于环境之中的：所谓环境是指一个系统之外的一切与它有联系的事物组成的集合。系统要发挥它应有的作用，达到应有的目标，系统自身一定要适应环境的要求。,3.2 系统类问题,系统,系统的特性： 系统是有功能的：所谓功能是指系统行为所引起的、有利于环境中某些事物乃至整个环境存在与发展的作用。 系统是有行为的：所谓行为是指系统相对于它的环境所表现出来的一切变化，行为属于系统自身的变化，同时又反映环境对系统的影响和作用。 系统是有状态的：所谓状态是指系统的那些可以观察和识别的形态特征。状态

16、一般可以用系统的定量特征来表示，如温度T、体积V等。,3.2 系统类问题,系统,典型系统实例：,3.2 系统类问题,卫星导航系统,操作系统,机器人系统,系统类问题与系统科学,系统类问题： 系统类问题是那些不能由单一算法解决，而必须构建一个系统来解决的问题。例如，生产过程控制问题，军事导航问题，制造企业生产计划管理问题 ,3.2 系统类问题,物料需求管理问题场景,系统类问题与系统科学,解决系统类问题需要采用系统科学方法： 系统科学是以系统为研究和应用对象的一门科学，诞生于20世纪40年代。系统科学的崛起被认为是20世纪现代科学的两个重大突破性成就之一。 系统科学是探索系统的存在方式和运动变化规律

17、的学问，是对系统本质的理性认识，是人们认识客观世界的一个知识体系。 系统科学方法是用系统的观点来认识和处理问题的各种方法的总称。 计算学科中的结构化方法、面向对象方法都沿用了系统科学的思想方法。,3.2 系统类问题,系统类问题与系统科学,（系统科学）解决系统类问题遵循的原则： 整体性原则： 非还原性是指系统的整体具有但还原为部分便不存在的特性“涌现性” 非加和性是指整体不能完全等于各部分之和“贝塔朗菲定律” 研究系统时，应从整体出发，立足于整体来分析其部分以及部分之间的关系，进而达到对系统整体的更深刻的理解。 整体优化原则：运用各种有效方法，从系统多种目标或多种可能的途径中选择最优系统、最优方

18、案、最优功能、最优运动状态，达到整体优化的目的。,3.2 系统类问题,系统类问题与系统科学,（系统科学）解决系统类问题遵循的原则： 动态原则： 系统总是动态的，永远处于运动变化之中。 研究系统时，应从动态的角度去研究系统发展的各个阶段，以准确把握其发展过程及未来趋势。 模型化原则 根据系统模型说明的原因和真实系统提供的依据，提出以模型代替真实系统进行模拟实验，达到认识真实系统特性和规律性的方法。 模型化方法是系统科学的基本方法，主要采用符号模型，包括概念模型、逻辑模型、数学模型等。 基于计算机的模型（Computer-Based Model），计算思维（Computational thinki

19、ng），建立基于计算机的模型，利用计算手段研究和解决系统类问题。,3.2 系统类问题,系统类问题求解过程及思维方法,3.2 系统类问题,系统类问题求解第一步：业务模型与业务建模,系统类问题求解的第一步业务建模/问题域建模 系统类问题是复杂问题，解决该问题的前提是正确的理解问题，把握系统的目标、结构、行为等，并将其描述出来 运用系统科学的模型化原则 这一过程称为业务建模/问题域建模 获得的结果业务模型,3.2 系统类问题,业务模型与业务建模,模型与建模的概念 模型是对某一真实系统（如卫星导航系统、企业信息系统）的目标、结构、行为的抽象描述。 模型的内容： 识别概念 识别概念间的关系 表达（可视化

20、/形式化） 建模的根本原则抽象：把握系统的本质内容，而忽略与系统当前目标无关的内容，它是一种基本的认知过程和思维方式。,3.2 系统类问题,业务模型与业务建模,业务建模/问题域建模的内容 业务过程模型 组织模型 信息模型 . 业务模型的作用： 理解 区分 命名 表达,3.2 系统类问题,物料需求管理问题的业务模型,3.2 系统类问题,概念及关系： 产品结构：描述了产品的构成关系，即产品各零部件之间的父子构成关系，一个父件由多少单位的子件构成。 提前期和期量标准：提前期描述了由零件制造、产品装配或材料采购所需的时间，当所有构成子件完成后制造出父件的周期即为提前期。期量标准是依据产品结构模型和提前

21、期信息，为产品建立时间坐标上的产品结构。,3.2 系统类问题,物料需求管理问题的业务模型,概念： 独立需求物项：企业可以独立对外销售的物料，其需求数量一般由市场决定，不依赖于其他物料的需求。 相关需求物项：为了制造独立需求物项而制造或采购的物项，例如木板是为了制造桌子而采购的，其需求数量是依赖于其他(独立或相关)物料需求数量而计算出来的。 库存：为了某些目的存储在仓库中的物项，库存量因入库而增加，因出库而减少，库存可以用于生产。 在途：物项已经投产尚未完工或已经采购尚未到货的数量，将在未来某一时间完工可用或到货。 计划产出量：预计将于某一时段产出某种物项的数量。 计划投入量：预计将于某一时段投

22、入某种物项的数量。,3.2 系统类问题,物料需求计算过程的实例：,物料需求管理问题的业务模型,3.2 系统类问题,问题的核心模型-物料需求计算模型,物料需求管理问题的业务模型,物料需求管理问题的求解：核心算法及软件系统,3.2 系统类问题,系统类问题求解第二步：软件模型,系统类问题的求解需要构建一个系统 人：用户/使用者 硬件：计算机、网络 软件： 基础软件：操作系统、数据库管理系统 应用软件：面向特定系统类问题求解的软件 应用软件的构建是系统类问题求解的核心 软件是复杂的智力产品，需运用系统科学方法、工程方法获取软件工程 业务模型（问题域模型）软件模型软件系统（解）,3.2 系统类问题,软件

23、模型,软件系统 系统 模块 类 函数 变量 调用/事件 对象/实例 数据库 表 ,3.2 系统类问题,软件模型,软件模型/软件建模 用例模型 功能模型 结构模型 行为模型 数据模型 ,3.2 系统类问题,物料需求管理系统的软件模型,3.2 系统类问题,模块划分及功能分解模型 分解原则：先总体、后局部的思想原则，自顶向下、分层解决。 模块化原则：将系统分解成具有特定功能的若干模块，从而完成系统指定的各项功能。,物料需求管理系统的软件模型,3.2 系统类问题,结构模型（类图） 基本构造法则： 区分对象及其属性； 区分整体对象及其组成部分； 形成并区分不同对象的类。 抽象：强调一个对象和其他对象相区

24、别的本质特性。 封装：封装是对抽象元素的划分过程，抽象由结构和行为组成，封装用来分离抽象的原始接口和它的执行。 类之间的静态联系：继承，聚合，关联,类图表示法,3.2 系统类问题,物料需求管理系统的软件模型,结构模型（类图）,3.2 系统类问题,物料需求管理系统的软件模型,动态/行为模型：表征运行时的对象交互/消息传递/接口调用,系统类问题求解第三步：软件实现,软件模型必须被实现为软件系统，才能够实际被用户使用，解决系统类问题 软件实现： 利用程序设计语言将软件模型转换为可运行的软件模块/系统 模块系统 模块实现的内容 用户界面程序 业务处理程序 数据的持久化存储程序 模块实现程序必须进行测试

25、模块/单元测试：模块接口测试，局部数据结构测试，路径测试，错误处理测试，边界测试,3.2 系统类问题,系统类问题求解第三步：软件实现,系统实现的概念： 将多个模块组装成一个完整的系统 系统实现的内容： 选择合适的体系结构并建立系统底层框架； 建立菜单管理器，即建立系统的功能菜单，给用户以功能入口； 提供系统级的功能和基础设施，如安全和权限控制、统一的界面风格控制、统一的数据访问等； 模块/构件的装载，包括将模块/构件装载到框架上，与菜单关联起来等； 将模块/构件组装为完整的过程以支持完整的问题求解等。 模块组装成系统后要进行整体测试系统测试,3.2 系统类问题,物料需求管理系统的软件实现,3.

26、2 系统类问题,库存管理模块业务处理程序,库存管理模块用户界面,物料需求管理系统的功能菜单和框架,3.2 系统类问题,物料需求管理系统的软件实现,系统类问题求解的第四步：系统的部署与运行,3.2 系统类问题,系统类问题求解的第四步：系统的部署与运行,系统部署与运行：数据+软件系统+使用 在企业构建系统运行的必要环境，铺设网络、搭建硬件、软件平台。 部署软件系统到企业： 在数据库中建立数据库、表、视图等； 在客户机、应用服务器上安装（物料需求管理）系统的客户机部分或服务器部分，取决于软件系统的体系结构选择； 对系统进行测试。 系统配置：设置系统的用户（计划员、库管员等）、设置用户的权限（即可以使

27、用的软件功能和数据）等。 对系统进行必要的初始化：将企业中的所有物项编码、清查库房中的物项数量，并将这些数据输入到系统中，作为系统运行的起点。,3.2 系统类问题,系统类问题求解的第四步：系统的部署与运行,系统部署与运行：数据+软件系统+使用 系统的试运行/试应用：尝试性的利用系统来解决问题，支持业务工作，例如计算物项的需求、对物项计划作出安排等，在此过程中，系统的运行、系统所产生的输出需要由用户检验其正确性，必要时对系统进行调整。 系统的运行和应用：如系统通过了试运行/试应用，则系统开始正式应用，企业信任该系统的解决问题的能力，并依赖系统支持其业务工作和问题求解。当然，某些错误可能会在运行期

28、出现，此时再进行系统的维护和完善。,3.2 系统类问题,物料需求管理系统的部署与运行,系统角色与权限配置,3.2 系统类问题,物料需求管理系统的体系结构选择,3.2 系统类问题,客户机/服务器结构,浏览器/服务器结构,用户界面 + 业务逻辑,数据,用户界面 + 业务逻辑,数据,高级话题：系统的结构性与演化,为什么系统的结构会变化，会演化？ 早期的软件实现技术是从零开始，利用某种程序设计语言实现模块或系统的所有部分，如用户界面、业务处理、数据的持久化存储等。缺点： 程序员需要考虑硬件平台、操作系统平台的特性等诸多因素。 实现难度大，对程序员的要求高，实现周期长，成本高。 随着技术的发展和反复的开

29、发，逐渐形成了对某类问题的有效解决方案，并形成了支持该问题的系统和工具 问题逐渐分离为与特定应用有关的部分和与特定应用无关的共性技术及工具，导致了软件实现模式和体系结构的发展和演化。,3.2 系统类问题,早期的程序员在实现时需要自己设计、定义数据的逻辑结构、数据的存储形式/结构，还需要考虑硬件平台、操作系统平台的特性等。 随着技术的发展和反复的开发，逐渐形成了关系数据库理论，并形成了关系数据库管理系统等工具 数据持久化存储问题逐渐分离为与特定应用有关的部分（如物料需求管理系统中的特定数据内容及格式）和与特定应用无关的共性技术及工具（如关系数据库及关系数据库管理系统），导致了软件实现模式和体系结

30、构的发展和演化。,3.2 系统类问题,系统结构演化举例数据持久化存储问题,系统的结构性与演化,软件模式的概念： “每个模式描述了那些在我们的环境中反复发生的问题，然后描述了该问题的解决方案的核心，从而使得你可以重复利用该方案”。 模式关注于某种特定的解决方案，这种方案在处理一个或多个反复发生的问题时是通用而有效的。 模式的一个关键特征是他们根植于实践，你可以通过观察人如何做事、事物如何工作而获得“解决方案的核心”。 模式广泛存在于软件的分析、设计、实现等过程和领域中，应该有针对性的选择软件模式，以更好、更快地解决软件系统问题。 软件模式影响了软件的结构，促进了软件结构的演化。,3.2 系统类问

31、题,系统的结构性与演化,软件体系结构： 问题： 随着软件系统的规模和复杂性不断增加，系统的全局结构的设计和规划变得比算法的选择以及数据结构的设计更加重要。 全局组织结构、全局控制结构、通信和同步、数据存取的协议、设计元素的功能、设计元素的组合、物理分布、规模和性能、设计方案的选择等。 软件体系结构的概念：包括构成系统的设计元素的描述、设计元素的交互、设计元素组合的模式，以及在这些模式中的约束。 软件体系结构的重要性：为系统设计一个合适的体系结构是系统取得长远的成功的关键因素。,3.2 系统类问题,系统的结构性与演化,软件体系结构设计的基本原则 抽象，分而治之，封装和信息隐藏，模块化原则，高内聚和低耦合，关注点分离，策略和实现的分离，接口和实现分离， 典型的软件体系结构 管道过滤器，数据抽象和面向对象组织结构，事件驱动和隐式调用，分层系统，知识库，解释器，过程控制， 应用领域 文字编辑软件、仪器软件、机器人、汽车的定速巡航控制以及管理信息系统、建筑设计软件、机械设计软件等,3.2 系统类问题,系统的可靠性与安全性,解决系统类问题需要考虑可靠性问题 可靠性(Reliability)的概念：产品在规定的条件下和规定的时间内完成规定功