算法设计与分析_01算法设计与分析引论.ppt

1 算法设计与分析引论 计算机的能力电子计算机的出现是本世纪的一件大事,因为它改变了我们这个世界的面貌。可以毫不夸张地这么说,今天人们依赖于计算机,就象人们依赖于电力, 如果它暂停了,社会就无法运转。快速电子计算机贵在神速,也就是它的运算速度快,同时它的发展之迅速也是惊人的。从每秒 5000 次运算,发展到现在的运算速度每秒数千亿次运算。元器件从继电器、真空管、晶体管、集成电路、大规模集成电路,发展到超大规模集成电路。结构上从每台机器作为运算工具的“单兵作战”模式,发展到今天将范围遍及各大洲的计算机网络,算法也从单机的串行计算发展到网络上并行的分布计算。 2 一台作 10 9次/ 秒运算( 1G )的计算机的效率超过 10 亿人同时工作。它可以作中期的天气预报,可以控制庞大的化工厂生产过程,以至于还可以驾驭现代化战争,从这个意义上来说它确实是近乎神奇的。不过必须强调的是这些都是在人的安排下进行工作的。比如人们利用计算机作天气预报,必须依据天气变化规律,作出它的偏微分方程数学模型,以及编好程序,指导计算机按照人的安排一步步地工作, 计算预报数据,绘制气象云图。这就是说,计算机虽然神通广大,还是在人的控制下工作。同时还应说明计算机并非什么都能做, 有的事情理论上它根本做不了。讨论哪些事计算机能做,哪些事计算机做不了,属于可计算性理论研究的范畴。还有一些问题理论上计算机虽是能做, 但实际上又是不可能完成的。 3 比如拿最简单例子, 26 个英文字母全排列,它的排列数为: 26!≈4×10 26 以每年 365 天计算,共有 365 ×24×3600 = ×10 7秒以每秒能完成 10 7 个排列的超高速电子计算机来做这项工作,需要 4×10 26/( ×10 14)≈ ×10 12年即使计算机运行速度随着技术的提高,恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。 4 用计算机解决问题的关键任何一项计算,总要事先拟定计算方案和规划计算步骤。为使计算机的计算过程能够解决某一问题,必须为计算机设计执行的解决方案中的每个详细步骤,并且将此过程完整地描述出来。所谓算法是对某个问题求解方案的完整而明确的描述。与算法有关的还有一个大家熟悉的公式: 程序=算法十数据结构也就是说,算法设计和程序设计是不完全相同的。由于数字计算机运算速度很高,是人工手算所不能比拟的。为了充分发挥计算机的这种优点,在用计算机求解问题过程中,应尽量减少人工干预。因此,必须先将所制定的解决方案“告诉”计算机,使计算机按照人们规定的计算顺序去自动执行。用计算机能接受的“语言”来描述解题步骤,这项工作叫做程序设计,它还包含了需要使用合适的数据结构。 5 “算法设计与分析”是研究算法的一门学科。它还很年轻远未定型,还处在发展中。有人说“计算机科学是一门研究算法的科学”。不论这个说法是否全面,算法无疑是计算机科学的重要组成部分。它近来发展极其迅速。“算法设计与分析”已是计算机专业本科生的一门必需掌握的内容。 一些有趣的问题(1) 巡回推销员问题:设有 n个城市,已知任意两城市间之距离,现有一推销员想从某一城市出发巡回经过每一城市(且每城市只经过一次),最后又回到出发点,问如何找一条最短路径。 6 设距离矩阵如下: ?????????????????018 65 72 64 18 056 73 55 65 56 041 7 72 73 41 039 64 55 739 0D试一试求出最短路径。 7 (2)皇后问题:这是高斯 1850 年提出的一个著名问题: 国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子,问在 n×n 格的棋盘上如何能摆上 n 个皇后而使她们都不能互相吃。当n很大时,问题很难。对于 n=8, 现已知此问题共有 92 种解,但只有 12 种是独立的,其余的都可以由这 12 种利用对称性或旋转而得到。设n=4 ,试一试。 8 (3 ) 设天平有一些 25 克的砝码,一些 10 克的砝码, 一些 5 克的砝码和一些 1 克的砝码。现要称 63 克的物体,问至少需要用几个砝码。(4) 背包问题 1: 有一旅行者要从 n 种物品中选取不超过 b公斤重的行李随身携带,要求总价值最大。例:设背包的容量为 50 千克。物品 1重10 千克,价值 60元;物品 2重20千克,价值 100 元;物品 3重30千克, 价值 120 元。求总价值最大。(5)背包问题 2:设有 n=8 个体积分别为 54,45,43, 29,23,21,14,1 的物体和一个容积为 C=110 的背包,问选择哪几个物体装入背包可以使其装的最满。 9 (6) 装箱问题: 设有体积分别为 v 1,v 2,