下载文档原格式
最大流常见算法最大流问题是图论中的一个重要问题，其求解方法有多种，本文将介绍最常见的几种算法。
一、最大流问题简介最大流问题是在一个网络中寻找从源点到汇点的最大流量的问题。
网络是由一些节点和连接这些节点的边构成的，每条边都有一个容量，表示该边所能承载的最大流量。
源点是流量的起点，汇点是流量的终点。
在网络中，还可能存在其他节点和边。
二、Ford-Fulkerson算法Ford-Fulkerson算法是最早用于解决最大流问题的算法之一。
该算法基于增广路径来不断增加流量，直到无法再找到增广路径为止。
1. 算法步骤（1）初始化：将所有边上的流量设为0。
（2）寻找增广路径：从源点开始进行深度优先或广度优先搜索，在搜索过程中只选择剩余容量不为0且没有被标记过的边，并记录路径上容量最小值min。
（3）更新路径上各个边上的流量：将路径上各个边上的流量加上min。
（4）返回第二步，直到无法找到增广路径为止。
2. 算法分析Ford-Fulkerson算法可以保证在有限步内求解出最大流，但是其时间复杂度与增广路径的选择有关，最坏情况下可能需要指数级的时间复杂度。
三、Edmonds-Karp算法Edmonds-Karp算法是基于Ford-Fulkerson算法的一种改进算法。
该算法使用BFS来寻找增广路径，可以保证在多项式时间内求解出最大流。
1. 算法步骤（1）初始化：将所有边上的流量设为0。
（2）寻找增广路径：从源点开始进行BFS，在搜索过程中只选择剩余容量不为0且没有被标记过的边，并记录路径上容量最小值min。
（3）更新路径上各个边上的流量：将路径上各个边上的流量加上min。
（4）返回第二步，直到无法找到增广路径为止。
2. 算法分析Edmonds-Karp算法相对于Ford-Fulkerson算法来说，在同样的网络中，其时间复杂度更低，可以保证在O(VE^2)的时间内求解出最大流。
但是在某些特殊情况下仍然可能需要指数级时间复杂度。
noi算法范围NOI算法范围NOI（National Olympiad in Informatics，全国信息学奥林匹克竞赛）是中国的一项高中生计算机科学竞赛，旨在培养和选拔优秀的计算机科学与技术人才。
NOI算法范围是指在NOI竞赛中所涵盖的算法知识内容。
一、线性结构算法1. 数组：在NOI竞赛中，数组的使用非常广泛。
掌握数组的基本操作，如遍历、查找、插入、删除等，对于解决很多算法问题至关重要。
2. 链表：了解链表的基本概念和操作，如插入、删除、反转等。
链表的灵活性和动态性使得它在某些问题的解决中具有很大优势。
3. 栈和队列：掌握栈和队列的基本操作，如入栈、出栈、入队、出队等。
栈和队列在解决一些特定问题时非常有用，如括号匹配、迷宫问题等。
二、排序和查找算法1. 冒泡排序：掌握冒泡排序的思想和实现方法，了解其时间复杂度和空间复杂度。
2. 快速排序：了解快速排序的思想和实现方法，掌握其时间复杂度和空间复杂度。
快速排序在解决大规模数据排序问题时效率高。
3. 二分查找：掌握二分查找的思想和实现方法，了解其时间复杂度。
二分查找适用于有序数组中的查找问题。
三、图论算法1. 最短路径算法：了解Dijkstra算法和Floyd算法，掌握它们的思想和具体实现方法。
最短路径算法在解决网络中的最短路径问题时非常重要。
2. 最小生成树算法：掌握Prim算法和Kruskal算法，了解它们的思想和实现方法。
最小生成树算法在解决网络中的连通问题时具有很大的应用价值。
四、动态规划算法1. 背包问题：了解0-1背包问题和完全背包问题，掌握它们的动态规划解法。
背包问题在资源分配和优化问题中有广泛的应用。
2. 最长公共子序列：了解最长公共子序列问题的动态规划解法，掌握其实现方法。
最长公共子序列问题在字符串匹配和相似性分析中有很大的作用。
五、搜索算法1. 深度优先搜索（DFS）：了解DFS的基本原理和实现方式，掌握其递归和非递归的实现方法。
数学建模常用方法建模常用算法,仅供参考：1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具）3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通常使用L i n d o、L i n g o软件实现）4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备）5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用）7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种暴力方案,最好使用一些高级语言作为编程工具）8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理）一、在数学建模中常用的方法：1.类比法2.二分法3.量纲分析法4.差分法5.变分法6.图论法7.层次分析法8.数据拟合法9.回归分析法10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划）11.机理分析12.排队方法13.对策方法14.决策方法15.模糊评判方法、16.时间序列方法17.灰色理论方法18.现代优化算法（禁忌搜索算法、模拟退火算法、遗传算法、神经网络)二、用这些方法可以解下列一些模型：优化模型、微分方程模型、统计模型、概率模型、图论模型、决策模型。
ISAP 是图论求最大流的算法之一，它很好的平衡了运行时间和程序复杂度之间的关系，因此非常常用。
约定我们使用邻接表来表示图，表示方法可以见文章带权最短路 Dijkstra, SPFA, Bellman-Ford, ASP, Floyd-Warshall 算法分析或二分图的最大匹配、完美匹配和匈牙利算法的开头（就不重复贴代码了）。
在下文中，图的源点（source）表示为s，汇点（sink）表示为t，当前节点为u。
建图时，需要建立双向边（设反向的边容量为0）才能保证算法正确。
引入求解最大流问题的一个比较容易想到的方法就是，每次在残量网络（residual network）中任意寻找一条从s到t的路径，然后增广，直到不存在这样的路径为止。
这就是一般增广路算法（labeling algorithm）。
可以证明这种不加改进的贪婪算法是正确的。
假设最大流是f，那么它的运行时间为O( f⋅∣E∣)。
但是，这个运行时间并不好，因为它和最大流f有关。
人们发现，如果每次都沿着残量网络中的最短增广路增广，则运行时间可以减为O(∣E∣2⋅∣V∣) 。
这就是最短增广路算法。
而 ISAP 算法则是最短增广路算法的一个改进。
其实，ISAP 的意思正是「改进的最短增广路」 (Improved Shortest Augmenting Path)。
顺便说一句，上面讨论的所有算法根本上都属于增广路方法（Ford-Fulkerson method）。
和它对应的就是大名鼎鼎的预流推进方法（Preflow-push method）。
其中最高标号预流推进算法（Highest-label preflow-pushalgorithm）的复杂度可以达到O(∣V∣2∣E∣−−−√)。
虽然在复杂度上比增广路方法进步很多，但是预流推进算法复杂度的上界是比较紧的，因此有时差距并不会很大。
算法解释概括地说，ISAP 算法就是不停地找最短增广路，找到之后增广；如果遇到死路就 retreat，直到发现s, t不连通，算法结束。
程序设计竞赛常用算法1.排序算法：排序是一个基本的算法问题，常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。
这些排序算法有各自的优势和适用场景，需要根据具体问题需求选择合适的算法。
2.图论算法：图论是程序设计竞赛中经常出现的重要领域。
常见的图论算法有深度优先（DFS）、广度优先（BFS）、Dijkstra算法、Floyd-Warshall算法、拓扑排序、最小生成树等。
这些算法可以用于解决最短路径、连通性、最大流最小割等问题。
3.动态规划：动态规划是一种常用于解决优化问题的算法。
该算法通过将问题分解成子问题，并记录子问题的解来求解原问题的最优解。
常见的动态规划算法有背包问题、最长公共子序列（LCS）、最大子序列和等。
4.字符串处理算法：字符串处理是程序设计竞赛中常见的问题。
常见的字符串处理算法有KMP算法、哈希算法、字符串匹配等。
这些算法可以用于解决模式匹配、字符串、字符统计等问题。
5.数学算法：数学算法在程序设计竞赛中也经常被使用。
常见的数学算法有质因数分解、素数筛、快速乘法、高精度计算等。
这些算法可以用于解决数论、计算几何、概率等问题。
6.图形算法：图形算法主要用于处理图像和几何图形。
常见的图形算法有扫描线算法、凸包算法、几何运算等。
这些算法可以用于解决图像处理、三维建模等问题。
7.树和图的遍历算法：树和图的遍历算法是程序设计竞赛中常用的算法之一、常见的树和图的遍历算法有先序遍历、中序遍历、后序遍历、深度优先（DFS）、广度优先（BFS）等。
这些算法可以用于解决树和图的构建、路径等问题。
8.最大匹配和最小割算法：最大匹配算法用于求解二分图的最大匹配问题，常见的算法有匈牙利算法。
最小割算法用于求解图的最小割问题，常见的算法有Ford-Fulkerson算法。
这些算法可以用于解决网络流和二分图匹配等问题。
9.贪心算法：贪心算法是一种常用于优化问题的算法。
该算法通过每一步选择局部最优解来达到全局最优解。
图论在网络优化中的应用一、概述图论是数学中的一个研究领域，主要研究的对象是图。
图是由顶点和边组成的，常用来描述事物之间的关系。
在网络优化中，图论可以帮助我们分析网络结构、优化网络流量以及解决其他相关问题。
二、最短路径算法在网络中，我们经常需要找到两个节点之间最短的路径。
这时，最短路径算法可以派上用场。
最短路径算法包括迪杰斯特拉算法和弗洛伊德算法等，它们都是基于图论的算法。
通过这些算法，我们可以高效地找到网络中节点之间的最短路径，从而优化网络通信效率。
三、最大流问题在网络中，我们需要考虑流量的问题。
最大流问题是指在网络中的一个节点到另一个节点之间的最大流量。
图论中的最大流算法可以帮助我们解决这个问题。
通过寻找网络中的最大流，我们可以优化网络资源的利用，提高网络的吞吐量。
四、最小生成树最小生成树是一个连通图中生成树的总权值最小的生成树。
在网络优化中，最小生成树可以用于构建最优的网络拓扑结构。
通过图论中相关的算法，我们可以找到网络中的最小生成树，并且实现对网络的优化。
五、网络分析除了上述提到的算法之外，图论在网络优化中还有许多其他的应用。
例如，通过网络分析，我们可以了解网络结构的特点，找到网络中的关键节点，优化网络连接方式等。
这些都可以帮助我们改进网络的性能和效率。
六、总结综上所述，图论在网络优化中具有重要的应用价值。
通过图论算法，我们可以解决网络中的各种问题，优化网络的性能，提高网络的效率。
图论的应用不仅局限于网络领域，还可以在其他领域发挥重要作用。
希望未来可以进一步深入研究图论的应用，为网络优化和其他相关领域的发展做出更大的贡献。
算法的分类算法是计算机科学中的重要概念，是指在一系列规则或指示下，通过一定的计算方式，解决特定的问题或完成特定的任务。
算法的分类可以根据不同的特征进行划分，下面将就这个话题进行详细探讨。
一、按照算法的基本操作方式分类1.递推算法递推算法是指根据已知的数据推算出未知数据的方法，其计算比较简单，容易理解。
常见的递推算法有斐波那契数列、汉诺塔问题等。
2.分治算法分治算法是把大问题不断分解成小问题，直到小问题可以简单的解决，然后逐步合并解决小问题的解法，得到原大问题的计算结果。
常见的分治算法有快速排序、归并排序等。
3.回归算法回归算法是通过分析已有数据的相关性，预测未来结果的算法。
主要用于统计分析和经济学领域。
枚举算法是指把所有的可能性都列出来，一一列举分析，得出结果的算法。
常见的枚举算法有全排列问题、最短路径问题等。
5.贪心算法贪心算法是通过对每一个问题选择当前最好的解决方法，在所有结果中找到最优解的算法。
常见的贪心算法有背包问题、最小生成树问题等。
6.动态规划算法动态规划算法是通过把大问题分解成一系列子问题，依次求解每个子问题的最优解，从而得出整个问题的最优解的算法。
常见的动态规划算法有最长公共子序列问题、最长上升子序列问题等。
二、按照算法的应用场景分类1.排序算法排序算法是指将一定序列的元素按照指定的大小关系进行排序的算法。
常见的排序算法有冒泡排序、选择排序、快速排序、堆排序等。
图论算法是指对图的相关概念及其表示方法进行研究的算法。
常见的图论算法有最短路径算法、最小生成树算法、最大流算法等。
3.字符串算法字符串算法是指对字符串相关概念及其处理方式进行研究的算法。
常见的字符串算法有字符串匹配算法、子串查找算法等。
4.数值计算算法数值计算算法是指对数值计算问题进行研究的算法。
常见的数值计算算法有数值积分算法、线性方程组求解算法、常微分方程数值解法等。
5.人工智能算法人工智能算法是指通过对人类智能的模拟，实现特定任务的算法。
数学建模中常见的十大模型集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#数学建模常用的十大算法==转(2011-07-24 16:13:14)1. 蒙特卡罗算法。
该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。
2. 数据拟合、参数估计、插值等数据处理算法。
比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。
3. 线性规划、整数规划、多元规划、二次规划等规划类算法。
建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。
4. 图论算法。
这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。
5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。
这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。
6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。
这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。
7. 网格算法和穷举法。
两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8. 一些连续数据离散化方法。
很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。
9. 数值分析算法。
如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。
10. 图象处理算法。
赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。
、此数学建模十大算法依据网上的一份榜单而写，本文对此十大算法作一一简单介绍。
这只是一份榜单而已，数学建模中还有很多的算法，未一一囊括。
欢迎读者提供更多的好的算法。
2、在具体阐述每一算法的应用时，除了列出常见的应用之外，同时，还会具体结合数学建模竞赛一一阐述。
毕竟，此十大算法，在数学建模竞赛中有着无比广泛而重要的应用。
且，凡是标着“某某年某国某题”，即是那一年某个国家的数学建模竞赛原题。
3、此十大算法，在一些经典的算法设计书籍上，无过多阐述。
若要具体细致的深入研究，还得请参考国内或国际上关于此十大算法的优秀论文。
谢谢。
一、蒙特卡罗算法1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam和Nick Metropolis共同发明了，蒙特卡罗方法。
此算法被评为20世纪最伟大的十大算法之一，详情，请参见我的博文：/v_JULY_v/archive/2011/01/10/6127953.aspx蒙特卡罗方法（Monte Carlo method），又称随机抽样或统计模拟方法，是一种以概率统计理论为指导的一类非常重要的数值计算方法。
此方法使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。
由于传统的经验方法由于不能逼近真实的物理过程，很难得到满意的结果，而蒙特卡罗方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可以得到很圆满的结果。
蒙特卡罗方法的基本原理及思想如下：当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。
有一个例子可以使你比较直观地了解蒙特卡洛方法：假设我们要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比如，积分）的复杂程度是成正比的。
蒙特卡洛方法是怎么计算的呢？假想你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。
最大流算法clc,clear,M=1000;c(1,2)=3;c(1,4)=3;c(2,3)=1;c(2,4)=20;c(3,6)=3;c(4,5)=10;c(5,1)=4;c(5,3)=2;c(5,6)=13;n=length(u);list=[];maxf=zeros(1:n);maxf(n)=1;while maxf(n)>0maxf=zeros(1,n);pred=zeros(1,n);list=1;record=list;maxf(1)=M;while (~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];index1=(find(u(flag,:)~=0));label1=index1(find(u(flag,index1)...-f(flag,index1)~=0));label1=setdiff(label1,record);list=union(list,label1);pred(label1(find(pred(label1)==0)))=flag;maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));record=union(record,label1);label2=find(f(:,flag)~=0);label2=label2';label2=setdiff(label2,record);list=union(list,label2);pred(label2(find(pred(label2)==0)))=-flag;maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2);endif maxf(n)>0v2=n;v1=pred(v2);while v2~=1if v1>0f(v1,v2)=f(v1,v2)+maxf(n);elsev1=abs(v1);f(v2,v1)=f(v2,v1)-maxf(n);endv2=v1;v1=pred(v2);endendendffunction [f,wf,No]=MaxFlowMinCut_Me(n,C)% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码% f %显示最大流% wf %显示最大流量% No %显示标号, 由此可得最小割% n 节点个数% C %弧容量最大流算法for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流f 为零流for(i=1:n)No(i)=0;d(i)=0;end%No,d 记录标号while(1)No(1)=n+1;d(1)=Inf; %给发点vs 标号while(1)pd=1; %标号过程for(i=1:n)if(No(i)) %选择一个已标号的点vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj 为饱和弧时No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;if(d(j)>d(i))d(j)=d(i);endelseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)>d(i))d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号,终止标号过程if(pd)break;end%vt 未得到标号, f 已是最大流, 算法终止dvt=d(n);t=n; %进入调整过程, dvt 表示调整量while(1)if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end%当t 的标号为vs 时, 终止调整过程t=No(t);end;end; %继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);endendn=6;C=[0 3 0 3 0 00 0 1 20 0 00 0 0 0 0 30 0 0 0 10 00 4 2 0 0 130 0 0 0 0 0];[f,wf,No]=MaxFlowMinCut_Me(n,C)最大匹配算法A=[1 1 0 1 00 1 1 1 01 0 1 0 10 1 1 0 00 0 0 1 1];A=[1 0 0 1 00 1 1 1 00 0 0 1 11 1 0 0 10 0 1 0 1];A=[1 1 0 1 00 1 1 1 01 0 1 0 10 1 1 0 00 0 0 1 1];A=[1 0 0 1 00 1 1 1 00 0 0 1 11 1 0 0 10 0 1 0 1];A=[1 0 0 1 00 1 0 1 00 1 0 0 11 1 1 0 00 0 1 1 1];m=5;n=5;M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end %求初始匹配Mif(M(i,j))break;end;end %获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end %将记录X中点的标号和标记*for(i=1:n)y(i)=0;end %将记录Y中点的标号和标记*for(i=1:m)pd=1; %寻找X中M的所有非饱和点for(j=1:n)if(M(i,j))pd=0;end;endif(pd)x(i)=-n-1;end;end %将X中M的所有非饱和点都给以标号0 和标记*,程序中用n+1 表示0 标号, 标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)<0)xi=i;break;end;end %假如X 中存在一个既有标号又有标记*的点, 则任取X中一个既有标号又有标记*的点xiif(xi==0)pd=1;break;end %假如X中所有有标号的点都已去掉了标记*,算法终止x(xi)=x(xi)*(-1); %去掉xi 的标记*k=1;for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end %对与xi 邻接且尚未给标号的yj 都给以标号iif(k>1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end %将yj 在M中与之邻接的点xk (即xkyj∈M), 给以标号j 和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j); %yj 不是M的饱和点while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j))); %任取M的一个非饱和点yj,逆向返回if(j==n+1)break;end %找到X中标号为0 的点时结束, 获得M-增广路Pk=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0; %将匹配M 在增广路P 中出现的边去掉else M(P(i,1),P(i,2))=1;end;end %将增广路P 中没有在匹配M中出现的边加入到匹配M中break;end;end;endif(pd)break;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止M %显示最大匹配M, 程序结束利用可行点标记求最佳匹配算法的 MATLAB 程序代码如下：n=5;A=[3 5 5 4 12 2 0 2 22 4 4 1 00 1 1 0 01 2 1 3 3];for(i=1:n)L(i,1)=0;L(i,2)=0;endfor(i=1:n)for(j=1:n)if(L(i,1)<A(i,j))L(i,1)=A(i,j);end; %初始可行点标记L M(i,j)=0;end;endfor(i=1:n)for(j=1:n) %生成子图Glif(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;end;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;endif(ii)break;end;end %获得仅含Gl 的一条边的初始匹配MM(ii,jj)=1;for(i=1:n)S(i)=0;T(i)=0;NlS(i)=0;endwhile(1)for(i=1:n)k=1;否则.for(j=1:n)if(M(i,j))k=0;break;end;endif(k)break;end;endif(k==0)break;end %获得最佳匹配M, 算法终止S(1)=i;jss=1;jst=0; %S={xi}, T=φwhile(1)jsn=0;for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j; %NL(S)={v|u∈S,uv∈EL}for(k=1:jsn-1)if(NlS(k)==j)jsn=jsn-1;end;end;end;end;endif(jsn==jst)pd=1; %判断NL(S)=T?for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;endif(jsn==jst&pd)al=Inf;%如果NL(S)=T, 计算al, Inf 为∞for(i=1:jss)for(j=1:n)pd=1;for(k=1:jst)if(T(k)==j)pd=0;break;end;endif(pd&al>L(S(i),1)+L(j,2)-A(S(i),j))al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;endfor(i=1:jss)L(S(i),1)=L(S(i),1)-al;end %调整可行点标记for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end %调整可行点标记for(i=1:n)for(j=1:n) %生成子图GLif(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;else Gl(i,j)=0;endM(i,j)=0;k=0;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;endif(ii)break;end;end %获得仅含Gl 的一条边的初始匹配MM(ii,jj)=1;breakelse %NL(S)≠Tfor(j=1:jsn)pd=1; %取y∈NL(S)\Tfor(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;endif(pd)jj=j;break;end;endpd=0; %判断y 是否为M的饱和点for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;endif(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj); %S=S∪{x}, T=T∪{y}else %获得Gl 的一条M-增广路, 调整匹配Mfor(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;endif(jst==0)k=0;endM(S(k+1),NlS(jj))=1;break;end;end;end;endMaxZjpp=0;for(i=1:n)for(j=1:n)if(M(i,j))MaxZjpp=MaxZjpp+A(i,j);end;end;end M %显示最佳匹配MMaxZjpp %显示最佳匹配M的权, 程序结束。
