大学计算机第7讲-算法-程序与计算系统之灵魂.ppt

算法与算法类问题求解算法与算法类问题求解ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员战德臣 教授符号化符号化,计算化计算化再语再语义化义化自然自然/社社会问题会问题程序化程序化执行化执行化算法的结果算法的结果机器级程序机器级程序-机器指令机器指令运算器和控制运算器和控制器器(CPU)-执行执行算法算法自然自然/社社会问题的会问题的求解结果求解结果产生产生用用0/1编码：指编码：指令和数据令和数据存储器：存储器：0/1存与取存与取0/1化化信号化信号化存储存储高级语言程序高级语言程序编译编译执行化执行化汇编语言程序汇编语言程序程序执行程序执行汇编汇编程序执行程序执行算法与算法类问题求解算法与算法类问题求解(1)为什么算法很重要呢为什么算法很重要呢?“是否会编程序是否会编程序”，本质上是，本质上是“能否想出求解问题的算法能否想出求解问题的算法”，其次才是将算法用计算机可以识别的形式书写出来其次才是将算法用计算机可以识别的形式书写出来战德臣 教授算法算法-计算机与软件的灵魂。“算法算法”(Algorithm)一词源于数学家的名字：公一词源于数学家的名字：公元元825年，阿拉伯数学家阿科瓦里茨米年，阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的写了著名的波斯教科书波斯教科书(PersianTextbook)，书中概括了进行四则算术运算的计算规则，书中概括了进行四则算术运算的计算规则。u算法算法是一个是一个有穷规则有穷规则的集合，它用规则规定了解决某一特定的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。列步骤。算法与算法类问题求解算法与算法类问题求解(2)什么是算法什么是算法?如音乐乐谱、太极拳谱等都可看作广义的算法如音乐乐谱、太极拳谱等都可看作广义的算法战德臣 教授有有穷穷性性：一个算法在执行有穷步规则之后必须结束。确确定定性性：算法的每一个步骤必须要确切地定义，不得有歧义性。输入输入：算法有零个或多个的输入。输输出出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。能能行行性性：算法中有待执行的运算和操作必须是相当基本的(可可以以由由机机器器自自动动完完成成)，并能在有限时间内完成。算法算法算法与算法类问题求解算法与算法类问题求解(3)什么是计算学科中的算法什么是计算学科中的算法?基本运算：除法、赋值、逻辑判断基本运算：除法、赋值、逻辑判断典型的典型的“重复重复/循环循环”与与“迭代迭代”寻找两个正整数的最大寻找两个正整数的最大公约数的欧几里德算法公约数的欧几里德算法输入输入：正整数：正整数M和正整数和正整数N输出输出：M和和N的最大公约数的最大公约数(设设MN)算法步骤算法步骤：Step1.M除以除以N,记余数为记余数为RStep2.如果如果R不是不是0，将将N的值赋给的值赋给M,R的值赋给的值赋给N,返回返回Step1;否则否则,最大最大公约数是公约数是N,输出输出N,算法结束。算法结束。战德臣 教授哥尼斯堡七桥问题哥尼斯堡七桥问题：“寻找走遍这7座桥且只许走过每座桥一次最后又回到原出发点的路径”“对给定的任意一个河道图与任意多座桥判定可能不可能每座桥恰好走过一次?”。梵天塔问题梵天塔问题：有三根柱子，梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上形成一座金塔，要求每次只能移动一个盘子，盘子只能在三根柱子上来回移动不能放在他处，在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上。其他如：背包问题背包问题，丢番图方程可丢番图方程可解性问题解性问题；算法与算法类问题求解算法与算法类问题求解(4)你知道一些典型的算法类问题吗你知道一些典型的算法类问题吗?算法类问题：由一个算法可以解决的问题,寻找一个(唯一的)方法(算法)以解决同一类型的无穷多个单个问题系列的问题战德臣 教授uTSP问题(TravelingSalesmanProblem，旅旅行行商商问问题题)，威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman 于19世纪初提出TSP问题uTSP问问题题：有有若若干干个个城城市市，任任何何两两个个城城市市之之间间的的距距离离都都是是确确定定的的，现现要要求求一一旅旅行行商商从从某某城城市市出出发发必必须须经经过过每每一一个个城城市市且且只只能能在在每每个个城城市市逗逗留留一一次次，最最后后回回到到原原出出发发城城市市，问问如如何何事事先先确确定定好好一一条条最最短短的的路路线线使使其其旅旅行行的的费费用用最少。最少。uTSP是最有代表性的组合优化组合优化问题之一，在半导体制造(线路规划)、物流运输(路径规划)等行业有着广泛的应用。城市之间的距离城市之间的距离算法与算法类问题求解算法与算法类问题求解(5)你知道你知道TSP问题吗问题吗?算法类问题示例战德臣 教授u问问题题抽抽象象及及数数学学建建模模：将问题抽象为一个数学问题，并给出求解该数学问题的算法模型。u算法策略设计算法策略设计u算算法法的的数数据据结结构构和和控控制制结结构构设设计计：将数学模型转换为可由计算机自动计算的算法。u算算法法的的实实现现：用程序设计语言编写算法实现的程序。u算算法法的的分分析析：分析算法的正确性和复杂性，判断能行性！算法与算法类问题求解算法与算法类问题求解(6)你知道算法类问题求解的一般步骤吗你知道算法类问题求解的一般步骤吗?算法类问题求解框架数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员战德臣 教授算法类问题求解的第一步就是要数学建模。算法类问题求解的第一步就是要数学建模。u数数学学建建模模是是用用数数学学语语言言描描述述实实际际现现象象的的过过程程，即建立数学模型的过程。u数数学学模模型型是是对对实实际际问问题题的的一一种种数数学学表表述述，是是关关于于部部分分现现实实世界为某种目的的一个抽象的简化的数学结构。世界为某种目的的一个抽象的简化的数学结构。数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(1)为什么说数学建模对于算法很重要为什么说数学建模对于算法很重要?将现实世界的问题抽象成数学模型，就可能发现问题的本将现实世界的问题抽象成数学模型，就可能发现问题的本质及其能否求解，甚至找到求解该问题的方法和算法。质及其能否求解，甚至找到求解该问题的方法和算法。战德臣 教授哥哥 尼尼 斯斯 堡堡 七七 桥桥 问问 题题被 抽 象 成 一 个“图图(Graph)”-由节点和边所构成的一种结构，-依据“图”，可发现该问题所蕴含的许多性质：u“连通连通-两个节点间有路径相连接”u“回回路路-从一个节点出发最后又回到该节点的一条路径”u“可达可达-从一个节点出发能够到达另一个节点”u“经过图中每边一次且仅一次的回路经过图中每边一次且仅一次的回路”u“经过图中每个节点一次且仅一次的回路”u什么情况下有解，什么情况下无解？什么情况下有解，什么情况下无解？数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(1)为什么说数学建模对于算法很重要为什么说数学建模对于算法很重要?如果能抽象成数学模型，则可将一个具体问题的求解，推广为一类如果能抽象成数学模型，则可将一个具体问题的求解，推广为一类问题的求解！问题的求解！战德臣 教授TSP问题的数学模型问题的数学模型数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(2)数学建模要做到怎样数学建模要做到怎样?战德臣 教授算法策略设计算法策略设计-算法思想算法思想当数学建模完成后，就要设计算法的策略或者说问题求解的策略。当数学建模完成后，就要设计算法的策略或者说问题求解的策略。u求解TSP的遍遍历历算算法法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线。u出现的问题是出现的问题是：组合爆炸组合爆炸路径组合数目：(n-1)!20个城市，遍历总数1.2161017计算机以每秒检索1000万条路线的计算速度，需386年。所有路径组所有路径组合及其长度合及其长度城市之间的距离城市之间的距离数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(3)算法思想或者算法策略对问题求解有什么影响算法思想或者算法策略对问题求解有什么影响?战德臣 教授uTSP问问题题的的难难解解性性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。u2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台台计计算算机机，所有计算机花费的时间之和为22.6年年。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)算法思想或者算法策略对问题求解有什么影响算法思想或者算法策略对问题求解有什么影响?战德臣 教授TSP问题，有没有其他求解算法呢？问题，有没有其他求解算法呢？u最优解最优解 vs.可行解可行解u不同的算法设计策略：不同的算法设计策略：遍历、搜索算法遍历、搜索算法分治算法分治算法贪心算法贪心算法动态规划算法动态规划算法可行解最优解TSP问题的可行解与最优解示意数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(4)有哪些算法策略有哪些算法策略?战德臣 教授贪贪心心算算法法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。一一定定要要做做当当前前情情况况下下的的最最好好选选择择，否否则则将将来可能会后悔，故名来可能会后悔，故名“贪心贪心”。uTSP问题的贪心算法求解思想从某一个城市开始，每次选择一个城市，直到所有城市都被走完。每每次次在在选选择择下下一一个个城城市市的的时时候候，只只考考虑虑当当前前情情况况，保保证证迄迄今今为为止止经经过过的的路路径径总总距距离离最短。最短。城市之间的距离城市之间的距离数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(5)为什么称为为什么称为“贪心算法贪心算法”?战德臣 教授基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架数学建模与算法策略设计数学建模与算法策略设计-算法思想算法思想(6)小结小结?算法思想的精确表达算法思想的精确表达-算法算法的数据结构的数据结构设计设计(I)ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员战德臣 教授算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(1)算法设计包括什么算法设计包括什么?n算法的数据结构设计算法的数据结构设计-问题或算法相关的数据之间的逻辑关问题或算法相关的数据之间的逻辑关系及存储关系的设计系及存储关系的设计n算法的控制结构设计算法的控制结构设计-算法的计算规则或计算步骤设计算法的计算规则或计算步骤设计如何如何构造和表达构造和表达处理的规则，以便能够按规则逐步计算出结果处理的规则，以便能够按规则逐步计算出结果?如何将数学模型中的数据转为计算机可以存储和处理的数据？如何将数学模型中的数据转为计算机可以存储和处理的数据？战德臣 教授数数据据结结构构是是数数据据的的逻逻辑辑结结构构、存存储储结结构构及及其其操操作作的的总总称称，它它提供了问题求解提供了问题求解/算法的数据操纵机制。算法的数据操纵机制。算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(2)什么是数据结构什么是数据结构?(数据的数据的)逻辑结构逻辑结构(数据的数据的)存储结构存储结构操操作作反映逻辑语义关系反映逻辑语义关系为便于计算系统处理为便于计算系统处理战德臣 教授l变量与存储单元变量与存储单元 算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(3)变量和存储单元之间的关系变量和存储单元之间的关系?变量及其存储变量及其存储战德臣 教授l“变量变量”与与“指针变量指针变量”算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(4)指针是什么指针是什么?*p变量及其存储变量及其存储战德臣 教授l“变量变量”与与“变量类型变量类型”及其存储及其存储算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(5)变量为什么需要声明类型变量为什么需要声明类型?变量及其存储变量及其存储战德臣 教授u向向量量或列列表表是有序数据的集合型变量，向量中的每一个元素都属于同一个数据类型，用一个统一的向量名和下标来唯一的确定向量中的元素。在程序设计语言中，又称为数组数组。u向量名通常表示该向量的起始存储地址，而向量下标表示所指向元素相对于起始存储地址的偏移位置。向量实例向量实例向量存储实例向量存储实例n=4;Sum=0;ForJ=0tonStep1 Sum=Sum+markJ;NextJAvg=Sum/(n+1);算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(6)如何控制读取向量如何控制读取向量/数组型变量的不同元素数组型变量的不同元素?多元素变量及其存储多元素变量及其存储多元素变量使得程序可通过下标来操作多元素变量中的每一个元素多元素变量使得程序可通过下标来操作多元素变量中的每一个元素编写求上述数组中值的平均值的程序编写求上述数组中值的平均值的程序战德臣 教授u矩矩阵阵或表表是按行按列组织数据的集合型变量，通常是一个二维向量，可表示为如M2,3或M23形式，即用符号名加两个下标来唯一确定表中的一个元素，前一下标为行序号，后一下标为列序号。系统会自动将其转换为对应的存储地址，找到相应的存储单元。在程序设计语言中，矩阵或表是一个多维数组变量。112522254539844212801003483751612341234行列M2,3表实例Sum=0;ForI=1to4Step1ForJ=1to4Step1Sum=Sum+MIJ;NextJNextIAvg=Sum/16;算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(I)(7)如何控制读取向量如何控制读取向量/数组型变量的不同元素数组型变量的不同元素?多元素变量及其存储多元素变量及其存储逻辑上是二维的按行、列下标来操作一个元素逻辑上是二维的按行、列下标来操作一个元素,如如M2,3或或M23；物理上仍旧是一；物理上仍旧是一维存储的，由维存储的，由“表起始地址表起始地址+(行下标行下标-1)*列数列数+列下标列下标”。这种转换可由系统自动完成，。这种转换可由系统自动完成，程序中只需按下标操作即可，即如程序中只需按下标操作即可，即如M23算法思想的精确表达算法思想的精确表达-算法算法的数据结构的数据结构设计设计(II)ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员战德臣 教授算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(II)(1)数据结构示例数据结构示例?典型的数据结构典型的数据结构-“树树”“树”的存储结构存储结构:一个存储单元存储“数据元素”；一个存储单元存储“指针”，指示数据元素之间的逻辑关系150120160数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构503070100数据元素数据元素对应数据元素的对应数据元素的指针指针指向该元指向该元素的父元素素的父元素战德臣 教授150120160503070100数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构存储结构中，通过指针的变化存储结构中，通过指针的变化,不改变数据元素的存储不改变数据元素的存储,但却但却改变了数据元素之间的逻辑关系改变了数据元素之间的逻辑关系算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(II)(1)数据结构示例数据结构示例?120战德臣 教授150120160503070100数据元素数据元素对应数据元素的左对应数据元素的左指针指针指向该元素指向该元素的左侧子结点的左侧子结点对应数据元素的右对应数据元素的右指针指针指向该元素指向该元素的右侧子结点的右侧子结点算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(II)(2)同同样的逻辑结构可以有不同的存储结构吗样的逻辑结构可以有不同的存储结构吗?“树”的另一种存储结构存储结构,用两个指针表达数据之间的逻辑关系，一个指向其左数据元素，一个指向其右数据元素。数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据结构不同，数据之间的操作方法也是不同的数据结构不同，数据之间的操作方法也是不同的战德臣 教授150120160503070100算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(II)(2)同样的逻辑结构可以有不同的存储结构吗同样的逻辑结构可以有不同的存储结构吗?数据的逻辑结构数据的逻辑结构150120160503070100数据的逻辑结构数据的逻辑结构110Null动手练习一下动手练习一下战德臣 教授u数数据据结结构构设设计计就就是是针针对对选选定定的的算算法法策策略略，设设计计其其相相应应的的数数据据结结构构及及其其运算规则。不同的算法可能有不同的数据结构及其运算规则！运算规则。不同的算法可能有不同的数据结构及其运算规则！城市映射为编号:A-1,B-2,C-3,D-4城市间距离关系:表或二维数组D，用Dij或Di,j来确定欲处理的每一个元素访问路径/解:一维数组S，用Sj来确定每一个元素1432A-D-C-B-ASS1 S2 S3 S4DD23算法设计算法设计-算法思想的精确表达算法思想的精确表达(II)(3)一个问题中应该设计哪些数据结构一个问题中应该设计哪些数据结构?TSP问题的数据结构设计问题的数据结构设计战德臣 教授基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架算法思想的精确表达算法思想的精确表达-算法的数据结构设计算法的数据结构设计(II)(4)小结小结?ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员算法思想的精确表达算法思想的精确表达-算法算法的控制结构的控制结构设计设计(I)战德臣 教授算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(1)算法设计包括什么算法设计包括什么?n算法的数据结构设计算法的数据结构设计-问题或算法相关的数据之间的逻辑关问题或算法相关的数据之间的逻辑关系及存储关系的设计系及存储关系的设计n算法的控制结构设计算法的控制结构设计-算法的计算规则或计算步骤设计算法的计算规则或计算步骤设计如何如何构造和表达构造和表达处理的规则，以便能够按规则逐步计算出结果处理的规则，以便能够按规则逐步计算出结果?如何将数学模型中的数据转为计算机可以存储和处理的数据？如何将数学模型中的数据转为计算机可以存储和处理的数据？战德臣 教授顺顺序序结结构构：“执执行行A，然然后后执执行行B”，是按顺序执行一条条规则的一种结构。分分支支结结构构：“如如果果Q成成立立，那那么么执执行行A，否否则则执执行行B”，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则的一种结构。循环结构循环结构：控制指令或规则的多次执行的一种结构-迭代(iteration)u循环结构又分为有界循环结构和条件循环结构。有界循环有界循环：“执行执行A指令指令N次次”，其中N是一个整数。条条件件循循环环：某些时候称为无界循环，“重重复复执执行行A直直到到条条件件Q成成立立”或“当当Q成立时反复执行成立时反复执行A”，其中Q是条件。算法与程序的基本控制结构算法与程序的基本控制结构算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(2)怎样表达算法的步骤呢怎样表达算法的步骤呢?战德臣 教授流程图流程图的基本表示符号的基本表示符号矩矩形形框框：表示一组顺序执行的规则或者程序语句。菱菱形形框框：表示条件判断，并根据判断结果执行不同的分支。圆形框圆形框：表示算法或程序的开始或结束。箭头线箭头线：表示算法或程序的走向。算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(3)怎样绘制算法或程序流程图怎样绘制算法或程序流程图?战德臣 教授u三种控制结构的流程图表示方法示意三种控制结构的流程图表示方法示意开始第1条规则或语句第n条规则或语句结束顺序结构的流程图开始条件条件成立否？是否条件成立成立时执行的规则或语句结束条件不成立不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化初始化部分开始循环控制循环控制条件条件成立？修改修改部分需循环执行的规则或语句。即：循环体循环体结束是否循环结束算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(4)不同结构的流程图示例不同结构的流程图示例?算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图战德臣 教授u循环结构的两种情况的流程图表示方法示意循环结构的两种情况的流程图表示方法示意初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束是否循环结束有界循环结构的流程图(循环次数确定)初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句结束否循环未结束是条件循环结构的流程图(循环次数不确定)算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(4)不同结构的流程图示例不同结构的流程图示例?战德臣 教授u欧几里德算法流程图欧几里德算法流程图算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(5)算法流程图示例算法流程图示例?算法与程序构造的表达方法：程序流程图算法与程序构造的表达方法：程序流程图战德臣 教授u步骤描述法，即用人们日常使用的语言和数学语言描述算法的步骤。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;(6)返回到第返回到第3步继续执行；步继续执行；(7)输出输出sum的结果。的结果。End of the algorithm(算法结束)算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(I)(6)自然语言表述算法有什么问题自然语言表述算法有什么问题?算法与程序构造的表达方法：步骤描述法算法与程序构造的表达方法：步骤描述法自然语言表示的算法容易出现二义性、不确定性等问题自然语言表示的算法容易出现二义性、不确定性等问题ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员算法思想的精确表达算法思想的精确表达-算法算法的控制结构的控制结构设计设计(II)战德臣 教授求解求解TSP问题的遍历算法问题的遍历算法遍历所有的组合路径；累加一条路径的距离之和；判断某条路径的距离是不是比当前最短路径距离短；如果是，则用新路径取代当前最短路径，并记录其距离；直到所有路径比较完毕；u当前最短路径设为空，当前最短距离设为最大值开始所有路径组合完毕否？结束否是组合一条新路径并计算该路径的距离比当前最短距离小吗？将该路径记录为当前最短路径，并用其距离值更新当前最短距离输出当前最短路径及当前最短距离是否算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(1)具体算法具体算法-TSP的遍历算法的控制结构如何设计的遍历算法的控制结构如何设计?将思想将思想/策略策略转变为转变为“步骤步骤”战德臣 教授步骤描述法表示的求解步骤描述法表示的求解TSP问题的贪心算法问题的贪心算法城市用数字编号来表示,1,2,N任何两个城市的距离记录在数组Di,j中依次访问过的城市编号被记录在S1,S2,SN中,即第i 次访问的城市记录在Si中。Step(1)：从第1个城市开始访问起，将城市编号1赋值给S1。Step(6)：第I次访问的城市为城市j，其距第I-1次访问城市的距离最短。算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(2)具体算法具体算法-TSP问题的贪心算法的控制结构如何设计问题的贪心算法的控制结构如何设计?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 Algorithm战德臣 教授步骤描述法表示的求解步骤描述法表示的求解TSP问题的贪心算法问题的贪心算法(Cont.)u前述第5步“从所有未访问过的城市中查找距离SI-1最近的城市j”还是不够明确，需要进一步细化(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;DtempDK,SI-1；(5.8)K=K+1;(5.9)如果如果K=N，转步骤，转步骤5.3。算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(2)具体算法具体算法-TSP问题的贪心算法的控制结构如何设计问题的贪心算法的控制结构如何设计?战德臣 教授流流程程图图表表示示的的求求解解TSP问问题题的的贪心算法贪心算法算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(3)具体算法具体算法-TSP问题的贪心算法的算法流程图问题的贪心算法的算法流程图?战德臣 教授算法思想解读算法思想解读u计计算算学学科科的的学学生生不不仅仅能能够够设设计计算算法法，而而且且会会描描述述和和表表达算法，更要能读懂算法。达算法，更要能读懂算法。外层循环，I从2至N循环；I-1个城市已访问过，正在找与第I-1个城市最近距离的城市；已访问过的城市号存储在S中。中层循环,K从第2个城市至第N个城市循环,判断DK,SI-1是否是最小值，j记录了最小距离的城市号K。内层循环，L从1至I-1,循环判断第K个城市是否是已访问过的城市，如是则不参加最小距离的比较；算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(4)你能够读懂流程图吗你能够读懂流程图吗?战德臣 教授基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架算法思想的精确表达算法思想的精确表达-算法的控制结构设计算法的控制结构设计(II)(5)小结小结?ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员算法的实现算法的实现-程序程序设计设计战德臣 教授算法的实现算法的实现u程程序序是算法的一种机器相容(Compatible)的表示，是利用计算机程序设计语言对算法描述的结果，是可以在计算机上执行的算法。算法的实现算法的实现-程序设计程序设计(1)算法实现要选定计算机语言，你知道吗算法实现要选定计算机语言，你知道吗?u程序设计过程程序设计过程：编辑源程序编辑源程序编译编译链接链接执行执行。一套书写程序一套书写程序的语法规则的语法规则计算机语计算机语言程序设言程序设计环境计环境：编辑、编编辑、编译、连接、译、连接、调试、运调试、运行一体化行一体化平台平台高级高级语言语言程序程序目标目标程序程序可执行可执行程序程序编辑编辑程序程序编译编译程序程序连接连接程序程序公用公用函数函数库库调试调试程序程序战德臣 教授SS0 S1 S2 S3K从从1,n-1是城市的编号是城市的编号I是至今已访问过的城市数是至今已访问过的城市数S0至至SI-1中存储的是已中存储的是已访问过的城市的编号访问过的城市的编号算法的实现算法的实现-程序设计程序设计(2)你能用某一种计算机语言书写出你能用某一种计算机语言书写出TSP问题问题贪心算法的程序吗贪心算法的程序吗?main()/前面已为前面已为 K 和和 I 赋过值赋过值L=0;Found=0;do if(SL=K)Found=1;break;else L=L+1;while(LI);/L从从1到到I循环循环 if Found=0 /城市城市K未出现过未出现过 else /城市城市K出现过出现过.判断城市判断城市K是否是已访问过的城市是否是已访问过的城市1432战德臣 教授SS0 S1 S2 S3K从从1,n-1是城市的编号是城市的编号I是至今已访问过的城市数是至今已访问过的城市数SI-1中存储的是当前访问中存储的是当前访问过的城市编号，要找第过的城市编号，要找第I个程个程序序算法的实现算法的实现-程序设计程序设计(2)你能用某一种计算机语言书写出你能用某一种计算机语言书写出TSP问题问题贪心算法的程序吗贪心算法的程序吗?main()K=1;Dtemp=10000;do /K从从1到到n-1循环循环 L=0;Found=0;do if(SL=K)Found=1;break;else L=L+1;while(LI);/L从从1到到I循环循环if(Found=0&DKSI-1Dtemp)j=K;Dtemp=DKSI-1;K=K+1;while(Kn);/K从从1到到n-1循环循环 SI=j;Sum=Sum+Dtemp;寻找下一个未访问过的城市寻找下一个未访问过的城市j,且其距当前访问城市且其距当前访问城市SI-1距离最短距离最短1432DKSI-1为城市为城市K距当距当前访问过的城市的距离前访问过的城市的距离战德臣 教授TSP问问 题题 贪贪 心心算法程序实例算法程序实例算法的实现算法的实现算法的实现算法的实现-程序设计程序设计(2)你能用某一种计算机语言书写出你能用某一种计算机语言书写出TSP问题问题贪心算法的程序吗贪心算法的程序吗?战德臣 教授基本目标基本目标:理解算法类问题求解框架理解算法类问题求解框架算法的实现算法的实现-程序设计程序设计(5)小结小结?ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学 教授.博士生导师教育部大学计算机课程教学指导委员会委员算法分析与计算复杂性算法分析与计算复杂性战德臣 教授u算法的模拟与分析算法的模拟与分析u算法的正确性问题：问题求解的过程、方法算法是正确的吗？算法的输出是问题的解吗？20世纪60年代，美国一架发往金星的航天飞机由于控制程序出错而永久丢失在太空中u算法的效果评价：算法的效果评价：算法的输出是最优解还是可行解？如果是可行解，与最优解的偏差多大如果是可行解，与最优解的偏差多大？u两种评价方法：证明方法证明方法：利用数学方法证明；仿仿真真分分析析方方法法：产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。算法分析与计算复杂性算法分析与计算复杂性(1)算法是正确的吗算法是正确的吗?算法是正确的吗算法是正确的吗?算法获得的解是最优的吗算法获得的解是最优的吗?战德臣 教授TSP问题贪心算法的模拟与分析问题贪心算法的模拟与分析uTSP问题贪心算法的正确性评价：问题贪心算法的正确性评价：直观上只需检查算法的输出结果中，每个城市出现且仅出现一次，该结果即是TSP问题的可行解，说明算法正确地求解了这些问题实例uTSP问题贪心算法的效果评价：问题贪心算法的效果评价：如果实例的最优解已知（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价；对于较大规模的问题实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法结果的比较。算法分析与计算复杂性算法分析与计算复杂性(1)算法是正确的吗算法是正确的吗?战德臣 教授u另一个问题：算法是能够执行的吗算法是能够执行的吗？u算法的复杂性分析算法的复杂性分析u算法的效率算法的效率：时间效率和空间效率u时时间间复复杂杂性性:如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称为这一算法的“时间复杂性”。u“大大O记法记法”：基本参数 n问题实例的规模把复杂性或运行时间表达为n的函数。“O”表示量级(order)，允许使用“=”代替“”，如n2+n+1=(n2)。u算法的空间复杂度算法的空间复杂度：算法在执行过程中所占存储空间的大小。算法分析与计算复杂性算法分析与计算复杂性(2)算法的计算时间有多长算法的计算时间有多长?算法获得结果的时间有多长算法获得结果的时间有多长?战德臣 教授算法分析与计算复杂性算法分析与计算复杂性(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)主要关注点：循环的层数主要关注点：循环的层数战德臣 教授TSP问题算法的复杂性分析问题算法的复杂性分析uTSP问题遍历算法遍历