更新时间：2022-08-25 18:38
匹配，一般指配合或搭配，也指结婚。“匹配”一词在不同的领域有着不同的意思，它既是数学语言，又是计算机方面的术语，其含义复杂多变。最优匹配是指基于利用匹配算法或一些规则找到最佳匹配结果，一般多用于模式识别、图像处理等领域。此外，Windows 日记本中“查找”功能的一个扩展选项，其中可包括多个匹配项。
推导过程设L是完备的二部赋权图G=(X,Y,E,F)的可行点标记，若M*是 的完美匹配，则M*是G的权数最大的匹配。称为最优（或最佳）匹配。
1、令M是图G的边子集，若M中任意两条边都没有共同的结点，则称M是G的一个匹配；其中与M的边关联的结点称为饱和点，否则成为非饱和点。
2、设M是G=（V，E）的一个匹配，若对G的任意匹配M'都有|M|>=|M'|，则称M是G的一个最大匹配。
3、给定了G的一个匹配M，G中属于M与不属于M的边交替出现的道路称为交互道路。
4、设P是G中关于匹配M的一条交互道路，若P的两个端点是关于M的非饱和点，则它就称为可增广道路。
5、M是G的最大匹配当且仅当G中不存在关于M的可增广道路。
6、设r是二分图G的最大匹配数，s是其邻接矩阵的最小覆盖数，则有r==s。
实际意义
指派问题：需要完成n1项任务，有n2个人可以承担这些任务。由于每个人的专长不同，完成不同任务的成本与效率也不同。应如何分配任务才能使得总成本最小或者总效益最大。
算法及步骤
使用匈牙利算法求解最佳匹配问题，基于最小成本的问题求解。
时间复杂度O(m×n)。
step1：使效益矩阵经过变换，在各行各列中都出现0元素
（1）效益矩阵每行的元素减去该行的最小元素；
（2）再将所得的效益矩阵每列的元素减去该列的最小元素。
step2：进行指派，寻求最优解
（1）从只有一个0元素的行（列）开始，给这个0元素加圈，这表示对这行所代表 的人而言，只有一种任务可以指派。然后划去该加圈0元素所在列（行）的其他0元素，表示该列所代表的任务已经指派完，无需考虑其他人。
（2）给只有一个0元素的列（行）的0元素加圈，同时划去该0元素所在行（列）的其他0元素。
（3）重复进行（1）、（2）两步，直至所有0元素都被加圈或划去为止。
（4）若仍存在未加圈未划去的0元素，且同行（列）的0元素至少有两个（表示对这个可以从两项任务中指派其一），则对同行同列中其他0元素总数最少的0元素加圈（表示选择性多的要礼让选择性少的），并划去同行同列中的其他0元素。可反复进行，直至所有0元素都被加圈或划去为止。
（5）若加圈的0元素数量m等于矩阵的阶数n（这里矩阵的阶数指成本/效益矩阵行数、列数中的较小值），则指派问题已经得到最优解；若m step3：作最少的直线覆盖所有的0元素，以确定成本/效益矩阵中的独立0元素 （1）对没有加圈0元素的行打勾； （2）对已打勾的行中被划去0元素所在列打勾； （3）对打勾的列中的加圈0元素所在行打勾； （4）重复（2）、（3）直至找不出新的可打勾的行、列为止； （5）选取未打勾的行和已打勾的列，即可覆盖全部0元素。 （6）选取的行、列数之和（即所作直线数）为l。若l step2的(4)，另行试探。 step4：增加独立的0元素 在未被直线覆盖的部分中找出最小元素。在打勾的行的各元素减去该最小元素，在打勾的列的各元素加上该最小元素，以保证原来的0元素不变。删除所有打勾、加圈、划去记号，返回step2。