算法的优化ppt课件.ppt

《算法的优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法的优化学习目标知识目标理解算法优化的意义。技能目标学会用不同的算法来解决问题，并能对算法进行优化。情感目标学会对视角分析问题，能利用高效的方法解决问题，养成细致缜密思考问题的习惯。材料一孙膑是战国时期著名的军事家。齐国的将军田忌经常同齐威王赛马。马分上、中、下三等，在比赛时，总是以上等马对上等马，中等马对中等马，下等马对下等马。齐威王每一个等级的马都要比田忌的强，所以田忌总是输。孙膑给田忌出了个主意，比赛时，让他以下等马对齐威王的上等马，再以上等马对他的中等马，最后以中等马对他的下等马。比赛结束，田忌以三局两胜的战绩取得了胜利。同样的马匹，仅仅调换了比赛顺序

2、，就得到了反败为胜的结果。从算法角度讲，孙膑的策略是一种经过优化的算法。自我探究这个材料说明了什么？什么叫做算法的优化？知识回顾算法是做某件事情或解决某一问题的方法、步骤、过程和程序。探索新知算法的优化指的就是用最优化的方法来解决问题。最优化方法是一种数学方法，它就是研究在给定的条件下如何寻求某些因素的组合、统筹、替代、转换等，以使某一指标（或结果）达到最优的一些学科的总称。它包括生活中的算法优化、排序的算法优化和查找的算法优化。材料二：著名数学家华罗庚先生在1964年所著的《统筹方法平话》里举了一个“烧水泡茶”的例子：一个人口渴了，想泡一壶茶喝，需要烧开水、洗

3、茶具、拿茶叶。他怎样才能在最短的时间喝上茶水呢？小组讨论你能为“烧水泡茶”提供几种解决方案?你认为哪种方案是最快捷的？为什么？算法比较方法一：①烧水②水烧开同时，洗茶壶，洗茶杯，拿茶具（16分钟）③沏茶方法二：①烧水②水烧开之前，洗茶壶，洗茶杯，拿茶具（20分钟）③沏茶方法三：①烧水②水烧开之后，洗茶壶，洗茶杯，拿茶具（20分钟）③沏茶材料三：李明从早上起床到上学前这段时间，要做以下几件事：叠被（2分钟）、洗脸（3分钟）、刷牙（2分钟）、刷锅（1分钟）、煮鸡蛋（10分钟）、吃早点（10分钟）。小组讨论：请你为李明设计一套最节省时间的方案。解决方法首先，刷锅；然后

4、，煮鸡蛋的同时，叠被，洗脸，刷牙；最后，吃早点。（共21分钟）材料四：某车间只有一台高精度的机床，常常出现很多零件同时要求用这台机床加工的情况。现有6个零件要求加工，每个零件加工耗时如下表所示。试一试按照怎样的顺序来加工零件，才能使这6个零件在车间里停留的平均时间最少？问题点拨：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小递增或递减排列的操作。排序问题是指在一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源。排序问题产生的背景主要是机器制

5、造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。解析：对于一台机器N个零件的排序问题，只要可加工的零件数越大，配上加工的时间越少，即按加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使每个零件停留的平均时间越少。练一练一位商人有9个银币，其中有一枚略轻，是假银币。能用天平（不用砝码）将假银币找出来吗？请给出最优化的算法。算法分析算法一：①任取2枚银元分别放在天平的两边，如果天平左右不平衡，则轻的那一边就是假银元；如果天平平衡，则进行第二步。②取下右边的银元，然后把剩下的7枚银元依次放在右边进行称量，直到天平不平衡，偏

6、轻的那一边就是假银元．算法二：①任取两枚银元分别放在天平的两端，如果天平左右不平衡，则轻的那一边是假银元；否则进行第二步。②重复执行第一步，如果前4次天平都平衡，则剩下的那一枚是假银元。算法三：①把9枚银元平均分成3组，每组3枚．②先将其中两组放在天平的两边，如果天平左右不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称量的那一组内。③取出含有假银元的那一组，从中任取2枚银元放在天平左右两边进行称量，如果天平左右不平衡，则轻的那一边是假银元；如果天平左右平衡，则未称的那一枚就是假银元．想一想蚂蚁的视力较差，但却能在黑暗的世界中快速找到食物，而且

7、可以找到从洞穴到事物的最短路径。小组探究，你知道蚂蚁是如何做到的吗？研究表明：蚂蚁在行走过程中会释放一种称为“信息素”的挥发性化学物质，用来标识自己的行走路径。在寻找食物的过程中，蚂蚁会根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。一点通起先，由于地面上没有信息素，因此蚂蚁们的行走路径是随机的，可以理解为“地毯式”搜寻食物。蚂蚁们在行走的过程中会不断的释放信息素，标识自己的行走路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为路径是随机分布的，长路径上的信息素随着时间的流逝浓度要比短路径上的低，因此在单位

8、时间内，短路径上的蚂蚁数