数学建模算法设计简介ppt课件

算法设计简介,问题求解概述,问题求解的一般步骤：,需求分析,建模,算法设计,程序实现,测试,应用,分析输入输出数据，设计合理的数据结构,设计适当的算法，确立输入输出之间的函数关系。比如，计算参数模型的函数参数，或者函数逼近（神经网络等方法）,建模方法,差分方程、差分方程组：抵押贷款买房问题等模型拟合：最小二乘法、三阶样条模型等概率模型：线性回归，随机行为模拟等线性规划：单纯形法等图论建模：最短路径问题、最大流问题等决策论：决策树、序列决策博弈论：囚徒困境问题微分方程、微分方程组建模：人口增长模型、传染病模型,模型的设计与实现数据结构,数据模型：数据对象，数据对象之间的关系数据对象之间的关系：逻辑结构，物理结构逻辑结构：线性结构，树形结构，图形结构，集合结构物理结构：顺序存储，链式存储，索引存储，散列存储,算法设计,算法：,输入数据,算法模块,输出结果,对于用户来讲，算法模块就是黑匣子,算法设计方法,算法,确定的,非确定的,传统算法：,近似算法：,随机算法：,智能算法：,以100%成功概率求解问题的最优解,对解的质量让步,对求解成功概率和解的质量让步,遗传算法，模拟退火算法，蚁群算法，神经网络算法等等,算法设计思想,枚举法：也称穷举法。归纳法：也就是通常的找规律。递推法：类似归纳，竞赛中的数学题常常需要递推和归纳。递归法：递归分为直接递归和间接递归，很多问题都需要借助递归思想和方法求解，包括分治、DP的题目。回溯法：也即试探法。迭代法：迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。迭代思想是很多问题求解或代码实现的基本方法。,从问题求解基本思路看，算法设计思想有如下几种：,算法设计方法（1）贪心法,（1）贪心法(greedymethod),算法思想：在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的决策(在一定的准则下)。决策一旦做出，就不可再更改。做出贪婪决策的依据称为贪婪准则。,贪心法采用的是局部最优策略，而局部最优有时并不保证全局最优。当然，有许多应用问题只要近似最优即可，对这些问题的求解贪心法还是非常实用的。,例如，找零钱问题，用贪心法可以求得最优解。,算法设计方法（2）分治法,（2）分治法（DivideandConquerMethod）,算法思想：把它分成两个或多个更小、更简单的问题；分别解决每个小问题；把各个小问题的解答组合起来，即可得出原问题的解。,典型案例：汉诺塔问题,算法设计方法（3）动态规划,算法思想：将一个问题的解决方案视为一系列决策的结果，并考察每个最优决策序列中是否包含一个最优子序列。动态规划方法采用最优原则来建立用于计算最优解的递归式。,（3）动态规划(DynamicProgramming),最优原则：即不管前面的策略如何，此后的决策必须是基于当前状态的最优决策。若不能保持最优原则，则不可应用动态规划方法。,动态规划的数学表现是递归、排列组合，在递归过程中会出现重复计算问题，为了解决这个开销，使用二维表格保存已计算出的结果，以便复用。,算法设计方法（4）,算法思想：回溯是一种系统地搜索问题解的方法。为了实现回溯，首先需要为问题定义一个解空间（solutionspace），这个空间必须至少包含问题的一个解（可能是最优的）。,（4）回溯法（backtrackingMethod）,回溯方法的步骤如下：定义一个解空间，它包含问题的解；用适合于搜索的方式组织该空间；用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。,算法设计方法（5）分支定界,算法思想：分支定界是另一种系统地搜索解空间的方法，回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。建立一个活节点表。每个活节点仅有一次机会可以扩充，生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表。直到找到解或活动表为空，扩充过程才结束。,（5）分支限界（branchandbound）,算法设计方法（6）随机算法,算法思想：在算法中引入随机因素，即通过随机因素选择算法的下一步操作。在许多情况下，一般算法比较复杂，性能较差，很多具有很好平均运行时间的算法，在最坏的情况下，却具有很坏的性能。采用随机算法可以实现“平均情况下的”良好业绩的希望。,（6）随机算法（RandomizedAlgorithms）,随机算法对所求解问题的同一个实例用同一随机算法求解两次可能得到完全不同的效果。这两次求解所需要的时间，甚至所得到的结果都可能会有相当大的差别。随机算法包括：数值概率算法蒙特卡罗（MonteCarlo）算法拉斯维加斯（LasVegas）算法舍伍德（Sherwood）算法,分治法,分治策略：分治法是一种常用的算法技巧，从字面上的看就是“分而治之”的意思，把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，将子问题的解的合并就得到原问题的解。,分治法在每一层递归上都有三个步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；合并：将各个子问题的解合并为原问题的解。,分治法,一、二基本都能满足，三是关键，能否利用分治法完全取决于问题是否具有第三条特征。不具备第三条特征，则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率，不能满足时采用动态规划法比用分治法更好。,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,分治法,分治法算法框架SolutionTypeDandC(ProblemTypeP)ProblemTypeP1,P2,.,Pk;if(Small(P)returnS(P);/解决小规模的问题elseDivide(P,P1,P2,.,Pk);/将问题分解成子问题P1,P2,.,PkreturnCombine(DandC(P1),DandC(P2),.,DandC(Pk);/递归的解各子问题,并将各子问题的解合并为原问题的解,最近点对问题,问题描述：在二维平面上的n个点中，如何快速的找出最近的一对点。最简单的想法是暴力枚举每两个点，计算得出最小距离，需要计算n(n-1)/2次，时间复杂度为O(n2),分治法求最近点对问题,算法描述：已知集合S中有n个点，分治法的思想就是将S进行拆分，分为2部分求最近点对。算法每次选择一条垂线L，将S拆分左右两部分为SL和SR，L一般取点集S中所有点的中间点的x坐标来划分，这样可以保证SL和SR中的点数目各为n/2，依次找出这两部分中的最小点对距离：L和R，记SL和SR中最小点对距离=min（L，R）。,分治法求最近点对问题,对于SL虚框范围内的p点，在SR虚框中与p点距离小于的顶多只有六个点，就是下图中的2个正方形的6的顶点。（如果有第7个点则与的定义矛盾）因此，计算时，只需计算SR中与p点距离最近的6个点，就可以求出最近点对。,以L为中心，为半径划分一个长带，最小点对还有可能存在于SL和SR的交界处，如右图中的虚线带，p点和q点分别位于SL和SR的虚线范围内，在这个范围内，p点和q点之间的距离才会小于，最小点对计算才有意义。,贪心法,能够使用贪心算法的问题必须满足下面两个性质：整体的最优解可以通过局部的最优解来求出；一个整体能够被分为多个局部，并且这些局部都能够求出最优解。,贪心算法的基本步骤：从问题的某个初始解出发；当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模；将所有部分解综合起来，得到问题的最终解。,在一些情况下，即使贪心算法不能得到整体最优解，但其近似最优解在许多情况下已经能满足某些问题的求解要求了。,背包问题,背包问题：给定n种物品和一背包。每种物品i的重量是wi，其价值为vi，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i的选择，可以是装入背包或不装入背包或只装入部分的物品i。该问题称为分数背包问题。如果在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。,0-1背包问题,0-1背包问题：对于0-1背包问题，贪心选择可能得不到最优解。因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间，使得每公斤背包空间的平均价值被降低了。考虑在下面的0-1背包问题实例中，选择贪心策略为尽量装单位价值最大的物品，贪心策略得到的解不是最优的。,多机调度问题,多机调度问题：某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。要求算出n个作业由m台机器加工处理的最短时间。,这个问题是NP完全问题，到目前为止还没有有效的解法。,NP完全问题,NP完全问题（多项式复杂程度的非确定性问题）：生成问题的一个解通常比验证一个给定的解时间花费要多得多。在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。主人向你提议说，你一定认识那位正在甜点盘附近角落的女士。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。,多机调度问题的近似算法,解题思路：（1）当nm时，首先将n个作业从大到小排序。然后依此顺序分步将作业分配给空闲的处理机，每步分配给一个机器，而且需要考虑分配哪一个作业。根据这种思想可利用如下贪心原则：从剩下的作业中，选择需要处理时间最长，然后依次选择处理时间次长的作业，直到所有的作业全部处理完毕，或者机器不能再处理其他作业。,采用最长处理时间作业优先的贪心选择策略，可以设计出解多机调度问题的较好的近似算法。,贪心法,很多情况下，贪心算法不能得到整体最优解，尽管如此，贪心算法也是应用最广泛的算法之一。许多时候，其近似最优解已经能满足问题的求解要求了。贪心算法在计算时最大的缺点是：在迭代时，很多时候会掉入到局部最优解，从而无法得到整体最优解。改进：模拟退火算法、遗传算法等,回溯法,回溯法实际上是基于穷举的方法。四个环节：确定问题的可能解空间，相当于找出进行穷举的搜索范围。以一种便于搜索的方式组织所有的可能解，一般是生成可能解空间树。以深度优先搜索方式搜索可能的解空间树（回溯技术）。在搜索过程中利用判定函数，也称为限界函数，通过“剪枝”来加速搜索过程。,回溯法0-1背包问题,0-1背包问题：n=3，w=16,15,15,p=45,25,25,c=30。解空间可以用完全二叉树表示，叶子结点如下：(1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0)求解过程相当于在树中搜索满足条件的叶结点。子集树：当所给问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。,回溯法旅行商问题,旅行商问题：设G是带权图。图中各边的费用（权）为一正数。一条周游路线是包括图中每个顶点的一条回路。其费用就是该路线上所有边的费用总和。对于该问题，每一个旅行可表示为顶点序列的一个排列。在解空间树中，每一个旅行都由树中的一条从根到叶的路径来表示。排列树：当所给问题时确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。,回溯法递归实现,递归回溯：回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。voidbacktrack(intt)/t表示递归深度if(tn)output(x);/n表示深度界限elsefor(inti=f(n,t);i0)if(f(n,t)=g(n,t)for(inti=f(n,t);i=g(n,t);i+)xt=h(i);if(constraint(t),八皇后问题,八皇后问题：在88格的国际象棋上摆放八个皇后，使其不能互相攻击。例如，八皇后问题的一个解：可由八元组（4,6,8,2,7,1,3,5)来表示。是1到8共8个数字的全排列。,四皇后问题,为了简化问题，我们讨论四皇后问题。解空间树是一个完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。回溯法求解4皇后问题，是对完全4叉树的搜索过程,四皇后问题回溯过程-1,四皇后问题的回溯算法的搜索过程图示从结点1到结点2，满足条件，放置皇后x1=1,继续搜索,四皇后问题回溯过程-2,结点3不满足条件，回溯到结点2；再向下搜索到结点8；满足条件，放置皇后x2=3,继续搜索,四皇后问题回溯过程-3,结点9不满足条件，回溯到结点11，仍不满足条件；这时经结点8，回溯到结点2,四皇后问题回溯过程-4,向下搜索到结点13，满足条件，放置第二个皇后x2=4;继续向下搜索到结点14，满足条件，放置第三个皇后x3=2;,四皇后问题回溯过程-5,向前搜索到结点15，不满足条件（只测试x4=3的情形），回溯搜索到结点16，仍不满足条件,四皇后问题回溯过程-6,回溯到结点1后，向下搜索到结点18，x1=2,四皇后问题回溯过程-7,结点19不满足条件，回溯到结点24后，也不满足条件；回溯到结点29之后满足条件，x2=4,四皇后问题回溯过程-8,结点30满足条件，x3=1；再向前搜索到结点31，满足条件，x4=3；此时，i=4，找到解,0-1背包问题的回溯算法,0-1背包问题：以n=3，w=16,15,15,p=45,25,25,c=30。为例：解空间可以用完全二叉树表示(1,1,1),(1,1,0),(1,0,1),(1,0,0),(0,1,1),(0,1,0),(0,0,1),(0,0,0),0-1背包问题的回溯算法,E-结点和活结点死结点,R=14V=45,R0wTxi0Rosenblatt1958首次提出了感知器的学习算法。这个算法是错误驱动的在线学习算法。先初始化一个权重向量w0（通常是全零向量），然后每次分错一个样本时，就用这个样本来更新权重。,二类感知器学习算法,二类感知器学习算法,单层感知器的局限,感知器的输出只能取0或1。单层感知器只能对线性可分的向量集合进行分类。明斯基（Minsky）于1969年发表了Perceptron一书。书中指出感知器仅能解决一阶谓词逻辑问题，不能解决高阶谓词逻辑问题,并给出了一个简单的例子，即XOR（异或）问题,BP神经网络,BP网络是在输入层与输出层之间增加若干层(一层或多层)神经元，这些神经元称为隐单元BP神经网络的计算过程由正向计算过程和反向计算过程组成。正向传播过程，输入模式从输入层经隐单元层逐层处理，并转向输出层，每一层神经元的状态只影响下一层神经元的状态。如果在输出层不能得到期望的输出，则转入反向传播，将误差信号沿原来的连接通路返回，通过修改各神经元的权值，使得误差信号最小。BP网络主要用于以下四个方面1)函数逼近：用输入向量和相应的输出向量训练一个网络逼近一个函数。2)模式识别：用一个待定的输出向量将它与输入向量联系起来。3)分类：把输入向量所定义的合适方式进行分类。4)数据压缩：减少输出向量维数以便于传输或存储。,BP神经网络,例:一个多层前馈神经网络训练样本X=x1,x2,.,xi馈入输入层.每层之间存在加权连接;其中,wij表示由某层的单元j到前一层的单元i的权,反向传播算法,反向传播算法:例,一个多层前馈神经网络第一个训练样本X=1,0,1（其类标号为1）,反向传播算法:例(续),初始输入、权值和偏差值净输入和输出的计算计算每个结点的误差,反向传播算法:例(续),计算权和偏置的更新,BP神经网络的几个问题,收敛速度问题BP神经网络收敛速度相对是比较慢的。训练ANN是一个很耗时的过程局部极小点问题使用的梯度下降方法经常会收敛到局部最小值逃离/避开局部极小点：修改W、V的初值并不是总有效。网络瘫痪问题在训练中，权可能变得很大，这会使神经元的网络输入变得很大，从而又使得其激活函数的导函数在此点上的取值很小。此时的训练步长会变得非常小，进而将导致训练速度降得非常低，最终导致网络停止收敛,BP算法中的梯度消失问题,误差从输出层反向传播时，在每一层都要乘以该层的激活函数的导数。当我们使用sigmoid型函数：logistic函数(x)或tanh函数时，其导数为：(x)=(x)(1(x)0,0.25tanh(x)=1(tanh(x)20,1可以看到，sigmoid型函数导数的值域都小于1。这样误差经过每一层传递都会衰减。当网络层数很深时，梯度就会不停的衰减，甚至消失，使得整个网络很难训练。这就是所谓的梯度消失问题（VanishingGradientProblem），也叫梯度弥散。,深度神经网络,2006年，加拿大多伦多大学教授、机器学习领域的泰斗GeoffreyHinton在科学上发表论文提出深度学习主要观点：1）多隐层的人工神经网络具有优异的特征学习能力，学习得到的特征对数据有更本质的刻画，从而有利于可视化或分类；2）深度神经网络在训练上的难度，可以通过“逐层初始化”（layer-wisepre-training）来有效克服，逐层初始化可通过无监督学习实现的。,深度学习vs.神经网络,神经网络：深度学习：,深度学习训练过程,第一步：采用自下而上的无监督学习1）逐层构建单层神经元。2）每层采用wake-sleep算法进行调优。每次仅调整一层，逐层调整。这个过程可以看作是一个featurelearning的过程，是和传统神经网络区别最大的部分。,深度学习训练过程,wake-sleep算法:1）wake阶段：认知过程，通过下层的输入特征（Input）和向上的认知（Encoder）权重产生每一层的抽象表示（Code），再通过当前的生成（Decoder）权重产生一个重建信息（Reconstruction），计算输入特征和重建信息残差，使用梯度下降修改层间的下行生成（Decoder）权重。也就是“如果现实跟我想象的不一样，改变我的生成权重使得我想象的东西变得与现实一样”。2）sleep阶段：生成过程，通过上层概念（Code）和向下的生成（Decoder）权重，生成下层的状态，再利用认知（Encoder）权重产生一个抽象景象。利用初始上层概念和新建抽象景象的残差，利用梯度下降修改层间向上的认知（Encoder）权重。也就是“如果梦中的景象不是我脑中的相应概念，改变我的认知权重使得这种景象在我看来就是这个概念”。,深度学习训练过程,Encoder,Decoder,InputImage,Classlabel,Features,Encoder,Decoder,Features,Encoder,Decoder,AutoEncoder:,深度学习训练过程,第二步：自顶向下的监督学习这一步是在第一步学习获得各层参数进的基础上，在最顶的编码层添加一个分类器（例如罗杰斯特回归、SVM等），而后通过带标签数据的监督学习，利用梯度下降法去微调整个网络参数。深度学习的第一步实质上是一个网络参数初始化过程。区别于传统神经网络初值随机初始化，深度学习模型是通过无监督学习输入数据的结构得到的，因而这个初值更接近全局最优，从而能够取得更好的效果。,深度神经网络,卷积网络循环神经网络无监督卷积网络深度玻尔兹曼机分布式自编码器回声状态网络深度信念网络,卷积神经网络,CNN（卷积神经网络）的核心出发点有三个局部感受野。模仿眼睛看东西的时候，目光是聚焦在一个相对很小的局部。在卷积神经网络中，每个隐层节点只连接到图像某个足够小局部的像素点上，从而大大减少需要训练的权值参数。权值共享。如同某个神经中枢中的神经细胞，它们的结构、功能是相同的，甚至是可以互相替代的。在卷积神经网中，同一个卷积核内，所有的神经元的权值是相同的，从而大大减少需要训练的参数。池化如同人的视觉，先随便看向远方，然后闭上眼睛，你仍然记得看到了些什么，但是你不会完全回忆起每一个细节？在卷积神经网络中，没有必要一定就要对原图像做处理，而是可以使用某种“压缩”方法，这就是池化，也就是每次将原图像卷积后，都通过一个下采样的过程，来减小图像的规模。,卷积神经网络,FeatureextractionlayerConvolutionlayer,ShiftanddistortioninvarianceorSubsamplinglayer,C,S,Featuremaps,卷积神经网络,卷积假设有二维离散函数f(x,y),g(x,y)，那么它们的卷积定义为图中神经元的卷积如下,卷积神经网络,卷积层对数据进行特征提取,卷积神经网络,下采样下采样，即池化，目的是减小特征图，池化规模一般为22。常用的池化方法有：最大池化（MaxPooling）。取4个点的最大值。这是最常用的池化方法。均值池化（MeanPooling）。取4个点的均值。高斯池化。借鉴高斯模糊的方法。不常用。可训练池化。训练函数f，接受4个点为输入，出入1个点。不常用。由于特征图的变长不一定是2的倍数，所以在边缘处理上也有两种方案：忽略边缘。即将多出来的边缘直接省去。保留边缘。即将特征图的变长用0填