第一篇：作业：现代化优算法学习心得
现代化优算法学习心得
在科技高度发展的今天，计算机在人们之中的作用越来越突出。在这个学期里，我专门学习了现代优化算法。现代优化算法包括禁忌搜索（tabu search）、模拟退火simu-lated annclaing)、遗传算法（genetic algorithms）、神经网络neural networks)、拉格朗日松弛等算法。这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础而构成的算法，我们称之为启发算法。启发算法的兴起于计算复杂性理论的形式有密切的联系，当人们不满足常规算法求解复杂问题时，现代优化算法开始体现其作用。我在这里就以禁忌搜索这种算法来谈谈现代优化算法在计算复杂性理论问题时所体现的优越性。
禁忌搜索(rabu scarch)算法是局部邻域搜运算法的推广，是人工智能在组合优化算法中的一个成功应用。Glover 在1986年首次提出这一概念，进而形成一套完整算法，详见文献[2，3]。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已达到过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。禁忌搜索算法是一种人工智能的算法，因此，从以下方面来谈谈禁忌搜索算法。
1、局部搜索
除特别强调外，我们都假设算法用以解决如下组合最优化问题：其中)(X为目标数，g（x）为约束方程，D为定义域。因为禁忌搜索算法中用到局部搜索算法，我们首先介绍局部搜索算法。该算法可以简单的表示为：局部搜索算法STEP1 选下一个初始可行解x0；记录当前最优解xbest：= x0，令P=N（xbest）；STEP2当P=Ф时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从N（xbest）中选一集合S，得到S中的最优解xbest；若xbest＜xbest，则xbest：=xnow，P：= N（xbest）；否则，P：=P-S；重复STEP2。在局部搜索算法中，STEP1的初始可行解选择可以采用随机的方法，也可用一些经验的方法或是其他算法所得到的解。STEP2中的集合S选取可以大到是Nxbest）本身，也可以小到只有一个元素，如用随机的方法在N（xbest）中选一点，从直观可以看出，S选取得小将使每一步的计量减少，但可比较的范围很小；S选取大时每一步计算时间增加，比较的范围自然增加，这两种情况的应用果依赖于实际问题。在STEP2中，其他停止准则是除STEP2的P=Ф以外的其他准则。这些准则的给出往往取决于人们对算法的计算时间、计算结果的要求，通过下面的例子来理解局部搜索算法。例2．1 5个城市的对称TSP数据如图2.1 对应的距离矩阵为
第二篇：算法学习心得
算法设计与分析学习心得
班级：物联网1201 姓名：刘潇 学号：1030612129
一、实验内容：
这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。
二、学习掌握：
基本程序描述：
（1）货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n一1）！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解
（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。
三.疑问与总结：
货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。
动态生成二维数组的程序我认为如果按照规范性，我的方法是中规中矩的，毕竟再向下延伸，生成三维的数组，需要三层的指针来实现。但是就程序的简化程度和计算机处理时间来说，我认为这样双层指针的算法有些太占用内存，毕竟要给行和列各分配n个空间。我通过与同学的交流，我发现可以用1位数组来实现二维的n*n的数组。首先分配n*n的空间，然后通过循环在一行的数据达到n时自动换行。这样程序得到了一定的简化，并且减少了一定的内存使用。我认为这种方法是比较贴合实际的。
四.心得体会
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。
如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。篇二：算法个人心得
算法学习心得: 算法这个词是在我在大学第一次c语言课上听到的，当时老师讲的是程序=算法+数据结构，算法是一个程序的灵魂。当时我什么也不懂，不知道什么叫数据结构，什么叫算法，它们是干什么的我也不明白。然而经历了大学四年的学习，现在的我对算法有了一个较为清晰的认识，对于它的作用也有了深刻的体会。
所谓算法简单来说就是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，也就是说算法告诉计算机怎么做，以此来解决问题。同一个问题存在多种算法来解决它，但是这些算法存在着优劣之分，好的算法速度快，效率高，占用空间小，差的算法不仅复杂难懂，而且效率低，对机器要求还高，当然，有时候算法之间存在一种互补关系，有些算法效率高，节省时间，但浪费空间，另外一些算法可能速度上慢些，但是空间比较节约，这时候我们就应该根据实际要求，和具体情况来采取相应的算法来解决问题。
这学期算法课上我们主要讲了七部分内容.第一章主要讲的是算法的基本概念，算法时间复杂度分析，算法的渐近时间复杂度等内容。因为算法之间的比较就是通过时间复杂度和空间复杂度来来比较的，第一章的主要目的就是让我们学会去分析一个算法的复杂度，以后就可以通过对复杂度的分析来评价算法的好坏。
第二章讲的是分治法，任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少，分治法的设计思想就是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。在这一章中我们讲到了寻找第k个元素，矩阵相乘，寻找最近点对等几个使用分治法的经典例子，最后还将讲到了傅里叶变换的问题。以前我们学到的归并排序，二分搜索其实也是基于分治法思想的。能采用分治法来解决的问题通常有如下几个特征： 1)该问题的规模缩小到一定的程度就可以容易地解决 2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子
结构性质。
3)利用该问题分解出的子问题的解可以合并为该问题的解； 4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公
共的子子问题。
在用分治法解决实际问题时，我们疑问究竟各个子问题的规模应该怎样才为适当？从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的，这就是一种平衡的思想。
第三章主要讲动态规划问题。这一章的内容我觉得是算法设计思想中最难，也最有趣的这部分。什么叫动态规划，动态规划的思想是什么？动态规划采用自顶向下的方式分析问题，自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。“多阶段决策问题是根据问题本身的特点，将其求解的过程划分为若干个相互独立又相互联系的阶段，在每一个阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一个阶段，在每一阶段选取其最优决策，从而实现整个过程总体决策最优的目的”（引用）。还记得期末考试中的最后一道关于任意给定一个数，从所给的牌中用最少的牌组成这个数，这个问题其实就可以用动态规划来解决。本科期间，在算法课上老师在动态规划这一章不布置的一个作业跟这个题目类似，当时的题目是找钱问题，问题是这样描述的：有n种不同面值的硬币，各硬币面值存于数组t[1:n]，现用这些面值的钱来找钱，编程计算找钱m的最少硬币数及各个面值。分析如下：假设对于i = 1...n-1，所需最少的硬币数count(i)已知，那么对于n，所需的硬币数为min(count(i)+ count(n-i)), i=1...n-1;于是一个直观的方法是用递归计算。
但是，递归过程中，每次计算count(i)，都会重复计算 count(1)....count(i-1);这样时间复杂度就是o(n^2);我们可以从1开始记录下每个钱数所需的硬币枚数，避免重复计算，为了能够输出硬币序列，我们还需要记录下每次新加入的硬币。下面给出用动态规划解决此问题的递推式：
参数说明： 当只用面值为t[1],t[2],„t[n]来找出钱j时，所用的硬币的最小个数记为c(i,j),则c(i,j)的递推方程为：
运用这个递推式，我们可以从下往上记录各个j所需要的应兵书i，最后当j=m时，所对应的i就是我们要求的。第四章讲的是集合算法，这一章的内容是我第一次接触，以前没有学过。这一章主要讲了平摊分析，union-find，finding the depth，以及2-3树等内容，平摊分析教会我们如何从整体的角度去更精确的分析算法的时间复杂度，union-find sets是一种简单的用途广泛的集合，并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速，finding the depth 确定深度问题。为了既能求得各点在原先树中的正确深度、又能使时间复杂度较小，需要使用具有路径压缩功能的find-depth指令，同时还需要采取一些辅助手段来保证深度计算的正确性。2-3树具有以下几个特点：
1、任一内结点（非叶结点）均有2个或3个儿子。
2、从根到每片树叶的路径长度相等。
3、内结点中只存放便于查找的信息，而叶结点中存放原始数据。
第五章主要讲了随机算法。在随机算法中，我们不要求算法对所有可能的输入均正确计算，只要求出现错误的可能性小到可以忽略的程度。另外我们也不要求对同一输入算法每次执行时给出相同的结果。我们所关心的是算法在执行时，是否能够产生真正随机的结果。有不少问题，目前只有效率很差的确定性求解算法，但用随机算法去求解，可以很快地获得相当可信的结果。随机算法通常分为两大类:las vegas算法、monte carlo算法。las vegas算法总是给出正确的结果，但在少数应用中，可能出现求不出解的情况。此时需再次调用算法进行计算，直到获得解为止.mont carlo算法通常不能保证计算出的结果总是正确，一般只能断定所给解的正确性不小于p（1/2＜p＜1）。通过反复执行算法（即以增大算法的执行时间为代价），能够使发生错误的概率小到可以忽略的程度。第五章还讲到素数测试，其中介绍了相关定理，重点讲了miller-rabin算法。
第六章介绍了计算模型，这一章主要介绍了有关计算的一些本质问题，random access machines(随机存取机，简称ram)，存储程序模型rasp（random access stored program），图灵机（turning machine）以及各个计算模型之间的关系。
第七章介绍了np完全问题，主要包括近似算法（approximation algorithms），非确定性turing机 ndtm，确定性turing机 dtm，以及之间的区别，np完全经典问题等内容。
经过一学期的算法学习，我对算法的了解进一步加深，曾经学习过的内容得到进一步巩固，同时没有接触的内容也让我有了新的认识。作为一名计算机专业的学生，算法是一门基础学科，它里面包含的思想无处不在，学好算法分析，对于在自己的方向上获得启示，体会更深有着重大作用。所以，我们应该培养对算法的兴趣，将算法的运用融入到生活当中，比如找钱问题就是个很好的例子，通过具体的生活实例来让算法变得更加有魅力，有吸引力,以此来激发对算法的兴趣。篇三：算法设计与分析学习总结 算法分析与设计 学习总结
题目：算法分析与设计学习总结
学 院 信息科学与工程学院
专 业 届 次
学生姓名 学 号
二○一三年一月十五日
算法分析与设计学习总结
本学期通过学习算法分析与设计课程，了解到：算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。
设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。（2）确定性。算法的每一个步骤必须有确切的定义。（3）输入。一个算法有0个或多个输入，作为算法开始执行前的初始值，或初始状态。（4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性。在有限时间内完成计算过程。
算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与 代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。经典的算法主要有：
1、穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。
穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行，其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。
2、迭代算法
迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组）的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行：
（1）选一个方程的近似根，赋给变量x0。(2)将x0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。
3、递推算法
递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系，从而达到目的。
4、递归算法
递归算法是一种直接或间接的调用自身的算法。
能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规
模较大问题的解。特别的，当规模n=0或1时，能直接得解。
递归算法解决问题的特点有：
（1）递归就是在过程或函数里调用自身
（2）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口
（3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低
（4）在递归调用的过程中系统为每一层的返回点、局部变量等开辟堆栈来存
储。
举例如下： fibonacci数列
int fib[50];//采用数组保存中间结果 void fibonacci(int n){ fib[0] = 1;fib[1] = 1;for(int i=2;i<=n;i++)fib[i] = fib[i-1]+fib[i-2];}
5、分治算法
分治算法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单地直接求解，原问题的解即子问题解的合并。
如果原问题可分割成k个子问题，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治策略的算法设计模式 divide_and_conquer（p）{ if(|p|＜＝n0)return adhoc(p)； divide p into smaller substances p1，p2，„，pk； for(i＝1;i＜＝k;k＋＋)yi＝divide-and-conquer（pi）//递归解决pi return merge（y1，y2，„，yk）//合并子问题 }
6、贪心算法
贪心算法也称贪婪算法。它在对问题求解时，总是做出在当前看来是最好的选择。它不从整体最优上考虑，所得出的仅是在某种意义上的局部最优解。贪心算法的基本思路如下：（1）建立数学模型来描述问题
（2）把求解的问题分成若干个子问题
（3）对每一子问题求解，得到子问题的局部最优解
（4）把子问题的局部最优解合成原来问题的一个解
贪心算法的一般流程: greedy(a){ s={ };//初始解集合为空集 while(not solution(s))//集合s没有构成问题的一个解 { x = select(a);//在候选集合a中做贪心选择 if feasible(s, x)//判断集合s中加入x后的解是否可行 s = s+{x};a = a-{x};} return s;｝
（1）候选集合a：问题的最终解均取自于候选集合a。（2）解集合s：解集合s不断扩展，直到构成满足问题的完整解。
（3）解决函数solution：检查解集合s是否构成问题的完整解。
（4）选择函数select：贪心策略，这是贪心算法的关键。
（5）可行函数feasible：解集合扩展后是否满足约束条件。
7、动态规划算法
动态规划算法是一种在数学和计算机科学中用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。
动态规划算法的步骤
(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值（写出动态规划方程）；(3)以自底向上的方式计算出最优值；(4)根据算法最优值时得到的信息，构造一个最优值。
动态规划算法的有效性依赖于问题本身所具有的两个重要的性质：最优子结构性质和子问题重叠性质。(1)最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
(2)重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
8、回溯算法 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先的选择并不优或达不到目标，就回退一步重新选择，这种走不通就退回再走的技术成为回溯法，满足回溯条件的某个状态的点称为“回溯点”。迷宫问题算法所采用的就是回溯算法。
回溯算法解决问题的过程是先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都一一试探，如有问题就返回纠正，反复进行这种试探在反复纠正，直到得出全部符合条件的答案或是问题无解为止。由于回溯方法的本质是深度优先的方法在解的空间树中搜索，就要从堆栈中找到回溯的前一个位置继续试探。
装载问题回溯算法数据结构 #define num 100 int n;//集装箱的数量 int c;//轮船的载重量 int w[num];//集装箱的重量数组 int x[num];//当前搜索的解向量 int r;//剩余集装箱的重量 int cw;//当前轮船的载重量 int bestw;//当前最优载重量
int bestx[num];//当前最优解 算法实现 //形参表示搜索第t层结点 void backtrack(int t){ //到达叶子结点 if(t>n){ //更新最优解 if(cw>bestw){ for(int i=1;i<=n;i++)bestx[i] = x[i];bestw = cw;} return;} //更新剩余集装箱的重量 r-= w[t];//搜索左子树
if(cw+w[t]<=c){ x[t] = 1;cw += w[t];backtrack(t+1);cw-= w[t];} //搜索右子树
if(cw+r>bestw){ x[t]=0;backtrack(t+1);} r += w[t];//恢复状态 }
9、分支限界算法 分支限界算法是一种在表示问题解空间的树上进行系统搜索的方法。该方法使用了广度篇四：算法设计与实现个人课程总结 算法课程总结
指导教师
所在院（系）
班 级
学生姓名
学 号
一、算法概述 1.什么是算法？
算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。
2.算法的五个重要特性：确定性、能行性、输入、输出、有穷性/有限性。1）确定性：算法每种运算必须有确切定义，不能有二义性。2）能行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。3）输入：每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域
4）输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性/有限性：一个算法总是在执行了有穷步的运算之后终止。3.计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。4.准确理解算法和计算过程的区别：不能终止的计算过程：操作系统；算法是“可以终止的计算过程”；算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。5.算法的语言主要有：自然语言，流程图，盒图，pad图，伪代码，计算机程序设计语言。
6.算法分类： 1)多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：ο(1)< ο(logn)< ο(n)< ο(nlogn)< ο(n2)< ο(n3)2）指数时间算法：计算时间用指数函数限界的算法。常见的指数时间限界函数：ο(2n)< ο(n！)< ο(nn)7.算法基本工具：循环与递归，算法与数据结构，优化算法的数学模型。8.主要算法：迭代算法，蛮力法，分治法，动态规划法，贪婪算法，图搜索基础。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪婪算法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可
以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪婪算法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(dfs)和广度优先搜索(bfs)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、重点学习 1.贪婪算法
贪婪+其他算法：由于贪婪往往能大幅化简状态，利用问题的某些“单调性”，加上贪婪的思想，往往能是问题大幅简化，从而结合其他算法解决问题经典例题：田忌赛马，利用贪婪来确定状态。2.分治法
分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用 1)二分查找
思想很简单，功能很强大，边界要注意，负数要特判（noi2010 piano）在非负数范围内的二分一般写法
如果是l := mid1 或 +1则 mid :=(l + r + 1)div 2 2)快速幂
a^b =(a^(b div 2))^2 + ord(odd(b))*a取模也适用 3）快速排序，归并排序
任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随机化 k := a[random(rg(x)*ans = 0 重构权，将f(i)-g(i)*ans作为新权值，用相应算法求出一个“最小值”，判断是否>=0，接着二分即可 5)树的分治
一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然后递归分治处理
树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高，这里只介绍基于点的分治
步骤：处理跟当前树根有关的信息，重新计算子树大小，在子树中选择重心为根，递归到相应子树处理。
因为每次选了重心，所以递归总共logn层，每层o(n)的复杂度，总复杂度就是o(nlogn)6)二分搜索
直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解。
而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多 经典例题：poi02szy，noi2001方程的解数。3.搜索
作为信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题，搜索一般可以用来部分预处理，打表找规律，当然还有骗分。
搜索的一般步骤：确定状态——选择搜索方式（dfs、bfs）——确定产生式规则——开始搜索。搜索的常见优化方式： 1)改变状态表示
这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步，再者，调试起来也会容易许多。
2）优化搜索顺序
这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少的儿子先扩展，例如大名鼎鼎的dancing links，除了利用双向十字链表去除冗余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。3）可行性剪枝以及最优性剪枝
这是非常常用的剪枝思路之一，因题目而异，在迭代加深搜索中尤为重要 一般思路：考虑每次解最多变优多少，从当前的层数来看还有多少改进空间，如果已经不可能成为解或更新答案则可以剪枝了
——a*及ida*算法：本质就是给搜索加上一个满足相容性的估价函数，然后用估价函数剪枝，理论上很牛b，实际上不常用，因为考场上很难想出满足那么多条件的估价函数，但记得一些常见模型的估价函数还是有价值的。例如15 数码的估价函数就可以选择除了0之外每个元素到自己该到的位置的曼哈顿距离之和，因为每次最多使一个数距离减少1，所以这个估价函数是相容的，再例如求k短路的a*算法就是用个堆维护 min{ f(s)+ g(s)}估价函数就是从汇点反搜的“反向最短路”的长度。
四、总结
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为it行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：t(n)=a*t(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。篇五：遗传算法学习心得
基本概念
遗传算法(genetic algorithms, ga)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。ga的组成:（1）编码（产生初始种群）
（2）适应度函数
（3）遗传算子（选择、交叉、变异）
（4）运行参数
编码
基因在一定能够意义上包含了它所代表的问题的解。基因的编码方式有很多，这也取决于要解决的问题本身。常见的编码方式有：
（1）二进制编码，基因用0或1表示（常用于解决01背包问题）如：基因a：00100011010(代表一个个体的染色体)（2）互换编码（用于解决排序问题，如旅行商问题和调度问题）
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。
（3）树形编码（用于遗传规划中的演化编程或者表示）
如,问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。
编码方法：基因就是树形结构中的一些函数。
（4）值编码（二进制编码不好用时，解决复杂的数值问题）在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
适应度函数
遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
如tsp问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。
遗传算子——选择
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。sga（基本遗传算法）中采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子，基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 fi，则个体i 被选中遗传到下一代群体的概率为：
遗传算子——交叉
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在ga中起关键作用，是产生新个体的主要方法。1.单交叉点法（用于二进制编码）
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如：交叉前：
00000|***00 11100|***01 交叉后：
00000|***01 11100|***00 2.双交叉点法（用于二进制编码）
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.如：交叉前： 01 |0010| 11 11 |0111| 01 交叉后： 11 |0010| 01 01 |0111| 11 3.基于“ 与/或 ”交叉法（用于二进制编码）对父代按位与”逻辑运算产生一子代a;按位”或”逻辑运算产生另一子代b。该交叉策略在解背包问题中效果较好.如：交叉前： 01001011 11011101 交叉后： 01001001 11011111 4.单交叉点法（用于互换编码）
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。
如：交叉前： 87213 | 09546 98356 | 71420 交叉后：
87213 | 95640 98356 | 72104 5.部分匹配交叉（pmx）法（用于互换编码）
先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代a：872 | 130 | 9546 父代b：983 | 567 | 1420 变为： temp a: 872 | 567 | 9546 temp b: 983 | 130 | 1420 对于 temp a、temp ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５ ３<——>６ ７<——>０ 子代ａ：802 | 567 | 9143 子代ｂ：986 | 130 | 5427 6.顺序交叉法(ox)（用于互换编码）
从父代ａ随机选一个编码子串，放到子代ａ的对应位置；子代ａ空余的位置从父代ｂ中按ｂ的顺序选取（与己有编码不重复）。同理可得子代ｂ。父代a: 872 | 139 | 0546 父代b: 983 | 567 | 1420 交叉后：
子代a: 856 | 139 | 7420 子代b: 821 | 567 | 3904 7.循环交叉（cx）法（用于互换编码）cx同ox交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：ox中来自第一个亲代的编码子串是随机产生的，而cx却不是，它是根据两个双亲相应位置的编码而确定的。
父代ａ：1 2 3 4 5 6 7 8 9 | | | | | 父代ａ：5 4 6 9 2 3 7 8 1 可得循环基因：1->5->2->4->9->1 用循环的基因构成子代ａ，顺序与父代ａ一样 1 2 4 5 9 用父代ｂ剩余的基因填满子代ａ： 1 2 6 4 5 3 7 8 9 子代ｂ的编码同理。（循环基因 5->1->9->4->2->5）
遗传算子——变异 变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。ga中的变异运算是产生新个体的辅助方法，它决定了ga的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率pm不能太小，这样降低全局搜索能力；也不能太大，pm > 0.5，这时ga退化为随机搜索。
第三篇：现代化网络学习心得
现代化网络学习心得
许丽晴
随着信息化快速发展，作为一名幼儿园教师，必须具备良好的信息素养是终生学习、不断完善自身的需要。应具有现代化的教育思想、教学观念，掌握现代化的教学方法和教学手段，熟练运用信息工具对信息资源进行有效的收集、加工、组织、运用;这些素质的养成就要求信息技术教师不断地学习，才能满足现代化教学的需要;信息素养成了终生学习的必备素质之一，如果教师没有良好的信息素养，就不能成为一名满足现代教学需要的高素质的数学教师。
通过聆听本次网络提升的学习，使我充认识到作为老师，要掌握信息操作的基本能力和获取信息的能力，除此之外还应具备信息收集处理以及表达的能力和综合运用能力。深刻的认识到教育信息的重要性，明白什么是教育信息化发的发展情况，真正理解了信息化教学环境在教育教学中的作用，掌握常用的教学模式和软件的基本应用。在线培训为我们提供了一个合作交流的平台，一个增强自信的平台。通过看专家视频讲座及各种电子教育技术的展示与操作，我获益很大。要想成为新型的幼儿教师，要不断地学习、不断的、地提高，才能适应当今教育发展的需要。此次培训改变了我对信息技术的片面理解，拓宽了个人的知识面，让我对信息技术有了一个全新的认识和理解。现代信息技术以图、文、声、像于一体，及多样性、新颖性、直观性、灵活性于一身，使静止的图文说话，复杂的内容变简单，抽象的思维更可及，知识的内容更明朗。使教学形象生动，方便快捷，实用有效。
在今后的教育教学过程中，我一定扎实工作，努力学习，把用所学到的教育技术知识更好地应用到现代化的教育教学中，扎实做好基本功，学习各种关于信息技术的专业知识，并将新的信息技术应用的课堂教育之中，持之以恒，不懈的努力优化自我的专业技能，更好的适应现代化教学的发展需求。
第四篇：教育现代化学习心得（最终版）
教育现代化学习心得
随着科学技术的发展，特别是计算机技术的推广和普及，使得多所学校能够通过教育网进行交流，互相探讨，互相学习，本人深受感触，通过对网上教育的学习，知道了多媒体技术在课堂教学中得到了广泛的应用，对教师教学质量的提高以及个人素质的提高都有很大的帮助。
下面我就自己通过学习计算机多媒体技术和课件制作方面的有关情况谈以下几点体会。
一、小学教师特别是青年教师要善于学习、乐于学习信息技术。
运用信息技术对我教学工作起到重要的作用。信息技术可以将我用语言难以表达清楚的问题直观、形象地展现给学生。有助于教学重点和难点的突破；教学过程中把丰富多彩的视频、动画、图片等资料展示给学生，可以引起学生的学习兴趣；通过某些问题的设置，可以培养学生对教学过程的参与意识，加深其对问题的认识和理解程度；选择合适的媒体进行教学，可以增大我课容量，节约时间。
单纯靠粉笔、黑板等教学工具来进行教学的传统教学模式显然是跟不上现代化教学的要求的掌握一定的计算机多媒体技术，如果没有现代化信息技术，就没有现在高质量的教学。
二、我是如何学习信息技术和课件制作的1、培养兴趣，循序渐进
以前我对信息技术和课件制作几乎是一窍不通。可是当我看到有的老师把信息技术引进课堂教学时，我就觉得课件制作作为一门技术对教学的作用是非常大的，我必须掌握这门技术，才能适应现代化的教育。
人们常说“兴趣是最好的老师”，培养了兴趣我就开始下功夫学习计算机的使用和课件制作。通过学习我知道了好多以前根本没有接触过的东西，比如制图软件photoshop等，还有各种课件制作软件，如powerpoint、flash等。在学习的过程中我发现我们常用的课件制作软件有好多相通之处，学好了其中的某一个，其他的自己动手、多进行尝试也会慢慢掌握。
2、善于研究，多问问题
学习的过程就是一个不断遇到问题和不断解决问题的过程。在学习和使用各种软件制作课件的时候，我遇到了很多的问题，遇到问题首先我就自己先琢磨，每个软件的功能都很多，我们学会的可能只是这些功能中的一部分，有好多功能需要靠自己尝试、研究和琢磨。当然也有好多问题自己解决不了，我就虚心请教别的老师。我相信，只要我们乐于尝试，善于思考问题、询问问题，难题是没有解决不了的。工作在教学第一线的老师们在教学过程中可能都有这种感觉，我们觉得很简单的东西有的学生还要问，我们认为简单的东西学生们说不定觉得挺难，所以我们鼓励学生多提问问题。课件制作也是同样的道理，我们初学者觉得不好解决的问题在别人看来也许是简单的，所以在学习课件制作的过程中多问问题是必要的。
3、亲自动手，乐于尝试
哲学上讲实践是认识的动力和来源，也是检验认识正确与否的唯一标准，把这一观点应用到课件制作上就是要亲自动手制作课件。也许我们在某一方面的创意是非常好的，可不亲自动手，这方面的创意就实现不了。我们可以先从简单的做起，由简单到复杂，根据自己的实际水平动手制作几个完整的课件，只有这样，自己的水平才会不断提高。
三，课件制作过程中应注意的几个问题
1、选择合适的媒体
现在开发的课件制作软件有好多，每一种软件都有它的优势，当然也可能在某些方面存在不足，我们在制作课件之前，应该通盘考虑所要讲授的课程的特点，需要处理的内容，然后根据不同的软件的优点来选择使用什么平台。
2、简洁实用是课件制作的重要原则
不少老师在制作课件时往往将自己的课件做得特别“好看”，在课件中加入大量的小动画和艳丽的图片以及很刺激的声音，我认为这样不仅起不到应有的效果，反而可能会冲淡主题，这些与课堂无直接关系的东西会过多的吸引学生的注意力。信息技术毕竟是一种辅助手段，它是用来辅助我们的教学的。一个好的课件关键在于它的实用性，应该说只要是有助于突破重点难点、有助于引起学生的深刻思考、有助于加深学生对问题的认识的课件就是好课件。
另外，我认为不要试图每堂课都通过信息技术来处理，这样既没有必要，也不现实，制作一个好的课件往往需要较长的时间。信息技术的应用不是对传统教学的否定，而是对传统教学的有利补充，提高学生学习效率的关键还是在课堂，我们在制作课件时应充分认识到这一点。
我相信，只要我们对信息技术有了正确的认识，加上我们的正确使用，信息技术必将在我们的教学过程中发挥其应有的作用。
第五篇：短作业优先调度算法
《操作系统》课程实验报告
姓名：陈凯
学号：541413430202
地点：四教楼301
指导老师：张旭
专业班级：嵌入式软件14-02
实验名称：短作业优先调度算法
一、实验目的：
测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间
最终能够计算每一个作业的周转时间。
二、实验内容：
模拟实现短作业调度算法，具体如下：
设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：
1、显示当前调度的是哪个作业，后备队列中有哪些作业
2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间
排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。
三、实验代码
#include
char name[10];//进程名
floatarrivetime;//到达时间
floatservicetime;//服务时间
floatstarttime;
//开始时间
floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;
//带权周转时间 };
sjf b[100];
//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)
//输入函数 { int i;
printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){
printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n执行顺序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++) { printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } } voidSsort(sjf *p,int N) //按短作业优先算法排序 { for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++) if(p[i].servicetime sjf temp;temp=p[i]; p[i]=p[j]; p[j]=temp;} } //运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0){ p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime; } else { p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间 p[k].finishtime=p[k-1].finishtime+p[k].servicetime; //结束时间=前一个进程的完成时间+现在进程的服务时间 } } for(k=0;k<=N-1;k++){ p[k].zztime=p[k].finishtime-p[k].arrivetime; //周转时间=完成时间-到达时间 p[k].dqzztime=p[k].zztime/p[k].servicetime; //带权周转时间=周转时间/服务时间 } } void SJF(sjf *p,int N){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; Ssort(p,N); Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、实验结果 五、实验总结 通过本次实验让我学到了很多关于作业与作业调度的知识，今后我会好好努力学习。
点击咨询 