1、1/55算法程序与计算系统之灵魂2/55基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架内容提要内容提要3/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂1.算法与算法类问题求解算法与算法类问题求解算法与算法类问题求解算法与算法类问题求解-什么是算法什么是算法-算法类问题及求解概述算法类问题及求解概述4/55算法算法u算法-计算学科和计算机器的灵魂。“算法”(Algorithm)一词源于数学家的名字：公元825年，阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的波斯教科书(Persian Textbook)，书中概括了进行四则算术运算的计算规则。u算法算法
2、是一个是一个有穷规则有穷规则的集合，它用规则规定了解决某一特定类型问题的运算的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。序列，或者规定了任务执行或问题求解的一系列步骤。1.算法与算法类问题求解算法与算法类问题求解1.1 什么是算法什么是算法?如音乐乐谱、太极拳谱等都可看作广义的算法如音乐乐谱、太极拳谱等都可看作广义的算法5/55算法算法解决问题的步骤程序程序计算机能够理解与执行的解决问题的步骤计算机语言计算机语言步骤书写的规范、语法规则、标准的集合是人和计算机都能理解的语言 算法、语言与计算机程序算法、语言与计算机程序1.算法与算法类问题求解
3、算法与算法类问题求解1.2 为什么算法很重要呢为什么算法很重要呢?“是否会编程序是否会编程序”，本质上是，本质上是“能否想出求解问题的算法能否想出求解问题的算法”，其次才是将算法用计算机可以识别的形式书写出来其次才是将算法用计算机可以识别的形式书写出来6/55u欧几里德算法欧几里德算法：求解两个数的最大求解两个数的最大公约数的算法公约数的算法(公元前公元前300年年)表述了最大公约数的求解过程表述了一个判定过程，即判定“m和n是互质的”（即除1以外，m和n没有公约数）命题的真假。该算法体现了输入、输出、有穷规则、确定性和能行性等算法的基本特征。寻找两个正整数的最大寻找两个正整数的最大公约数的欧
4、几里德算法公约数的欧几里德算法输入输入：正整数：正整数M和正整数和正整数N输出输出：M和和N的最大公约数的最大公约数(设设MN)算法步骤算法步骤：Step 1.M除以除以N,记余数为记余数为RStep 2.如果如果R不是不是0，将将N的值赋给的值赋给M,R的值赋给的值赋给N,返回返回Step 1;否则否则,最大最大公约数是公约数是N,输出输出N,算法结束。算法结束。算法示例算法示例1.算法与算法类问题求解算法与算法类问题求解1.3 什么是计算学科中的算法什么是计算学科中的算法?7/55有穷性有穷性：一个算法在执行有穷步规则之后必须结束。确定性确定性：算法的每一个步骤必须要确切地定义，不得有歧义
5、性。输入输入：算法有零个或多个的输入。输出输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。能行性能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成可以由机器自动完成)。并能在有限时间内完成。算法的基本特征算法的基本特征1.算法与算法类问题求解算法与算法类问题求解1.4 具备什么特征才能被认为是算法具备什么特征才能被认为是算法?基本运算：除法、赋值、逻辑判断基本运算：除法、赋值、逻辑判断典型的典型的“重复重复/循环循环”与与“迭代迭代”寻找两个正整数的最大寻找两个正整数的最大公约数的欧几里德算法公约数的欧几里德算法输入输入：正整数：正整数M和正整数和正整数N输
6、出输出：M和和N的最大公约数的最大公约数(设设MN)算法步骤算法步骤：Step 1.M除以除以N,记余数为记余数为RStep 2.如果如果R不是不是0，将将N的值赋给的值赋给M,R的值赋给的值赋给N,返回返回Step 1;否则否则,最大最大公约数是公约数是N,输出输出N,算法结束。算法结束。8/55u算法(类)问题：寻找一个(唯一的)方法(算法)以解决同一类型的无穷多个单个问题系列的问题。u典型问题：哥尼斯堡七桥问题哥尼斯堡七桥问题：“寻找走遍这7座桥且只许走过每座桥一次最后又回到原出发点的路径”“对给定的任意一个河道图与任意多座桥判定可能不可能每座桥恰好走过一次?”。梵天塔问题梵天塔问题：有
7、三根柱子，梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上形成一座金塔，要求每次只能移动一个盘子，盘子只能在三根柱子上来回移动不能放在他处，在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上。其他如：背包问题背包问题，丢番图方程可丢番图方程可解性问题解性问题；1.算法与算法类问题求解算法与算法类问题求解1.5 你知道一些典型的算法类问题吗你知道一些典型的算法类问题吗?算法类问题：由一个算法可以解决的问题9/55uTSP问题(Traveling Salesman Problem，旅行商问题旅行商问题)，威廉哈密尔顿爵士和英国数学家克克曼于19世纪初提出TSP问题uT
8、SP问题问题：有若干个城市，任何两个城市之间的距离都是确定的，现要：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。最少。uTSP是最有代表性的组合优化组合优化问题之一，在半导体制造(线路规划)、物流运输(路径规划)等行业有着广泛的应用。城市之间的距离城市之间的距离1.算法与算法类问题求解算法与算法类问题求解1.6 你知道你知道
9、TSP问题吗问题吗?算法类问题示例10/55u问题抽象及数学建模问题抽象及数学建模：将问题抽象为一个数学问题，并给出求解该数学问题的算法模型。u算法策略设计算法策略设计u算法的数据结构和控制结构算法的数据结构和控制结构设计设计：将数学模型转换为可由计算机自动计算的算法。u算法的实现算法的实现：用程序设计语言编写算法实现的程序。u算法的分析算法的分析：分析算法的正确性和复杂性，判断能行性！1.算法与算法类问题求解算法与算法类问题求解1.7 你知道算法类问题求解的一般步骤吗你知道算法类问题求解的一般步骤吗?算法类问题求解框架11/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂2.数学建模
10、与算法策略设计数学建模与算法策略设计-算法思想算法思想数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想-数学建模数学建模-有不同的算法求解策略有不同的算法求解策略12/55算法类问题求解的第一步就是要数学建模。算法类问题求解的第一步就是要数学建模。u数学建模：数学建模：是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立对问题进行精确描述和定义的数学模型。简单而言，数学建模数学建模是用数学语言描述实是用数学语言描述实际现象的过程际现象的过程，即建立数学模型的过程。u数学模型数学模型是对实际问题的一种数学表述，是关于部分现实世界为某种目是对实际问题的一种数学表述，是关于
11、部分现实世界为某种目的的一个抽象的简化的数学结构。的的一个抽象的简化的数学结构。2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.1 为什么说数学建模对于算法很重要为什么说数学建模对于算法很重要?将现实世界的问题抽象成数学模型，就可能发现问题的本将现实世界的问题抽象成数学模型，就可能发现问题的本质及其能否求解，甚至找到求解该问题的方法和算法。质及其能否求解，甚至找到求解该问题的方法和算法。13/55哥尼斯堡七桥问题哥尼斯堡七桥问题被抽象成一个“图图(Graph)”-由节点和边所构成的一种结构，-依据“图”，可发现该问题所蕴含的许多性质：u“回路回路-从一个节点出发最后又回到
12、该节点的一条路径”u“连通连通-两个节点间有路径相连接”u“可达可达-从一个节点出发能够到达另一个节点”u“经过图中每边一次且仅一次的回路经过图中每边一次且仅一次的回路”u“经过图中每个节点一次且仅一次的回路”u 什么情况下有解，什么情况下无解？什么情况下有解，什么情况下无解？u注：离散数学或者集合论与图论课程将介绍图的有关性质和方法。2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.1 为什么说数学建模对于算法很重要为什么说数学建模对于算法很重要?如果能抽象成数学模型，则可将一个具体问题如果能抽象成数学模型，则可将一个具体问题的求解，推广为一类问题的求解！的求解，推广为一
13、类问题的求解！14/55TSP问题的数学模型问题的数学模型2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.2 数学建模要做到怎样数学建模要做到怎样?15/55算法策略设计算法策略设计-算法思想算法思想当数学建模完成后，就要设计算法的策略或者说问题求解的策略。当数学建模完成后，就要设计算法的策略或者说问题求解的策略。uTSP问题的基本求解策略u遍历遍历：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线。u出现的问题是出现的问题是：组合爆炸组合爆炸路径组合数目：(n-1)!20个城市，遍历总数1.2161017计算机以每秒检索1000万条路线的计算
14、速度，需386年。所有路径组所有路径组合及其长度合及其长度城市之间的距离城市之间的距离2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.3 算法思想或者算法策略对问题求解有什么影响算法思想或者算法策略对问题求解有什么影响?16/55uTSP问题的难解性问题的难解性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。u2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机台计算机，所有计算机花费的时间之和为22.6年年。An
15、optimal TSP tour through Germanys 15 largest cities.It is the shortest among 43 589 145 600 possible tours visiting each city exactly once.2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.3 算法思想或者算法策略对问题求解有什么影响算法思想或者算法策略对问题求解有什么影响?17/55uTSP问题，有没有其他求解算法呢？问题，有没有其他求解算法呢？u最优解最优解 vs.可行解可行解u不同的算法设计策略：遍历、搜索算法遍历、搜索算法 分治算
16、法分治算法 贪心算法贪心算法 动态规划算法动态规划算法 u可选取一种合适的策略来求解TSP问题可行解最优解TSP问题的可行解与最优解示意2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.4 有哪些算法策略有哪些算法策略?算法策略设计算法策略设计-算法思想算法思想18/55u贪心算法贪心算法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。一定要做当前情况下的最好选择，否则一定要做当前情况下的最好选择，否则将来可能会后悔，故名将来可能会后悔，故名“贪心贪心”。uTSP问题的贪心算法求解思想从某一个城市开始，每次选择一个城市，直到所有城市都被走完。每次在选择下一
17、个城市的时候，只考虑每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距当前情况，保证迄今为止经过的路径总距离最短。离最短。城市之间的距离城市之间的距离2.数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想2.5 为什么称为为什么称为“贪心算法贪心算法”?贪心算法贪心算法19/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂3.算法设计算法设计-算法思想的精确表达算法思想的精确表达算法设计算法设计-算法思想的精确表达算法思想的精确表达(I)-算法的数据结构设计算法的数据结构设计-算法的控制结构设计及其表达方法算法的控制结构设计及其表达方法-TSP算法解读算
18、法解读20/553.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.1 算法设计包括什么算法设计包括什么?算法设计算法设计n算法的数据结构设计算法的数据结构设计-问题或算法相关的数据之间的逻辑关问题或算法相关的数据之间的逻辑关系及存储关系的设计系及存储关系的设计 n算法的控制结构设计算法的控制结构设计-算法的计算规则或计算步骤设计算法的计算规则或计算步骤设计如何构造和表达处理的规则，以便能够按规则逐步计算出结果如何构造和表达处理的规则，以便能够按规则逐步计算出结果?如何将数学模型中的数据转为计算机可以存储和处理的数据？如何将数学模型中的数据转为计算机可以存储和处理的数据？21/55数
19、据结构数据结构u如何组织、记忆、改变和操作数据的集合呢？数据存在什么结构呢？数据的逻辑结构数据的逻辑结构：数据之间的关系；数学模型中反映的通常是数据的逻辑结构。数据的存储结构数据的存储结构：在反映数据逻辑关系的原则下，数据在存储器中的存储方式。典型的有顺序存储结构和链式存储结构。面向数据存储结构的基本运算基本运算：(1)建立数据结构；(2)清除数据结构；(3)插入数据元素；(4)删除数据元素；(5)更新数据元素；(6)查找数据元素；(7)按序重新排列；(8)判定某个数据结构是否为空，或是否已达到最大允许的容量；(9)统计数据元素的个数等。u数据结构数据结构是数据的逻辑结构、存储结构及其操作的总
20、称，它提供了问题是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解求解/算法的数据操纵机制。算法的数据操纵机制。3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.2 什么是数据结构什么是数据结构?22/553.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.2 什么是数据结构什么是数据结构?典型的数据结构典型的数据结构-“树树”示例示例存储结构中存储结构中,用一个指针表达数据之间的逻辑关系用一个指针表达数据之间的逻辑关系150120160数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构503070100数据元素数据元素对应数据元素的对应数据元素的指针指针指
21、向该元指向该元素的父元素素的父元素数据结构的设计数据结构的设计23/55150120160503070100数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构通过指针的变化通过指针的变化,不改变数据的存储不改变数据的存储,但却改变了数据之间的逻辑关系但却改变了数据之间的逻辑关系数据结构的设计数据结构的设计3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.2 什么是数据结构什么是数据结构?24/55150120160503070100数据元素数据元素对应数据元素的左对应数据元素的左指针指针指向该元素指向该元素的左侧子结点的左侧子结点对应数据元素的右对应数据元素的右指针指针指向该
22、元素指向该元素的右侧子结点的右侧子结点3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.3 同样的逻辑结构可以有不同的存储结构吗同样的逻辑结构可以有不同的存储结构吗?数据结构的设计数据结构的设计典型的数据结构典型的数据结构-“树树”示例示例另一种存储结构另一种存储结构,用两个指针用两个指针表达数据之间的逻辑关系表达数据之间的逻辑关系数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据结构不同，数据之间的操作方法也是不同的数据结构不同，数据之间的操作方法也是不同的25/551501201605030701003.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.3 同
23、样的逻辑结构可以有不同的存储结构吗同样的逻辑结构可以有不同的存储结构吗?数据结构的设计数据结构的设计典型的数据结构典型的数据结构-“树树”示例示例另一种存储结构另一种存储结构,用两个指针用两个指针(左指针左指针和和右指针右指针)表达数据之间的逻辑关系表达数据之间的逻辑关系数据的逻辑结构数据的逻辑结构150120160503070100数据的逻辑结构数据的逻辑结构110Null动手练习一下动手练习一下26/55u向量向量或列表列表或数组数组。u矩阵矩阵或表表向向量量实实例例n=4;Sum=0;For J=0 to n Step 1 Sum=Sum+mark J;Next JAvg=Sum/n;多
24、元素变量及其程序处理多元素变量及其程序处理(前讲介绍的前讲介绍的)3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.4 多元素变量结构是怎样的多元素变量结构是怎样的?112522254539844212801003483751612341234行行列列M2,3表表实实例例Sum=0;For I=1 to 4 Step 1 For J=1 to 4 Step 1 Sum=Sum+MIJ;Next J Next I Avg=Sum/16;27/55u数据结构设计就是针对选定的算法策略，设计其相应的数据结构及数据结构设计就是针对选定的算法策略，设计其相应的数据结构及其运算规则。不同的算法
25、可能有不同的数据结构及其运算规则！其运算规则。不同的算法可能有不同的数据结构及其运算规则！城市映射为编号:A-1,B-2,C-3,D-4城市间距离关系:表或二维数组D，用Dij或Di,j来确定欲处理的每一个元素访问路径/解:一维数组S，用Sj来确定每一个元素1432A-D-C-B-ASS1 S2 S3 S4DD233.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.5 一个问题中应该设计哪些数据结构一个问题中应该设计哪些数据结构?TSP问题的数据结构设计问题的数据结构设计28/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂3.算法设计算法设计-算法思想的精确表达算法思想的精
26、确表达算法设计算法设计-算法思想的精确表达算法思想的精确表达(II)-算法的数据结构设计算法的数据结构设计-算法的控制结构设计及其表达方法算法的控制结构设计及其表达方法-TSP算法解读算法解读29/55顺序结构顺序结构：“执行执行A，然后执行，然后执行B”，是按顺序执行一条条规则的一种结构。分支结构分支结构：“如果如果Q成立，那么执行成立，那么执行A，否则执行，否则执行B”，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则的一种结构。循环结构循环结构：控制指令或规则的多次执行的一种结构-迭代(iteration)u循环结构又分为有界循环结构和条件循环结构。有界循环有界循环：“执行执行A指令指
27、令N次次”，其中N是一个整数。条件循环条件循环：某些时候称为无界循环，“重复执行重复执行A直到条件直到条件Q成立成立”或“当当Q成立时反复执行成立时反复执行A”，其中Q是条件。算法与程序的基本控制结构算法与程序的基本控制结构3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.6 怎样表达算法的步骤呢怎样表达算法的步骤呢?30/55流程图流程图的基本表示符号的基本表示符号矩形框矩形框：表示一组顺序执行的规则或者程序语句。菱形框菱形框：表示条件判断，并根据判断结果执行不同的分支。圆形框圆形框：表示算法或程序的开始或结束。箭头线箭头线：表示算法或程序的走向。算法与程序构造的表达方法：程序流
28、程图算法与程序构造的表达方法：程序流程图3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.7 怎样绘制流程图怎样绘制流程图?31/55u三种控制结构的流程图表示方法示意开始第1条规则或语句第n条规则或语句结束顺序结构的流程图开始条件条件成立否？是否条件成立成立时执行的规则或语句结束条件不成立不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化初始化部分开始循环控制循环控制条件条件成立？修改修改部分需循环执行的规则或语句。即：循环体循环体结束是否循环结束3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.7 怎样绘制流程图怎样绘制流程图?算法与程序构造的表达方法：
29、程序流程图算法与程序构造的表达方法：程序流程图32/55u循环结构的两种情况的流程图表示方法示意初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束是否循环结束有界循环结构的流程图(循环次数确定)初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束否循环未结束是条件循环结构的流程图(循环次数不确定)3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.7 怎样绘制流程图怎样绘制流程图?算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图33/55u算法思想及算法流程图表示示例u欧几里德算法流程图3.算法设计算法设计-算法思想的精确表达算法
30、思想的精确表达3.7 怎样绘制流程图怎样绘制流程图?算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图34/55u步骤描述法，即用人们日常使用的语言和数学语言描述算法的步骤。u例如：sum=1+2+3+4+n求和问题的算法描述Start of the algorithm(算法开始)(1)输入输入N的值；的值；(2)设设 i 的值为的值为1；sum的值为的值为0；(3)如果如果 i=N，则执行第，则执行第(4)步，否则转到第步，否则转到第(7)步执行；步执行；(4)计算计算 sum+i，并将结果赋给，并将结果赋给sum；(5)计算计算 i+1，并将结果赋给，并将结果赋给i;
31、(6)返回到第返回到第3步继续执行；步继续执行；(7)输出输出sum的结果。的结果。End of the algorithm(算法结束)3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.8 自然语言表述算法有什么问题自然语言表述算法有什么问题?算法与程序构造的表达方法：步骤描述法算法与程序构造的表达方法：步骤描述法自然语言表示的算法容易出现二义性、不确定性等问题自然语言表示的算法容易出现二义性、不确定性等问题35/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂3.算法设计算法设计-算法思想的精确表达算法思想的精确表达算法设计算法设计-算法思想的精确表达算法思想的精确表达(
32、III)-算法的数据结构设计算法的数据结构设计-算法的控制结构设计及其表达方法算法的控制结构设计及其表达方法-TSP算法解读算法解读36/55求解求解TSP问题的遍历算法问题的遍历算法遍历所有的组合路径；累加一条路径的距离之和；判断某条路径的距离是不是比当前最短路径距离短；如果是，则用新路径取代当前最短路径，并记录其距离；直到所有路径比较完毕；u当前最短路径设为空，当前最短距离设为最大值开始所有路径组合完毕否？结束否是组合一条新路径并计算该路径的距离比当前最短距离小吗？将该路径记录为当前最短路径，并用其距离值更新当前最短距离输出当前最短路径及当前最短距离是否3.算法设计算法设计-算法思想的精确
33、表达算法思想的精确表达3.9 算法的控制结构如何设计算法的控制结构如何设计?将思想将思想/策略策略转变为转变为“步骤步骤”37/55步骤描述法表示的求解步骤描述法表示的求解TSP问题的贪心算法问题的贪心算法城市用数字编号来表示,1,2,N任何两个城市的距离记录在数组Di,j中依次访问过的城市编号被记录在S1,S2,SN中,即第i 次访问的城市记录在Si中。Step(1)：从第1个城市开始访问起，将城市编号1赋值给S1。Step(6)：第I次访问的城市为城市j，其距第I-1次访问城市的距离最短。3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.9 算法的控制结构如何设计算法的控制结构
34、如何设计?Start of the Algorithm(1)S1=1;(2)Sum=0;(3)初始化距离数组初始化距离数组DN,N;(4)I=2;(5)从所有未访问过的城市中查找距离从所有未访问过的城市中查找距离SI-1最近的城市最近的城市j;(6)SI=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果如果I=N，转步骤，转步骤(5)，否则，转步，否则，转步骤骤(10);(11)Sum=Sum+D1,j；(12)逐个输出逐个输出SN中的全部元素中的全部元素;(13)输出输出Sum。End of the Algorithm38/55步骤描述法表示的求解步骤描述法表示的求解TSP
35、问题的贪心算法问题的贪心算法(Cont.)u前述第5步“从所有未访问过的城市中查找距离SI-1最近的城市j”还是不够明确，需要进一步细化3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.9 算法的控制结构如何设计算法的控制结构如何设计?(5.1)K=2;(5.2)将将Dtemp设为一个大数设为一个大数(比所有两个城市之间的距离都大比所有两个城市之间的距离都大)(5.3)L=1；(5.4)如果如果SL=K，转步骤，转步骤5.8；/该城市已出现过，跳过该城市已出现过，跳过(5.5)L=L+1；(5.6)如果如果LI，转，转5.4；(5.7)如果如果DK,SI-1Dtemp;j=K;Dt
36、empDK,SI-1；(5.8)K=K+1;(5.9)如果如果K=N，转步骤，转步骤5.3。39/55数学建模与算法策略设计-算法思想径大小不一的金盘子按照从大到小的顺序依次套放将现实世界的问题抽象成数学模型，就可能发现问题的本质及其能否求解，甚至找到求解该问题的方法和算法。如果R不是0，将N的值赋给M,R的值赋给N,返回Step 1;否则,最大公约数是N,输出N,算法结束。如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；数学建模：是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立对问题进行精确
37、描述和定义的数学模型。TSP问题的贪心算法求解思想条件不成立时执行的规则或语句2 什么是数据结构?分支结构：“如果Q成立，那么执行A，否则执行B”，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则的一种结构。S1 S2 S3 S4算法设计-算法思想的精确表达TSP问题贪心算法程序实例(12)逐个输出SN中的全部元素;算法与程序构造的表达方法：步骤描述法Next J(5)计算 i+1，并将结果赋给i;程序设计过程：一般经过编辑源程序编译链接执行。流程图表示的求解流程图表示的求解TSP问题的问题的贪心算法贪心算法3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.9 算法的控制结构如何
38、设计算法的控制结构如何设计?40/55算法思想解读算法思想解读u计算学科的学生不仅能够计算学科的学生不仅能够设计算法，而且会描述和表设计算法，而且会描述和表达算法，更要能读懂算法。达算法，更要能读懂算法。外层循环，I从2至N循环；I-1个城市已访问过，正在找与第I-1个城市最近距离的城市；已访问过的城市号存储在S中。中层循环,K从第2个城市至第N个城市循环,判断DK,SI-1是否是最小值，j记录了最小距离的城市号K。内层循环，L从1至I-1,循环判断第K个城市是否是已访问过的城市，如是则不参加最小距离的比较；3.算法设计算法设计-算法思想的精确表达算法思想的精确表达3.10 你能够读懂流程图吗
39、你能够读懂流程图吗?41/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂4.算法实现算法实现-程序设计程序设计算法实现算法实现-程序设计程序设计42/55一个盘子，盘子只能在三根柱子上来回移动不能放数学建模与算法策略设计-算法思想算法设计-算法思想的精确表达列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线-算法的数据结构设计TSP问题贪心算法程序实例TSP问题贪心算法的效果评价：循环结构的两种情况的流程图表示方法示意算法设计-算法思想的精确表达访问路径/解:一维数组S，用Sj来确定每一个元素算法的实现算法的实现u程序程序是算法的一种机器相容(Compati
40、ble)的表示，是利用计算机程序设计语言对算法描述的结果，是可以在计算机上执行的算法。u计算机语言计算机语言是书写算法步骤地规范、标准、语法规则等，以便使人和计算机能够理解用计算机语言编写出的程序(注：更重要的是使计算机能够理解)。4.算法实现算法实现-程序设计程序设计4.1 算法实现要选定计算机语言，你知道吗算法实现要选定计算机语言，你知道吗?43/55u程序设计过程程序设计过程：一般经过编辑源程序编译链接执行。所谓编辑源程序是利用程序编辑器，按照计算机语言的规范书写程序的过程；所谓编译是将编制好的源程序翻译成机器可以执行的机器代码程序(又称为目标代码)的过程。所谓链接是将目标代码与公用函数
41、库中的函数实现代码集成起来形成最终可执行程序的过程。所谓执行就是程序的运行过程。u计算机语言程序设计环境计算机语言程序设计环境通常由一套书写程序的语法规则、一个编译程序、一个链接程序和一组编译好的公用函数库构成。有些计算机语言同时也提供了相应的编程环境、调试环境及集成开发环境等。算法的实现算法的实现4.算法实现算法实现-程序设计程序设计4.1 算法实现要选定计算机语言，你知道吗算法实现要选定计算机语言，你知道吗?44/55TSP问题贪心问题贪心算法程序实例算法程序实例算法的实现算法的实现4.算法实现算法实现-程序设计程序设计4.2 你能用某一种计算机语言书写出你能用某一种计算机语言书写出TSP
42、问题问题贪心算法的程序吗贪心算法的程序吗?45/55算法：程序与计算系统之灵魂算法：程序与计算系统之灵魂5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性46/55算法分析与计算复杂性算法分析与计算复杂性u算法的模拟与分析算法的模拟与分析u算法的正确性问题：问题求解的过程、方法算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中u算法的效果评价：算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大如果是可行解，与最优解
43、的偏差多大？u两种评价方法：证明方法证明方法：利用数学方法证明；仿真分析方法仿真分析方法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.1 算法是正确的吗算法是正确的吗?算法是正确的吗算法是正确的吗?算法获得的解是最优的吗算法获得的解是最优的吗?47/55算法分析示例：算法分析示例：TSP问题贪心算法的模拟与分析问题贪心算法的模拟与分析uTSP问题贪心算法的正确性评价：问题贪心算法的正确性评价：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是
44、TSP问题的可行解，说明算法正确地求解了这些问题实例uTSP问题贪心算法的效果评价：问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.1 算法是正确的吗算法是正确的吗?算法分析与计算复杂性算法分析与计算复杂性48/55u另一个问题：算法是能够执行的吗算法是能够执行的吗？u算法的复杂性分析算法的复杂性分析u算法的效率算法
45、的效率：时间效率和空间效率u时间复杂性时间复杂性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。u“大大O记法记法”：基本参数 n问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“”，如n2+n+1=(n2)。u算法的空间复杂度算法的空间复杂度：算法在执行过程中所占存储空间的大小。5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.2 算法的计算时间有多长算法的计算时间有多长?算法分析与计算复杂性算法分析与计算复杂性算法获得结果的时间有多长算法获得
46、结果的时间有多长?49/555.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.2 算法的计算时间有多长算法的计算时间有多长?算法分析与计算复杂性算法分析与计算复杂性算法复杂性分析示例算法复杂性分析示例sum=0；（1次）次）for(i=1;i=n;i+)（n次）次）for(j=1;j=n;j+)（n2次）次）sum+；（n2次）次）解解：T(n)=2n2+n+1=O(n2)主要关注点：循环的层数主要关注点：循环的层数50/55算法复杂性分析示例：算法复杂性分析示例：TSP问问题算法的复杂性题算法的复杂性uTSP问题遍历算法遍历算法的复杂性：列出每一条可供选择的路线，计算
47、出每条路线的总里程，最后从中选出一条最短的路线组合爆炸：路径组合数目为(n-1)!时间复杂度是O(n-1)!)uTSP问题贪心算法贪心算法的复杂性：粗略看是一个关于n的三重循环，即复杂度为n3级别。时间复杂度是O(n3)。5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.2 算法的计算时间有多长算法的计算时间有多长?算法分析与计算复杂性算法分析与计算复杂性nn2n351/555.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.2 O(n3),O(n!)和和O(3n)差别有多大差别有多大?算法分析与计算复杂性算法分析与计算复杂性问题规模n计算量10
48、10！20 20！100 100！1000 1000！10000 10000！20！=1.2161017203 =8000O(n3)O(3n)0.2秒秒4 1028秒秒=1015年年注：每秒百万次，n=60，1015年相当于10亿台计算机计算一百万年O(n3)与与O(3n)的差别，的差别，O(n!)与与O(n3)的差别的差别52/55u难解性问题难解性问题u当算法的时间复杂度的表示函数是一个多项式时，如O(n2)时，则计算机对于大规模问题是可以处理的。例如，TSP问题的贪心算法 O(n3)。u当算法的时间复杂度是用指数函数表示时，如O(2n)，当n很大（如10000）时计算机是无法处理的，在计算复杂性中将这一类问题被称为难解性问题难解性问题。例如，TSP问题的遍历算法。u计算复杂性理论计算复杂性理论u所有可以在多项式时间内求解的问题称为P类问题u所有在多项式时间内可以验证的问题称为NP类问题，PNP。uOpen problem:P=NP?美国克雷数学研究所百万大奖难题。5.高级问题初探高级问题初探:算法分析与计算复杂性算法分析与计算复杂性5.3 算法的计算时间有多长算法的计算时间有多长?算法分析与计算复杂性算法分析与计算复杂性53/55本讲小结本讲小结基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架
