数学建模十大经典算法(__数学建模必备资料)

Fromclownstudio建模十大经典算法1、蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时通过模拟可以来检验自己模型的正确性。2、数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。3、线性规划、整数规划、多元规划、二次规划等规划类问题。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo、MATLAB软件实现。4、图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。5、动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中。6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法。这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。7、网格算法和穷举法。网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，最好使用一些高级语言作为编程工具。8、一些连续离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。9、数值 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法。如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。10、图象处理算法。赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图Fromclownstudio形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。历年全国数学建模试题及解法赛题解法93A非线性交调的频率设计拟合、规划93B足球队排名图论、层次分析、整数规划94A逢山开路图论、插值、动态规划94B锁具装箱问题图论、组合数学95A飞行管理问题非线性规划、线性规划95B天车与冶炼炉的作业调度动态规划、排队论、图论96A最优捕鱼策略微分方程、优化96B节水洗衣机非线性规划97A零件的参数设计非线性规划97B截断切割的最优排列随机模拟、图论98A一类投资组合问题多目标优化、非线性规划98B灾情巡视的最佳路线图论、组合优化99A自动化车床管理随机优化、计算机模拟99B钻井布局0-1规划、图论00ADNA序列分类模式识别、Fisher判别、人工神经网络00B钢管订购和运输组合优化、运输问题01A血管三维重建曲线拟合、曲面重建01B公交车调度问题多目标规划02A车灯线光源的优化非线性规划02B彩票问题单目标决策03ASARS的传播微分方程、差分方程03B露天矿生产的车辆安排整数规划、运输问题04A奥运会临时超市网点设计统计分析、数据处理、优化04B电力市场的输电阻塞管理数据拟合、优化05A长江水质的 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 和预测预测评价、数据处理05BDVD在线租赁随机规划、整数规划Fromclownstudio06A出版资源配置06B艾滋病疗法的评价及疗效的预测07A中国人口增长预测07B乘公交，看奥运多目标规划数据处理图论08A数码相机定位08B高等教育学费 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 探讨09A制动器试验台的控制方法分析09B眼科病床的合理安排动态规划10A10B赛题发展的特点：1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B，某些问题需要使用计算机软件，01A。问题的数据读取需要计算机技术，如00A（大数据），01A（图象数据，图象处理的方法获得），04A（数据库数据，数据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果。2.赛题的开放性增大解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对数据处理上。3.试题向大规模数据处理方向发展4.求解算法和各类现代算法的融合从历年竞赛题来看，常用的方法：线性规划整数规划非线性规划动态规划层次分析法图论方法拟合方法插值方法随机方法微分方程方法各种算法的详解一、蒙特卡洛算法1、含义的理解以概率和统计理论方法为基础的一种计算方法。也称统计模拟方法，是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法，它是将所求解的问题同一定的概率模型相联系，用计算机实现统计模拟或抽样，以获得问题的近似解。2、算法实例（有很多相似的例题，包括平行线等）在数值积分法中，利用求单位圆的1/4的面积来求得Pi/4从而得到Pi。单位圆的1/4面积是一个扇形，它是边长为1单位正方形的一部分。只要能求出扇形面积S1在正方形面积S中占的比例K=S1/S就立即能得到S1，从而得到Pi的值。怎样求出扇形面积在正方形面积中占的比例K呢？一个办法是在正方形中随机投入很多点，使所投的点落在正方形中每一个位置的机会相等看其中有多少个点落在扇形内。将落在扇形内的点数m与所投点的总数n的比m/n作为k的近似值。P落在扇形内的充要条件是221xy。Fromclownstudio已知：K=1ss，Kmn，s=1，s1=4Pi，求Pi。由1smsn，知s1*msn=mn，而s1=4Pi，则Pi=*4mn程序：（该算法可以修改后用Mathematica计算或者Matlab）/*利用蒙特卡洛算法近似求圆周率Pi*//*程序使用：VC++6.0*/#include<stdio.h>#include<math.h>#include<stdlib.h>#defineCOUNT800/*循环取样次数，每次取样范围依次变大*/voidmain(){doublex,y;intnum=0;inti;for(i=0;i<COUNT;i++){x=rand()*1.0/RAND_MAX;/*RAND_MAX=32767，包含在<stdio.h>中*/y=rand()*1.0/RAND_MAX;if((x*x+y*y)<=1)num++;/*统计落在四分之一圆之内的点数*/}printf("Pi值等于：%f\n",num*4.0/COUNT);}结果：测试6次的结果显示：循环取样次数求得的Pi值8003.08500080003.110000800003.1352008000003.13915080000003.141393Fromclownstudio800000003.141321可以看出:随着点数的增加，求得的Pi值渐渐接近真实值。如果加入程序：srand(time(NULL));，同时循环取样次数一定，让取样结果随时间变化，当取样次数为80000000时，可得6次的结果显示：3.1412903.1414003.1412683.1414843.1413583.1414623、应用的范围蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。4、参考书籍[1]蒙特卡罗方法及其在粒子输运问题中的应用[2]蒙特卡罗方法引论二、数据拟合、参数估计、插值等数据处理算法（1）数据拟合在Mathematica中，用Fit对数据进行最小二乘拟合：Fit[data,funs,vars]在Matlab中，工具箱（toolboxes）中有曲线拟合工具（curveFitting）。实例：2010年苏北赛B题温室中的绿色生态臭氧病虫害防治中关于中华稻蝗密度与水稻减产率之间的关系可以通过数据拟合来观察（简单举例，没有考虑全部数据）数据：密度（头/m2）310203040减产率（%）2.412.916.320.126.8程序（Mathematica）：data={{3,2.4},{10,12.9},{20,16.3},{30,20.1},{40,26.8}};a1=Fit[data,{1,x,x^2,x^3},x]Show[ListPlot[data,Filling->Axis],Plot[{a1},{x,0,60}]]结果：-3.68428+2.38529x-0.0934637x2+0.00132433x3（2）参数估计（参考书：概率论与数理统计）参数估计为统计推断的基本问题，分为点估计和区间估计。点估计：①矩估计法X连续型随机变量，概率密度12(;,,)nfxX为离散型随机变量分布律12{}(;,,,)kPXxpx12,,,k为待估参数，12,,nXXX是来自X的样本，假设总体X的前k阶矩存在，为Fromclownstudio12()(;,,)lllnEXxfxdx（X连续型）或12()(;,,,)XlllkxREXxpx（X离散型）1,2,,lk（其中XR是X可能取值的范围）。一般来说，它们是12,,,k的函数。基于样本矩11nlliiAXn依概率收敛于相应的总体矩(1,2,)llk，样本矩的连续函数依概率收敛于相应的总体矩的连续函数，我们就用样本矩作为相应的总体矩的估计量，而以样本矩的连续函数作为相应的总体矩的连续函数的估计量。这种估计方法成为矩估计法。②最大似然估计法X连续型随机变量似然函数121()(,,,;)(;)nniiLLxxxfx其中1(;)niifx是来自X的样本12,,nXXX的联合密度。X为离散型随机变量似然函数121()(,,,;)(;),nniiLLxxxpx其中1(;)niipx是来自X的样本12,,nXXX的联合分布律。若1212ˆ()(,,,;)max(,,,;)nnLLxxxLxxx则称12ˆ(,,,)nxxx为的最大似然估计值，称12ˆ(,,,)nXXX为的最大似然估计量。这样，确定最大似然估计量的问题就归结为微分学中的求最大值的问题了。估计量的评选标准为：（1）无偏性（2）有效性（3）相合性区间估计：对于一个未知量，人们在测量或计算时，常不以得到近似值为满足，还需要估计误差，即要求知道近似值的精确程度（亦即所求真值所在的范围）。这样的范围常以区间的形式给出，同时还给出此区间包含参数真值的可信度，这种形式的估计称为区间估计，这样的区间即所谓置信区间。正态总体均值、方差的置信区间与单侧置信限（置信水平为1-）一个正态总体未知参数其他参数枢轴量的分布置信区间2已知(0,1)/XZNn/2()XznFromclownstudio2未知(1)/XttnSn/2((1))SXznn2未知2222(1)(1)nSn2222/21/2(1)(1)(,)(1)(1)nSnSnn另外还包括两个正态总体的情况，其他区间估计：（0-1）分布参数的区间估计（3）插值1、含义的理解在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点。插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值（与拟合的不同点在于拟合的函数不需通过每一个离散点）。插值问题的提法是：假定区间[a，b］上的实值函数f（x）在该区间上n＋1个互不相同点x0，x1…xn处的值是f[x0］，…f（xn），要求估算f（x）在[a，b］中某点的值。其做法是：在事先选定的一个由简单函数构成的有n＋1个参数C0，C1，…Cn的函数类Φ(C0，C1，…Cn)中求出满足条件P（xi）＝f（xi）（i＝0，1，…n）的函数P(x)，并以P()作为f()的估值。此处f（x）称为被插值函数，x0，x1，…xn称为插值结(节)点，Φ(C0，C1，…Cn)称为插值函数类，上面等式称为插值条件，Φ（C0，…Cn）中满足上式的函数称为插值函数，R（x）＝f（x）－P（x）称为插值余项。当估算点属于包含x0，x1…xn的最小闭区间时，相应的插值称为内插，否则称为外插。2、基本类型多项式插值在一般插值问题中，若选取Φ为n次多项式类，由插值条件可以唯一确定一个n次插值多项式满足上述条件。拉格朗日插值和牛顿插值都属于多项式插值。拉格朗日插值：设连续函数y=f（x）在[a,b]上对给定n+1个不同结点：01,,,nxxx分别取函数值01,,,nyyy其中()iiyfx0,1,,in（1）试构造一个次数不超过n的插值多项式2012()nnnPxaaxaxax（2）使之满足条件()niiPxy0,1,2,,in（3）构造n次多项式()klx0,1,,kn使()klx=1,k=i0,ki（4）Fromclownstudio由1()()nnikkiikPxylxy0,1,2,,in(5)即()nPx满足插值条件，于是问题归结为具体求出基本插值多项式()klx。根据（4）式()klx以外所有的节点都是()klx的根，因此令0111()()()()()()kkknlxxxxxxxxxxx0()njjjkxx又由()klx=1，得：01111()()()()()kkkkkkknxxxxxxxxxx所以有01110111()()()()()()()()()()()kknkkkkkkkknxxxxxxxxxxlxxxxxxxxxxx0njjkjjkxxxx代入（5）得拉格朗日插值多项式为：000()()nnnjnkkkkkjkjjkxxPxlxyyxx牛顿插值：（拉格朗日插值的缺点）拉格朗日插值公式的形式虽然有一定的规律，但是当增加一个节点时，不仅要增加项数，而且以前各项也必须重新全部计算，不能利用已有的结果。为克服这一缺点，我们取用另一种形式――牛顿插值公式。牛顿插值公式中用到了差商。一般称：01112010[,,,][,,,][,,,]nnnnfxxxfxxxfxxxxx为()fx在01,,,nxxx处的n阶差商。差商可列表计算：xiyi一阶差商二阶差商三阶差商四阶差商x0f(x0)x1f(x1)f[x0,x1]x2f(x2)f[x1,x2]f[x0,x1,x2]x3f(x3)f[x2,x3]f[x1,x2,x3]f[x0,x1,x2,x3]Fromclownstudiox4f(x4)f[x3,x4]f[x2,x3,x4]f[x1,x2,x3,x4]f[x0,„,x4]由差商定义可知2001001201P()()[,]()[,,]()()xfxfxxxxfxxxxxxx由差商定义可求得000101012011010101()()()[,]()()[,,]()()()[,,,]()()()[,,,,]nnnnfxfxxxfxxxxxxfxxxxxxxxxfxxxxxxxxxfxxxx记00010101201101()()()[,]()()[,,]()()()[,,,]nnnNxfxxxfxxxxxxfxxxxxxxxxfxxx0101()()()()[,,,,]nnnRxxxxxxxfxxxx则()()()nnnfxNxRx其中()nNx称为n次牛顿插值多项式，()nRx是截断误差。最终我们可以证明()nNx满足插值条件()()niniNxfx0,1,2,,in因此有()()nnnnNxfx牛顿插值公式的优点是：当增加一个节点时，只要再增加一项就行了，即有递推式101011()()()()()[,,,,]kkkkkNxNxxxxxxxfxxxx当然，与拉格朗日插值相比它还有节省运算次数的优点（尤其是节省乘法运算次数）。分段插值与样条插值为了避免高次插值可能出现的大幅度波动现象，在实际应用中通常采用分段低次插值来提高近似程度埃尔米特插值许多实际插值问题中，为使插值函数能更好地和原来的函数重合，不但要求二者在节点上函数值相等，而且还要求相切，对应的导数值也相等，甚至要求高阶导数也相等。这类插值称作切触插值，或埃尔米特(Hermite)插值。满足这种要求的插值多项式就是埃尔米特插值多项式三角函数插值当被插函数是以2π为周期的函数时，通常用n阶三角多项式作为插值函数，并通过高斯三角插值表出。三、线性规划、整数规划、多元规划、二次规划（1）线性规划Fromclownstudio1、含义的理解线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。2、线性规划问题的数学模型的一般形式和模型建立（1）列出约束条件及目标函数（2）画出约束条件所表示的可行域（3）在可行域内求目标函数的最优解及最优值（实际问题中建立数学模型一般有以下三个步骤：根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的函数关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。）所建立的数学模型具有以下特点：（1）、每个模型都有若干个决策变量（x1,x2,x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。（2）、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。（3）、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。3、实例生产计划问题问题：某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A：4吨，原材料B：12吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多？产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35设x1为甲产品分配的设备台数，x2为乙产品分配的台数。则条件限制为：3*x1+2*x2181*x1+0*x240*x1+2*x212x10，x20求maxz=3*x1+5*x2Fromclownstudio用lingo编程，程序如下：max=3*x1+5*x2;3*x1+2*x2<=18;x1<=4;x2<=6;x1>=0;x2>=0;结果为：Globaloptimalsolutionfound.Objectivevalue:36.00000Totalsolveriterations:1VariableValueReducedCostX12.0000000.000000X26.0000000.000000RowSlackorSurplusDualPrice136.000001.00000020.0000001.00000032.0000000.00000040.0000003.00000052.0000000.00000066.0000000.000000即在x1=2，x2=6时，企业获利最多，为36万元。4、线性规划的应用在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果.广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。（2）整数规划一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。不同于线性规划问题，整数和0-1规划问题至今尚未找到一般的多项式解法。组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题,车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。Fromclownstudio整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。0-1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0-1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。（4）二次规划二次规划是非线形规划中一类特殊的数学规划问题，它的解是可以通过求解得到的。通常通过解其库恩—塔克条件（KT条件）,获取一个KT条件的解称为KT对，其中与原问题的变量对应的部分称为KT点。二次规划分为凸二次规划与非凸二次规划，前者的KT点便是其全局极小值点，而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数，则约束条件是线性的。由于求解二次规划的方法很多，所以较为复杂；其较简便易行的是沃尔夫法，它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。四、图论：（参考资料：建模教程(图与网络））（1）含义的理解图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运筹学有交叉。图论中常用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象、用点与点之间的线表示研究对象之间的特定关系。在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。因此，图论中的图与几何图，工程图等本质上是不同的。（2）历史（包括应用范围）它有200多年历史，大体可划分为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围游戏而产生，最有代表性的工作是所谓的Euler七桥问题，即一笔画问题。第二阶段是从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如Hamilton问题，地图染色的四色问题以及可平面性问题等，这时，也出现用图解决实际问题，如Cayley把树应用于化学领域，Kirchhoff用树去研究电网络等.第三阶段是二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以Ford和Fulkerson建立的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，促进了图论对实际问题的应用。算法重要的算法Fromclownstudio1、求有向图的强连通分支(StrongerstConnectedComponent)（1）Kosaraju算法（2）Gabow算法（3）Tarjan算法2、求最小生成树(MinimalSpanningTrees)（1）Kruskal算法(2)Prim算法3、最小树形图（1）朱永津刘振宏算法4、最短路径问题（1）SSSP(Single-sourceShortestPaths)①Dijkstra算法②Bellman-Ford算法(SPFA算法)（2）APSP(All-pairsShortestPaths)①Floyd-Warshall算法②Johnson算法5、网络流问题（1）最大网络流①增广路算法⒈Ford-Fulkerson算法⒉Edmonds-Karp算法⒊最短路径增殖EK-2（MPLA）⒋Dinic②预流推进算法（2）最小费用流6、图匹配问题（1）匈牙利算法（2）HopcroftKarp算法（3）Kuhn-Munkres算法（4）Edmonds'blossom-contraction算法（有关资料网址：http://www.nocow.cn/index.php/%E5%9B%BE%E8%AE%BA）（1）基本概念无向图一个无向图(undirectedgraph)G是由一个非空有限集合)(GV和)(GV中某些元素的无序对集合)(GE构成的二元组，记为))(),((GEGVG。其中},,,{)(21nvvvGV称为图G的顶点集（vertexset）或节点集（nodeset），)(GV中的每一个元素),,2,1(nivi称为该图的一个顶点（vertex）或节点（node）；},,,{)(21meeeGE称为图G的边集（edgeset），)(GE中的每一个元素ke(即)(GV中某两个元素jivv,的无序Fromclownstudio对)记为),(jikvve或ijjikvvvve),,2,1(mk，被称为该图的一条从iv到jv的边（edge）。当边jikvve时，称jivv,为边ke的端点，并称jv与iv相邻（adjacent）；边ke称为与顶点jivv,关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图G中相邻。边上赋权的无向图称为赋权无向图或无向网络（undirectednetwork）。我们对图和网络不作严格区分，因为任何图总是可以赋权的有向图一个有向图（directedgraph或digraph）G是由一个非空有限集合V和V中某些元素的有序对集合A构成的二元组，记为),(AVG。其中},,,{21nvvvV称为图G的顶点集或节点集，V中的每一个元素),,2,1(nivi称为该图的一个顶点或节点；},,,{21maaaA称为图G的弧集（arcset），A中的每一个元素ka(即V中某两个元素jivv,的有序对)记为),(jikvva或),,2,1(nkvvajik，被称为该图的一条从iv到jv的弧（arc）。当弧jikvva时，称iv为ka的尾（tail），jv为ka的头（head），并称弧ka为iv的出弧（outgoingarc），为jv的入弧（incomingarc）。对应于每个有向图D，可以在相同顶点集上作一个图G，使得对于D的每条弧，G有一条有相同端点的边与之相对应。这个图称为D的基础图。反之，给定任意图G，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为G的一个定向图。完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。n个顶点的完全图记为nK。若YXGV)(，YX，0||||YX（这里||X表示集合X中的元素个数），X中无相邻顶点对，Y中亦然，则称G为二分图(bipartitegraph)；特别地，若YyXx,，则)(GExy，则称G为完全二分图，记成|||,|YXK。最短路、网络流、二分图1、最短路问题（SPP－shortestpathproblem）最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等Fromclownstudio等。也可以用于解决其它的最优化问题。若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类单源最短路径问题包括起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全相同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。）确定起点终点的最短路径问题即已知起点和终点，求两点之间的最短路径。全局最短路径问题求图中所有的最短路径。算法只要采用Floyed-Warshall算法（这是弗洛伊德利用动态规划(dynamicprogramming)的原理设计的一个高效算法）。Floyed-Warshall算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。不可思议的是，只要按排适当，就能得到结果。最短路算法：Dijkstra算法Dijkstra复杂度是O(N^2)，如果用binaryheap优化可以达到O((E+N)logN)，用fibonacciheap可以优化到O(NlogN+E)其基本思想是采用贪心法，对于每个节点v[i]，维护估计最短路长度最大值，每次取出一个使得该估计值最小的t，并采用与t相连的边对其余点的估计值进行更新，更新后不再考虑t。在此过程中，估计值单调递减，所以可以得到确切的最短路。Dijkstra程序：voidDijkstra(){for(inti=1;i<=n;i++)dis[i]=map[1][i];intk;for(inti=1;i<n;i++){inttmin=maxint;Fromclownstudiofor(intj=1;j<=n;j++)if(!used[j]&&tmin>dis[j]){tmin=dis[j];k=j;}used[k]=1;for(intj=1;j<=n;j++)if(dis[k]+map[k][j]<dis[j])dis[j]=dis[k]+map[k][j];}printf("%d",dis[n]);}/*求1到N的最短路,dis[i]表示第i个点到第一个点的最短路ByPing*/还有其他算法：Floyd-Warshall算法Bellman-Ford算法Johnson算法实例：某公司在六个城市621,,,ccc中有分公司，从ic到jc的直接航程票价记在下述矩阵的),(ji位置上。（表示无直接航路），请帮助该公司设计一张城市1c到其它城市间的票价最便宜的路线图。055252510550102025251001020402010015252015050102540500用矩阵nna（n为顶点个数）存放各边权的邻接矩阵，行向量pb、1index、2index、d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量顶点未标号当第顶点已标号当第iiipb01)(；)(2iindex存放始点到第i点最短通路中第i顶点前一顶点的序号；)(id存放由始点到第i点最短通路的值。求第一个城市到其它城市的最短路径的Matlab程序如下：clear;Fromclownstudioclc;M=10000;a(1,:)=[0,50,M,40,25,10];a(2,:)=[zeros(1,2),15,20,M,25];a(3,:)=[zeros(1,3),10,20,M];a(4,:)=[zeros(1,4),10,25];a(5,:)=[zeros(1,5),55];a(6,:)=zeros(1,6);a=a+a';pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;whilesum(pb)<length(a)tb=find(pb==0);d(tb)=min(d(tb),d(temp)+a(temp,tb));tmpb=find(d(tb)==min(d(tb)));temp=tb(tmpb(1));pb(temp)=1;index1=[index1,temp];index=index1(find(d(index1)==d(temp)-a(temp,index1)));iflength(index)>=2index=index(1);endindex2(temp)=index;endd,index1,index2运行结果为：d=03545352510index1=165243index2=165611即：d（最短通路的值）03545352510index1（标号顶点顺序）165243index2（标号顶点索引）1656112、网络流（1）含义的理解网络流（networkflows）是图论中的一种理论与方法，研究网络上的一类最优化问题。（2）历史及应用1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图D＝（V、E、C），Fromclownstudio其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。（3）算法的实现Edmonds-Karp算法建立在Ford-Fulkerson方法上的增广路算法,与一般的Ford-Fulkerson算法不同的是,它用广度搜索实现对增广路的寻找.以下为代码:intn;longintc[128][128];longmaxflow(ints,intt){intp,q,queue[128],u,v,pre[128];longintflow,aug;flow=0;while(true){memset(pre,-1,sizeof(pre));for(queue[p=q=0]=s;p<=q;p++){u=queue[p];for(v=0;(v<n)&&(pre[t])<0;v++){if((c[u][v]>0)&&(pre[v]<0)){pre[v]=u;queue[++q]=v;}}Fromclownstudioif(pre[t]>=0){break;}}if(pre[t]<0){break;}aug=0x7fff;for(u=pre[v=t];v!=s;(v=u),(u=pre[u])){if(c[u][v]<aug){aug=c[u][v];}}for(u=pre[v=t];v!=s;(v=u),(u=pre[u])){c[u][v]-=aug;c[v][u]+=aug;}flow+=aug;}returnflow;}3、二分图（1）含义的理解二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(iinA,jinB)，则称图G为一个二分图。2、相关应用作为一种数学模型，二分用途是十分有用的，许多问题可以用它来刻划。例如“资源匹配”、“工作安排”、“人员择偶”等等。而这就需要考虑匹配问题。匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。而二分图最大匹配可以用最大流或者匈牙利算法。最大流在网络流中有介绍。匈牙利算法为：（资料：百度百科）匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于HallFromclownstudio定理（此定理使用于组合问题中。二部图G中的两部分顶点组成的集合分别为X,Y,Z,={X1,X2,X3,X4,.........,Xm},Y={y1,y2,y3,y4,.........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)）中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。算法的思路：不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.资料来源：http://www.nocow.cn/index.php/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配）由增广路的定义可以推出下述三个结论：1.P的路径长度必定为奇数，第一条边和最后一条边都不属于M。2.P经过取反操作可以得到一个更大的匹配M’。3.M为G的最大匹配当且仅当不存在相对于M的增广路径。用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)算法轮廓：1.置M为空2.找出一条增广路径P，通过取反操作获得更大的匹配M’代替M3.重复(2)操作直到找不出增广路径为止程序清单：constmaxm=200;maxn=200;vari,j,k,m,n:longint;g:array[1..maxm,1..maxn]ofboolean;Fromclownstudioy:array[1..maxn]ofboolean;lk:array[1..maxn]oflongint;functionfind(x:longint):boolean;vari:longint;beginfori:=1tondoifg[x,i]and(noty[i])thenbeginy[i]:=true;if(lk[i]=0)orfind(lk[i])thenbeginlk[i]:=x;find:=true;exit;end;end;find:=false;end;#include<stdio.h>#include<string.h>boolg[201][201];intn,m,ans;boolb[201];intlink[201];boolinit(){int_x,_y;memset(g,0,sizeof(g));memset(link,0,sizeof(link));ans=0;if(scanf("%d%d",&n,&m)==EOF)returnfalse;for(inti=1;i<=n;i++){scanf("%d",&_x);for(intj=0;j<_x;j++){scanf("%d",&_y);g[i][_y]=true;}}returntrue;Fromclownstudio}boolfind(inta){for(inti=1;i<=m;i++){if(g[a][i]==1&&!b[i]){b[i]=true;if(link[i]==0||find(link[i])){link[i]=a;returntrue;}}}returnfalse;}intmain(){while(init()){for(inti=1;i<=n;i++){memset(b,0,sizeof(b));if(find(i))ans++;}printf("%d\n",ans);}}每次增广时间为O(E),最多进行O(V)次迭代,时间复杂度为O(VE).五、动态规划、回溯搜索、分治算法、分支定界等计算机算法一、动态规划（http://www.nocow.cn/index.php/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92）1、含义的理解动态规划（dynamicprogramming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优性原理（principleofoptimality），把多阶段过程转化为一Fromclownstudio系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《DynamicProgramming》，这是该领域的第一本著作。2、动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型3、应用范围动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。4、动态规划的基本原理多阶段决策过程最优化：多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题5、基本概念、基本方程和计算方法（见资料《建模教程—动态规划》）6、动态规划优缺点：动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。DP方程中附加某些约束条件，可使求解更加容易。求得最优解以后，可得所有子问题的最优解。动态规划的缺点：“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。状态变量维数不能太高，一般要求小于67、实例机器可以在高、低两种负荷下生产。u台机器在高负荷下的年产量是)(ug，在低负荷下的年产量是)(uh，高、低负荷下机器的年损耗率分别是1a和1b（1011ab）。现有m台机器，要安排一个n年的负荷分配计划，即每年初决定多少台机器投入高、低负荷运行，使n年的总产量最大。如果进一步假设uug)(，uuh)(（0），即高、低负荷下每台机器的年产量分别为和，结果将有什么特点。解年度为阶段变量nk,,2,1。状态kx为第k年初完好的机器数，决策ku为第kFromclownstudio年投入高负荷运行的台数。当kx或ku不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。机器在高、低负荷下的年完好率分别记为a和b，则11aa，11bb，有ba。因为第k年投入低负荷运行的机器台数为kkux，所以状态转移方程是)(1kkkkuxbaux（1）阶段指标kv是第k年的产量，有)()(),(kkkkkkuxhuguxv（2）指标函数是阶段指标之和，最优值函数)(kkxf满足.1,2,,,0)],(),([max)(110nkmxxfuxvxfkkkkkkxukkkk(3)及自由终端条件.0,0)(111mxxfnnn（4）当kv