第1章算法概述培训资料.ppt

计算机算法设计与分析郭艺辉广东金融学院计算机科学与技术系办公室:1622电话:**********,37215835Email:校内邮箱gdufguo@计算机算法设计与分析教材:计算机算法设计与分析-王晓东参考资料:算法设计与分析郑宗汉清华大学出版社计算机算法基础(第三版)余祥宣华中科技大学出版社算法设计与分析基础(第2版) 作者:(美)Levitin 译者: 潘彦  清华大学出版社主要章节介绍第1章 算法引论第2章 递归与分治策略第3章 动态规划第4章 贪心算法第5章 回溯法第6章 分支限界法第7章 概率算法第8章 NP完全性理论第9章 近似算法第10章 算法优化策略计算机算法设计与分析算法:是指解决问题的一种方法或一个过程。更严格地讲,算法是由若干条指令组成的又穷序列,且满足下述4条性质:输入:有零个或多个外部量作为算法的输入。输出:算法产生至少一个量作为输出。确定性:组成算法的每条指令清晰、无歧义。有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。百鸡问题公元前5世纪末,中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?百鸡问题算法A的程序代码如下:Forx=0To100Fory=0To100Forz=0To100If(x+y+z=100)And(5*x+3*y+z/3=100)(x)+""+Str(y)+""+Str(z)EndIfNextzNextyNextx算法的描述方法百鸡问题算法B程序代码如下:Forx=0 To 20Fory=0 To 33Z=100-x-yIf5*x+3*y+z/3=(x)+""+Str(y)+""+Str(z)EndIfNextyNextx百鸡问题运算结果是计算机B先把结果运算出来。为什么会这样呢? 我们来分析一下,算法A需要执行101×101×101约100万次内循环,而算法B只需要执行21×34约714次内循环。货郎担问题货郎担问题(TravelingSalesmanProblem,简称“TSP”)中国邮路问题,旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中,它成为许多重要算法思想的测试平台,同时也促使一些新的理论领域的产生,比如多面体理论和复杂性理论。货郎担问题:某售货员要到若干个城市销售货物,已知各城市之间的距离,要求售货员选择出发的城市及旅行路线,使每一个城市仅经过一次,最后回到原出发城市,而总路程最短。