第一篇:人工智能十大算法总结
5-1 简述机器学习十大算法的每个算法的核心思想、工作原理、适用 情况及优缺点等。1)C4.5 算法:
ID3 算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。ID3 算法计算每个属性的信息增益,并选取具有最高增益的属性作为给定的测试属性。C4.5 算法核心思想是ID3 算法,是ID3 算法的改进,改进方面有: 1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 2)在树构造过程中进行剪枝 3)能处理非离散的数据 4)能处理不完整的数据
C4.5 算法优点:产生的分类规则易于理解,准确率较高。缺点:
1)在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。2)C4.5 只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。2)K means 算法:
是一个简单的聚类算法,把n 的对象根据他们的属性分为k 个分割,k < n。算法的核心就是要优化失真函数J,使其收敛到局部最小值但不是全局最小值。
其中N 为样本数,K 是簇数,rnk b 表示n 属于第k 个簇,uk 是第k 个中心点的值。然后求出最优的uk
优点:算法速度很快
缺点是,分组的数目k 是一个输入参数,不合适的k 可能返回较差的结果。
3)朴素贝叶斯算法:
朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。算法的基础是概率问题,分类原理是通过某对象的先验概率,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。朴素贝叶斯假设是约束 性很强的假设,假设特征条件独立,但朴素贝叶斯算法简单,快速,具有较小的出错率。在朴素贝叶斯的应用中,主要研究了电子邮件过滤以及文本分类研究。
4)K 最近邻分类算法(KNN)
分类思想比较简单,从训练样本中找出K个与其最相近的样本,然后看这k个样本中哪个类别的样本多,则待判定的值(或说抽样)就属于这个类别。缺点:
1)K 值需要预先设定,而不能自适应
2)当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K 个邻居中大容量类的样本占多数。
该算法适用于对样本容量比较大的类域进行自动分类。
5)EM 最大期望算法
EM 算法是基于模型的聚类方法,是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量。E步估计隐含变量,M步估计其他参数,交替将极值推向最大。EM 算法比K-means 算法计算复杂,收敛也较慢,不适于大规模数据集和高维数据,但比K-means 算法计算结果稳定、准确。EM 经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。
6)PageRank 算法
是google 的页面排序算法,是基于从许多优质的网页链接过来的网页,必定还是优质网页的回归关系,来判定所有网页的重要性。(也就是说,一个人有着越多牛X 朋友的人,他是牛X 的概率就越大。)优点:完全独立于查询,只依赖于网页链接结构,可以离线计算。缺点:1)PageRank 算法忽略了网页搜索的时效性。
2)旧网页排序很高,存在时间长,积累了大量的in-links,拥有最新资讯的新网页排名却很低,因为它们几乎没有in-links。
7)AdaBoost Adaboost 是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。整个过程如下所示:
1.先通过对N 个训练样本的学习得到第一个弱分类器;
2.将分错的样本和其他的新数据一起构成一个新的N 个的训练样本,通过对这个样本的学习得到第二个弱分类器; 3.将和都分错了的样本加上其他的新样本构成另一个新的N个的训练样本,通过对这个样本的学习得到第三个弱分类器; 4.如此反复,最终得到经过提升的强分类器。
目前AdaBoost 算法广泛的应用于人脸检测、目标识别等领域。
8)Apriori 算法
Apriori 算法是一种挖掘关联规则的算法,用于挖掘其内含的、未知的却又实际存在的数据关系,其核心是基于两阶段频集思想的递推算法。Apriori 算法分为两个阶段:1)寻找频繁项集
2)由频繁项集找关联规则
算法缺点:
1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;
2)每次计算项集的支持度时,都对数据库中的全部记录进行了一遍扫描比较,需要很大的I/O 负载。9)SVM 支持向量机
支持向量机是一种基于分类边界的方法。其基本原理是(以二维数据为例):如果训练数据分布在二维平面上的点,它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是,通过训练,找到这些分类之间的边界(直线的――称为线性划分,曲线的――称
为非线性划分)。对于多维数据(如N 维),可以将它们视为N 维空间中的点,而分类边界就是N 维空间中的面,称为超面(超面比N维空间少一维)。线性分类器使用超平面类型的边界,非线性分类器使用超曲面。
支持向量机的原理是将低维空间的点映射到高维空间,使它们成为线性可分,再使用线性划分的原理来判断分类边界。在高维空间中是一种线性划分,而在原有的数据空间中,是一种非线性划分。SVM 在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。10)CART 分类与回归树
是一种决策树分类方法,采用基于最小距离的基尼指数估计函数,用来决定由该子数据集生成的决策树的拓展形。如果目标变量是标称的,称为分类树;如果目标变量是连续的,称为回归树。分类树是使用树结构算法将数据分成离散类的方法。优点
1)非常灵活,可以允许有部分错分成本,还可指定先验概率分布,可使用自动的成本复杂性剪枝来得到归纳性更强的树。2)在面对诸如存在缺失值、变量数多等问题时CART 显得非常稳健。
第二篇:算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中,算法分析与设计是一门非常重要的课程,很多人为它如痴如醉。很多问题的解决,程序的编写都要依赖它,在软件还是面向过程的阶段,就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的,它可以培养我们养成思考分析问题,解决问题的能力。作为IT行业学生,学习算法无疑会增强自己的竞争力,修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习,我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥,但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的,尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如:T(n)=a*T(n/b)+f(n),它可以看作一个大问题分解为a个子问题,其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时,我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗,即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中,我学到了以前从未遇见过的随机算法,它给予我很大的启示。随机算法不随机,它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风,它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用,才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据,也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理:指纹的运用,理论出错率的计算,算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发,要想学好算法,学好数学是必不可少的。没有深厚的数学功力作为地基,即使再漂亮的算法框架,代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子,更重要的是为了学习蕴含在其中的思想方法。为什么呢?举个例子。有同学曾问我这样一个问题:1000只瓶子装满水,但有一瓶有毒,且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒,每只老鼠可以喝多个瓶子的水,每个瓶子可以只喝一点。问如何解决?其实一开始我也一头雾水,但是他提醒我跟计算机领域相关,我就立马有了思路,运用二进制。因为计算机的最基本思想就是二进制。所以说,我们不仅要学习算法,更得学习思想方法。
①算法最基本的设计方法包括分治法,动态规划法,贪心法,周游法,回溯法,分支定界法。我们可利用分治法做快速排序,降低找n个元素中最大元和最小元的量级,降低n位二进制x和y相乘的量级,做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题,关键是子问题要与原问题同类,可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题,但是子问题是重复的,后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树,解决矩阵连乘时最小计算次数问题,寻找最长公共子序列等等。
贪心法就是局部最优法,先使局部最优,再依次构造出更大的局部直至整体。如Kruscal最小生成树算法,求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点,典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走,当走到某步时,发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题,平面点集的凸包问题和0-1背包问题。
分支定界法:它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法,会计法和势能法。聚集法就是把指令分为几类,计算每一类的消耗,再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去,以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗,再将每一步消耗全部累计。
这几种方法都是平摊分析法,平摊分析的实质就是总体考虑指令的消耗时间,尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多,每种方法都有属于它的难点。如聚集法中如何将指令有效分类,会计法中用什么指令提前计算什么指令的消耗,势能法中如何选取势能。因此掌握这些方法原理还不够,还要学会去应用,在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算,局限于如何提高性能以降低复杂度,我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活,设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性,也可以用来判断两个字符串的相近性,这可应用在数据挖掘中。快速傅立叶变换(FFT)可应用在计算多项式相乘上来降低复杂度,脱线min算法就是利用了Union-Find这种结构。还有图中相关算法,它对于解决网络流量分配问题起了很大的帮助,等等。
这些应用给了我很大的启发:因为单纯讲一个Union-Find算法,即使了解了它的实现原理,遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来,不能停留在思想方法阶段,要学以致用,做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解,所以就粗浅的谈一下我的看法。
首先谈到计算模型,就不得不提到图灵计算,他将基本的计算抽象化,造出一个图灵机,得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的,否则就是不可计算的。由此引申出一个著名论题:任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂,我认为它是制约算法发展的瓶颈,但这也是算法分析的魅力所在。NP问题一般可分为3类,NP-C问题,NP-hard问题以及顽型问题。NP-C它有个特殊的性质,如果存在一个NP-C问题找到一个多项式时间的解法,则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解,但是规模大时,就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法,如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课,我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案,讲完一章,再发课件。让我们先思考一会儿,或者给出个奖励机制,谁能解决这个问题,平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到,一个问题出来,未经过思考就已经知晓它的答案,就没什么意思,得不到提高,而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考,点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业,个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码,没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助,因为这间接成为了程序设计题,不是算法设计题。
③本门课的时间安排的不太恰当,因为本学期的课程太多,压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣,比较重视,想花功夫,但苦于没时间。所以可不可以将课程提前一个学期,那时候离散数学也已经学过,且课程的压力也不是很大。错开时间的话,我觉得应该能够更好提高大家算法分析设计的能力。
第三篇:算法总结
算法分块总结
为备战2005年11月4日成都一战,特将已经做过的题目按算法分块做一个全面详细的总结,主要突出算法思路,尽量选取有代表性的题目,尽量做到算法的全面性,不漏任何ACM可能涉及的算法思路。算法设计中,时刻都要牢记要减少冗余,要以简洁高效为追求目标。另外当遇到陌生的问题时,要想方设法进行模型简化,转化,转化成我们熟悉的东西。
图论模型的应用
分层图思想的应用:
用此思想可以建立起更简洁、严谨的数学模型,进而很容易得到有效算法。重要的是,新建立的图有一些很好的性质: 由于层是由复制得到的,所以所有层都非常相似,以至于我们只要在逻辑上分出层的概念即可,根本不用在程序中进行新层的存储,甚至几乎不需要花时间去处理。由于层之间的相似性,很多计算结果都是相同的。所以我们只需对这些计算进行一次,把结果存起来,而不需要反复计算。如此看来,虽然看起来图变大了,但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理,为发现有效算法打下了良好的基础。
这些特点说明这个分层图思想还是很有潜力的,尤其是各层有很多公共计算结果这一点,有可能大大消除冗余计算,进而降低算法时间复杂度。二分图最大及完备匹配的应用: ZOJ place the robots: 二分图最优匹配的应用:
最大网络流算法的应用:典型应用就求图的最小割。最小费用最大流的应用:
容量有上下界的最大流的应用:
欧拉路以及欧拉回路的应用:主要利用求欧拉路的套圈算法。最小生成树:
求最小生成树,比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E),后者一般应用于稀疏图,其时间复杂度为O(Elog2V)。最小K度限制生成树:
抽象成数学模型就是:
设G=(V,E,ω)是连通的无向图,v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值:把v0点从图中删去后,图中可能会出 现m 个连通分量,而这m 个连通分量必须通过v0来连接,所以,在图G 的所有生成树中 dT(v0)≥m。也就是说,当k 首先,将 v0和与之关联的边分别从图中删去,此时的图可能不再连通,对各个连通分量,分别求最小生成树。接着,对于每个连通分量V’,求一点v1,v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’},则该连通分量通过边(v1,v0)与v0相连。于是,我们就得到了一个m度限制生成树,不难证明,这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树,为了解题的简便,把该树转化成以v0为根的有根树。 假设已经得到了最小p度限制生成树,如何求最小p+1 度限制生成树呢?在原先的树中加入一条与v0相关联的边后,必定形成一个环。若想得到一棵p+1 度限制生成树,需删去一条在环上的且与v0无关联的边。删去的边的权值越大,则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点,动态转移方程:Best(v)=max(Best(father(v)),(father(v),v)),边界条件为Best[v0]=-∞,Best[v’]=-∞|(v0,v’)∈E(T)。 状态共|V|个,状态转移的时间复杂度O(1),所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树; 2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。 加边和去边过程,利用动态规划优化特别值得注意。 次小生成树: 加边和去边很值得注意。 每加入一条不在树上的边,总能形成一个环,只有删去环上的一条边,才能保证交换后仍然是生成树,而删去边的权值越大,新得到的生成树的权值和越小。具体做法: 首先做一步预处理,求出树上每两个结点之间的路径上的权值最大的边,然后,枚举图中不在树上的边,有了刚才的预处理,我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢?因为这是一棵树,所以并不需要什么高深的算法,只要简单的BFS 即可。 最短路径的应用: Dijkstra 算法应用: Folyed 算法应用: Bellman-Ford 算法的应用: 差分约束系统的应用: 搜索算法 搜索对象和搜索顺序的选取最为重要。一些麻烦题,要注意利用数据有序化,要找一个较优的搜索出发点,凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜,记忆化搜索,注意剪枝: 广搜(BFS)的应用: 枚举思想的应用: ZOJ 1252 island of logic A*算法的应用: IDA*算法的应用,以及跳跃式搜索探索: 限深搜索,限次: 迭代加深搜索: 部分搜索+高效算法(比如二分匹配,动态规划): ZOJ milk bottle data: 剪枝优化探索: 可行性剪枝,最优性剪枝,调整搜索顺序是常用的优化手段。 动态规划 动态规划最重要的就是状态的选取,以及状态转移方程,另外还要考虑高效的预处理(以便更好更快的实现状态转移)。最常用的思想就是用枚举最后一次操作。 状态压缩DP,又叫带集合的动态规划:题目特点是有一维的维数特别小。类似TSP问题的DP: 状态划分比较困难的题目: 树形DP: 四边形不等式的应用探索:四边形不等式通常应用是把O(n^3)复杂度O(n^2) 高档数据结构的应用 并查集的应用: 巧用并查集中的路径压缩思想: 堆的利用: 线段树的应用: 总结用线段树解题的方法 根据题目要求将一个区间建成线段树,一般的题目都需要对坐标离散。建树时,不要拘泥于线段树这个名字而只将线段建树,只要是表示区间,而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的,都可以建线段树;不要拘泥于一维,根据题目要求可以建立面积树、体积树等等 树的每个节点根据题目所需,设置变量记录要求的值 用树形结构来维护这些变量:如果是求总数,则是左右儿子总数之和加上本节点的总数,如果要求最值,则是左右儿子的最大值再联系本区间。利用每次插入、删除时,都只对O(logL)个节点修改这个特点,在O(logL)的时间内维护修改后相关节点的变量。 在非规则删除操作和大规模修改数据操作中,要灵活的运用子树的收缩与叶子节点的释放,避免重复操作。 Trie的应用:; Trie图的应用探索: 后缀数组的应用研究: 在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。 树状数组的应用探索:; 计算几何 掌握基本算法的实现。凸包的应用:; 半平面交算法的应用:; 几何+模拟类题目:几何设计好算法,模拟控制好精度。扫描法:; 转化法:ZOJ 1606 将求所围的格子数,巧妙的转化为求多边形的面积。离散法思想的应用:; 经典算法:找平面上的最近点对。 贪心 矩形切割 二分思想应用 活用经典算法 利用归并排序算法思想求数列的逆序对数: 利用快速排序算法思想,查询N个数中的第K小数: 博弈问题 博弈类题目通常用三类解法:第一类推结论; 第二类递推,找N位置,P位置; 第三类SG函数的应用。第四类极大极小法,甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。 第一类:推结论。典型题目: 第二类:递推。典型题目: 比如有向无环图类型的博弈。在一个有向图中,我们把选手I有必胜策略的初始位置称为N位置(Next player winning),其余的位置被称为P位置(Previous player winning)。很显然,P位置和N位置应该具有如下性质: 1. 所有的结束位置都是P位置。 2. 对于每一个N位置,至少存在一种移动可以将棋子移动到一个P位置。3. 对于每一个P位置,它的每一种移动都会将棋子移到一个N位置。 这样,获胜的策略就是每次都把棋子移动到一个P位置,因为在一个P位置,你的对手只能将棋子移动到一个N位置,然后你总有一种方法再把棋子移动到一个P位置。一直这样移动,最后你一定会将棋子移动到一个结束位置(结束位置是P位置),这时你的对手将无法在移动棋子,你便赢得了胜利。 与此同时,得到了这些性质,我们便很容易通过倒退的方法求出哪些位置是P位置,哪些位置是N位置,具体的算法为: 1. 将所有的结束位置标为P位置。 2. 将所有能一步到达P位置的点标为N位置。 3. 找出所有只能到达N位置的点,将它们标为P位置。 4. 如果在第三步中没有找到新的被标为P位置的点,则算法结束,否则转到步骤2。这样我们便确定了所有位置,对于题目给出的任一初始位置,我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类:SG函数的应用。 关于SG函数的基本知识:对于一个有向图(X, F)来说,SG函数g是一个在X上的函数,并且它返回一个非负整数值,具体定义为 g(x)min{n0,ng(y)对于所有yF(x)} 1. 对于所有的结束位置x,g(x)= 0。 2. 对于每一个g(x)≠ 0的位置x,在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。 3.对于每一个g(x)= 0的位置x,所有可以由它一步到达的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i个有向图的SG函数值,i = 1,…,n,那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四类:极大极小法。 典型题目:ZOJ 1155:Triangle War ZOJ 1993:A Number Game 矩阵妙用 矩阵最基本的妙用就是利用快速乘法O(logn)来求解递推关系(最基本的就是求Fibonacci数列的某项)和各种图形变换,以及利用高斯消元法变成阶梯矩阵。典型题目: 数学模型举例 向量思想的应用: UVA 10089:注意降维和向量的规范化 ; 利用复数思想进行向量旋转。 UVA 10253: 递推 数代集合 数代集合的思想: ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题:Intuitionistic Logic 用枚举+数代集合思想优化,注意到题中有一句话:“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”,这句话告诉我们H的元素个数不会超过100,因此可以考虑用一个数代替一个集合,首先把所有的运算结果都用预处理算出来,到计算的时候只要用O(1)的复杂度就可以完成一次运算。 组合数学 Polya定理则是解决同构染色计数问题的有力工具。 补集转化思想 ZOJ 单色三角形: 字符串相关 扩展的KMP算法应用:;最长回文串; 最长公共子串; 最长公共前缀; 填充问题 高精度运算 三维空间问题专题 无论什么问题,一旦扩展到三难空间,就变得很有难度了。三维空间的问题,很考代码实现能力。 其它问题的心得 解决一些判断同构问题的方法:同构的关键在于一一对应,而如果枚举一一对应的关系,时间复杂度相当的高,利用最小表示,就能把一个事物的本质表示出来。求最小表示时,我们一定要仔细分析,将一切能区分两个元素的条件都在最小表示中体现,而且又不能主观的加上其他条件。得到最小表示后,我们往往还要寻求适当的、高效的匹配算法(例如KMP字符匹配之类的),来比较最小表示是否相同,这里常常要将我们熟悉的高效算法进行推广 源程序代码: } 一、自然数拆分(递归) } #include 二、快速排序(递归)int a[100];void spilt(int t)#include spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i; int value=a[from];printf(“please enter the number:”); while(from a[from]=a[to]; while(from ++from; a[to]=a[from]; } a[from]=value; return from; } void qsort(int a[],int from,int to){ int pivottag;if(from {pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to); } scanf(“%d”,&n); for(i=1;i<=n/2;i++){ a[1]=i;a[2]=n-i;spilt(2); 三、删数字(贪心) #include int a[11]={3,0,0,0,9,8,1,4,7,5,1}; int k=0,i=0,j; int m; while(i<11) { printf(“%d ”,a[i]); i++;} printf(“n please input delete number:”); 四、全排列(递归)#include int i;char temp;if(k==n) for(i=0;i<=3;i++) {printf(“%c ”,a[i]);} else { for(i=k;i<=n;i++) { temp=a[i]; a[i]=a[k]; a[k]=temp; A(a,k+1,n); } } } main(){ int n; char a[4]={'a','b','c','d'},temp; A(a,0,3); getch(); return 0;} 五、多段图(动态规划)#include “stdio.h” #define n 12 //图的顶点数 { while(from scanf(“%d”,&m);for(k=0;k { for(i=0;i<=11-k;i++) { if(a[i]>a[i+1]) { for(j=i;j<10;j++) {a[j]=a[j+1];} break;//满足条件就跳转 } } } int quicksort(int a[],int n){ qsort(a,0,n);} } printf(“the change numbers:”); for(i=0;i<11-m;i++) { if(a[i]!=0) { printf(“%d ”,a[i]);} } } #define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组 int path[k];//存储最短路径的数组 void creatgraph()//创建图的(成本)邻接矩阵 { int i,j; for(i=0;i for(j=0;j scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 } void printgraph()//输出图的成本矩阵 { int i,j; printf(“成本矩阵:n”); for(i=0;i { for(j=0;j printf(“%d ”,cost[i][j]); printf(“n”); } } //使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j<=n-1;j++) if(cost[i][j]>0 &&(cost[i][j])+v[j] {length=cost[i][j]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0;//起点 path[k-1]=n-1;//最后的目标 for(i=1;i<=k-2;i++)(path[i])=d[path[i-1]];//将最短路径存入数组中 } //使用向后递推算法求多段图的最短路径 void BackPath(){ int i,j,length,temp,v[n],d[n]; for(i=0;i for(i=1;i<=n-1;i++) { for(length=MAX,j=i-1;j>=0;j--) if(cost[j][i]>0 &&(cost[j][i])+v[j] {length=cost[j][i]+v[j];temp=j;} v[i]=length; d[i]=temp; } path[0]=0; path[k-1]=n-1; for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];} //输出最短路径序列 void printpath(){ int i; for(i=0;i printf(“%d ”,path[i]);} main(){ freopen(“E:1input.txt”,“r”,stdin); creatgraph(); printgraph(); FrontPath(); printf(“输出使用向前递推算法所得的最短路径:n”); printpath(); printf(“n输出使用向后递推算法所得的最短路径:n”); BackPath(); printpath();printf(“n”);} 六、背包问题(递归)int knap(int m, int n){ int x; x=m-mn; if x>0 sign=1; else if x==0 sign=0; else sign=-1; switch(sign){ case 0: knap=1;break; case 1: if(n>1) if knap(m-mn,n-1) knap=1; else knap= knap(m,n-1); else knap=0; case-1: if(n>1) knap= knap(m,n-1); else knap=0; } } 七、8皇后(回溯)#include int i; i=1; while(i if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return 0; i++; } return 1;} void Nqueens(int X[N+1]){ int k, i; X[1]=0;k=1; while(k>0){ X[k]=X[k]+1; while((X[k]<=N)&&(!place(k,X))) X[k]=X[k]+1; if(X[k]<=N) if(k==N){ for(i=1;i<=N;i++) printf(“%3d”,X[i]);printf(“n”); } else{ k=k+1; X[k]=0; } else k=k-1; } } void main(){ int n, i; int X[N+1]={0}; clrscr(); Nqueens(X); printf(“The end!”);} 八、图着色(回溯)#include int j,t; while(1){ nextValue(k); if(X[k]==0) return 0; if(k==(N-1)){ for(t=0;t printf(“%3d”,X[t]); printf(“n”); count++; } else mcoloring(k+1); } } int nextValue(int k){ int j; while(1){ X[k]=(X[k]+1)%(M+1); if(X[k]==0) return 0; for(j=0;j if((GRAPH[k][j]==1)&&(X[k]==X[j])) break; } if(j==N){ return 0; } } } void main(){ int k; clrscr(); k=0; mcoloring(k); printf(“ncount=%dn”,count);} 矩阵链乘法(动态规划) 符号S[i, j]的意义: 符号S(i, j)表示,使得下列公式右边取最小值的那个k值 public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s) { int n=p.length-1; for(int i = 1;i <= n;i++)m[i][i] = 0; for(int r = 2;r <= n;r++) for(int i = 1;i <= n-r+1;i++){ int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for(int k = i+1;k < j;k++){ int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j]){ m[i][j] = t; s[i][j] = k;} } } } O的定义: 如果存在两个正常数c和n0,对于所有的n≥n0时,有: |f(n)|≤c|g(n)|,称函数f(n)当n充分大时的阶比g(n)低,记为 f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义: 如果存在正常数c和n0,对于所有n≥n0时,有: |f(n)|≥c|g(n)|,则称函数f(n)当n充分大时下有界,且g(n)是它的一个下界,即f(n)的阶不低于g(n)的阶。记为: f(n)=Ω(g(n))。Θ的定义: 如果存在正常数c1,c2和n0,对于所有的n>n0,有: c1|g(n)|≤f(n)≤c2|g(n)|,则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法: O(1) (2)指数时间算法: O(2n) Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call chess(n-1) 贪心方法基本思想: 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择 所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。 多段图: COST[j]=c(j,r)+COST[r]; 回溯法: (假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi),看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解,那么就将可能要测试的mi+1…mn个向量略去。约束条件: (1)显式约束:限定每一个xi只能从给定的集合Si上取值。 (2)解 空 间:对于问题的一个实例,解向量满足显式 约束条件的所有多元组,构成了该实例 的一个解空间。 (3)隐式约束:规定解空间中实际上满足规范函数的元 组,描述了xi必须彼此相关的情况。基本做法: 在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解:如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。 8皇后问题 约束条件 限界函数: 子集和数问题: 约束条件 限界函数: 回溯法--术语: 活结点:已生成一个结点而它的所有儿子结点还没有 全部生成的结点称为活结点。 E-结点:当前正在生成其儿子结点的活结点叫E-结点。 死结点:不再进一步扩展或其儿子结点已全部生成的结点称为死结点。 使用限界函数的深度优先节点生成的方法成为回溯法;E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法 且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别: 分支限界法本质上就是含有剪枝的回溯法,根据递归的条件不同,是有不同的时间复杂度的。 回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列,优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解 一般如果只考虑时间复杂度二者都是指数级别的 可是因为分支限界法存在着各种剪枝,用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){ int j; X[k]=1; if(s+W[k]==M){ for(j=1;j<=k;j++) printf(“%d ”,X[j]); printf(“n”); } else if((s+W[k]+W[k+1])<=M){ sumofsub(s+W[k],k+1,r-W[k]); } if((s+r-W[k]>=M)&&(s+W[k+1]<=M)){ X[k]=0; sumofsub(s,k+1,r-W[k]); } } void main(){ M=30; W[1]=15; W[2]=9; W[3]=8; W[4]=7; W[5]=6; W[6]=5; W[7]=4; W[8]=3; W[9]=2; W[10]=1; sumofsub(0,1,60);} P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L,则此问题L是NP-难度的。如果L是NP难度的且L NP,则此问题是NP-完全的 1、PROLOG程序一般由一组事实、规则和问题组成。事实一般表示对象的性质或关系;规则一般表示对象间的因果关系、蕴含关系或对应关系; 问题表示用户的询问是程序运行的目标。问题是程序执行的起点,称为程序的目标。PROLOG就是一种基于Horn子句的逻辑程序。 PROLOG程序的运行是从目标出发,并不断进行匹配、合一、归结,有时还要回溯,直到目标别完全满足或不能满足时为止。 PROLOG程序的执行过程是一个(归结)演绎推理过程。其特点是:推理方式为反向推理, 控制策略是深度优先, 且有回溯机制。 3、简述用A*算法求解问题时为什么会出现重复扩展节点问题,解决的方法有哪些? 答:当问题有解时,A*算法总是找到问题的最优解结束。如果h函数定义的不合理,则当扩展一个节点时,不一定就找到了从初始节点到该节点的最优路径,对于这样的节点,就有可能被多次扩展。特别是如果这样的节点处于问题的最优解路径上时,则一定会被多次扩展。解决的方法一是对h函数的定义给出限制,使得h满足单调性。对于满足单调性条件的h,则一定不会出现重复扩展节点问题。二是对A*算法加以改进,使用修正的A*算法进行搜索,这样,随着经验的丰富,系统的性能自然就会不断改善和提高。 24、机器学习的三个要素:信息,发展和知识。对应于机器学习的对象、方法和目标。 25、基于学习策略的分类:符号学习和神经网络学习。 26、决策树:也称判断树,它由对象的若干属性、属性值和有关决策组成的一棵树。其中的节点为属性,分支为属性值,从同一节点出发的各个分支之间是逻辑或关系,根节点为对象的一个属性;从根节点出发到每一个叶子节点的所有节点和边,按顺序串联成一条分支路径,位于同一分支路径上的各个属性-值对之间是逻辑与关系,叶子节点是这个与关系的对应结果,即决策。 27、决策树学习首先要有一个实例集,基本方法和步骤:(1)选取一个属性,按这个属性的不同取值对实例集进行分类;并以该属性作为根节点,以这个属性的诸取值作为根节点的分支,进行画树;(2)考察所得的每一个子类,看其中的实例的结论是否完全相同。如果相同,则以这个相同的结论作为相应分支路径末端的叶子节点;否则,选取一个非父节点的属性,按这个属性的不同取值对孩子集进行分类,并以该属性作为节点,以这个属性的诸取值作为节点的分支,继续进行画树。如此继续,直到所分的子集全都满足:实则可以减少重复扩展节点问题。 4、简述回溯策略与深度优先策略的不同点。 答:回溯搜索策略与深度有限搜索策略最大的不同是深度有限搜索策略属于图搜索,而回溯搜索则不是图搜索。在回溯搜索中,只保留了从初始节点到当前节点的搜索路径。而深度优先搜索,则保留了所有的已经搜索过的路径。 5、不确定性类型按性质分:随机性,模糊性,不完全性,不一致性 6、在删除策略归结的过程中删除以下子句:含有纯文字的子句;含 有永真式的子句;子句集中被别的子句类含的子句。 7、图:指由节点和有向边组成的网络。按连接同一节点的各边的逻辑关系又可分为或图和与或图。 8、合一算法:求非空有限具有相同谓词名的原子公式集的最一般合一(MGU)。 9、人工智能的远期目标是制造智能机器,近期目标是实现机器智能。 10、什么是产生式?产生式规则的语义是什么? 产生式规则基本形式:P→Q 或者 IF P THEN Q P 是产生式的前提(前件),用于指出该产生式是否可用的条件 Q 是一组结论或操作(后件),用于指出当前提 P 所指示的条件满足时,应该得出的结论或应该执行的操作 产生式规则的语义:如果前提P被满足,则可推出结论 Q 或执行 Q 所规定的操作 11、谓词公式G通过8个步骤所得的子句集合S,称为G的子句集。请写出这些步骤:1)消去蕴含式和等价式→,<-> ;2)缩小否定词的作用范围,直到其作用于原子公式: ;3)适当改名,使量词间不含同名指导变元和约束变元。;4.)消去存在量词(形成Skolem标准型);5)消去所有全称量词 ;6)化成合取范式;7).适当改名,使子句间无同名变元;8).消去合取词∧,用逗号代替,以子句为元素组成一个集合S 12、人工智能的基本技术包括搜索技术 推理技术 知识表示和知识库技术、归纳技术、联、想技术 13、产生式系统有三部分组成综合数据库,知识库和推理机。其中推理可分为正向推理和反向推理。 14、在归结原理中,几种常见的归结策略并且具有完备性的是删除策略 支持集策略 线性归结策略、输入归结策略、单元归结策略 15、归结法中,可以通过修改证明树的方法得到问题的解答 16、开发专家系统所要解决的基本问题有三个,那就是知识的获取、知识的表示和知识的运用,在语义网络表示知识时,所使用的推理方法有AKO 和ISA。 17、α-β剪枝的条件是:α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值节点的α值,即α(先辈层)≥β(后继层),则可中止该极小值层中这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。 β剪枝:若任一极大值层节点的α值大于或等于它任一先辈极小值层节点的β值,即α(后继层)≥β(先辈层),则可以中止该极大值层中这个MAX节点以下的搜索过程。这个MAX节点的最终倒推值就确定为这个α值。 18、知识表示的方法主要有逻辑表示法(谓词表示法)框架 产生式和语义网络,类和对象,模糊集合,因果网络,脚本,过程等 19、知识的分类:(1)就形式而言:显示和隐式。显示知识是指可用语言文字符号形象声音及其他人能直接识别和处理的形式,明确的在其载体上表示出来的知识。隐式知识只可用神经网络存储和表示(2)就严密性和可靠性而言:理论知识和经验知识(3)就确定性而言:确定性知识和不确定知识(4)就确切性而言:确切描述的知识和非确切描述的知识。 20、知识表示是指面向计算机的知识描述或表达形式和方法。具体的讲就是要用某种约定的形式结构来描述知识,而且这种形式结构还要能够转换为机器的内部形式,使的计算机能方便的存储、处理和应用。------知识表示是建立专家系统级各种知识系统的重要环节,也是知识工程的一个重要方面。 21、基于谓词逻辑的推理主要是演绎方式的推理;基于框架、语义网络和对象知识表示的推理是一种称为继承的推理。 22、机器学习:主要指机器对自身行为的修正或性能的改善和机器对客观规律的发现。(让计算机模拟人的学习行为,或者说让计算机也具有学习的能力) 23、机器学习的流程:(1)对于输入的信息,系统根据目标和经验做出决策予以响应,即执行相应的动作;(2)对目标的实现或任务的完成情况进行评估;(3)将本次的输入、响应和评价作为经验予以存储记录。可以看出,第一次决策时系统中还无任何经验,但从第二此决策开始,经验便开始积累。 例结论完全相同,而得到所有的叶子节点为止。这样一棵决策树就被生成。 28、神经网络分为四大类:分层前向网络、反馈前向网络、互联前向网络、广泛互联网络。 29、网络学习一般是利用一组称为样本的数据,作为网络的输入(和输出),网络按照一定的规则自动调节神经元之间的连接强度或拓扑结构,当网络的实际输出满足期望的要求,或者趋于稳定是,则认为学习成功。 30、神经网络学习的规则是权值修正规则:相关规则和误差修正规则。 31、神经网络学习方法分类:(外部影响)有导师学习,强化学习,无导师学习;(内部变化)权值修正,拓扑变化,权值与拓扑修正;(算法性质)确定性学习,随机性学习;(输入要求)基于相似性学习,基于命令学习。 32、专家系统:应用于某一专门领域,拥有该领域相当数量的专家级知识,能模拟专家的思维,能达到专家级水平,像专家一样解决困难、复杂的实际问题的计算机(软件)系统。 33、专家系统的基本要素:专家拥有丰富的专业知识和实践经验或者说拥有丰富的理论知识和经验知识,特别是经验知识。 34、专家系统与一般的软件系统开发无异,其开发过程同样要遵循软件工程的步骤和原则,即也要进行系统分析、系统设计等几个阶段的工作。 但由于它是专家系统,而不是一般的软件系统,所以,又有其独特的地方,主要包括以下几个步骤: 系统总体分析与设计;知识获取;知识表示与知识描述语言设计;知识库设计、知识库管理系统设计;推理机与解释模块设计;总控与界面设计;编程与调试;测试与评价;运行与维护。可以看出它有如下特点:知识获取和知识表示设计是一切工作的起点;知识表示与知识描述语言确定后,其他设计可同时进行; 35、对涉及人工智能的一些问题的认识:首先人工智能把人脑更有效的扩大和延伸是人类智能扩大的延伸,人工智能的应用十分广泛:机器翻译、智能控制、模式识别、机器博弈等,运用智能技术解决很多的实际问题从而使现有的计算机更有效更灵活成为人类智能化信息处理的工具。人工智能用计算机模拟人的思维活动包含理解能力、学习能力、推理能力,主要是脑功能的结构模拟和功能模拟。然而人类不能赋予机器同等的情感,无法确保责任问题,此外生物物种灭绝新型细菌的出现,人类的未来难以预料 37、能解节点定义如下: ①(终节点)是能解节点; ②若非终节点有(“或”)子节点时,当且仅当其子节点至少有一能解,该非终节点才能解; ③若非终节点有(“与”)子节点时,当且仅当其子节点均能解,该非终节点才能解。 18、局部图的耗散值定义如下: ①若n是局部图的一个叶节点,则k(n,N)=(h(n)),其中(h(n))表示节点n到目标节点集的最佳解图耗散值的估计; ②若n由一个外向连接符指向后继节点{n1,…,ni},并设该连接符的耗散值为Cn,则k(n,N)=(Cn+ k(n1,N)+ … + k(ni,N))。 19、耗散值最小的解图称为(最佳)解图 20、AO*算法是一种用于对(与或图)进行搜索的启发式搜索算法,该算法对目前找到的局部图进行评价,选择(耗散值最小)的局部图进行优先搜索,直到找到一个解图为止。当启发函数h满足(单调)条件时,在问题有解的情况下,AO*算法一定能找到最佳解图结束。 21、所谓“图灵实验”,是为了判断一台机器是否具备智能的实验。实验由三个封闭的房间组成,分别放置主持人、参与人和机器。主持人向参与人和机器提问,通过提问的结果来判断谁是人,谁是机器。如果主持人无法判断谁是人,谁是机器,则这台机器具备智能,即所谓的“智能机器”。 22/深度优先方法的特点是什么?属于图搜索;是一个通用的搜索方法;如果深度限制不合适,有可能找不到问题的解;不能保证找到最优解。 23/什么是置换?置换是可交换的吗?通常用有序对的集合s={t1/v1,t2/v2,„,tn/vn}来表示任一置换,置换集的元素ti/vi的含义是表达式中的变量vi处处以项ti来替换,用s对表达式E作置换后的例简记为Es。一般来说,置换是不可交换的,即两个置换合成的结果与置换使用的次序有关。第四篇:算法总结材料
第五篇:人工智能总结(精华版)