关键词串匹配，前缀函数，KMP算法
在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3…sn，模式串表示为T=t1t2…tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。
1KMP算法
最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一般情况下为O((n-m+1)m)（注：n和m分别为主串和模式串的长度），最坏的情况下为O(m*n)，最好的情况下为O(m+n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为O(m+n)。
那么如何确定哪些是多余的比较？在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进行，无须回溯。假设主串为s1s2，sn.，模式串为t1t2，tm.，其中m≦n，从si+1开始的子串遇到一个不完全的匹配，使得：
(1.1)
如果我们能确定一个最小的整数，使得：
(1.2)
其中，所以确定i''''等价于确定k，这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关，只与给定的模式串t中与主串匹配的q有关，即k=f(q)，
f(q)=max{i|0iq且t[1..i]是t[1..q]的后缀}(1.3)
确定KMP前缀函数的算法如下：
#defineMAXSIZE100
Typedefunsignedcharstring[MAXSIZE+1];//0号单元用来存放串的长度
voidf(sstringt,int*array)
{
m=t[0];//m为当前模式串的长度
array=(int*)malloc((m+1)*sizeof(int));//0号元不用
array[1]=0;k=0;
for(q=2;q<=m;q++)
{while(k>0&&t[k+1]!=t[q])k=array[k];
if(t[k+1]==t[q])k=k+1;
array[q]=k;
}
}
关于KMP算法的前缀函数f(x)的示例见表1。
当模式串中有i个字符串匹配成功，第i+1个字符不匹配时，则从i-f(i)个字符重新开始比较，这样不仅无须回溯，而且一次可以向前滑动i-f(i)个字符，大大提高了模式匹配的效率。下面给出朴素匹配算法和KMP匹配算法的比较，见表2。
表2朴素匹配算法和KMP匹配算法比较表
朴素算法KMP算法
时间复杂度O((n-m+1)m)O(m+n)
向前移动字符个数1q-f(q)
回溯次数q-1无
其中：n为主串长度，m为模式串长度，q为匹配成功的字符个数
2KMP算法的改进
在KMP算法的实际应用中，发现该算法也存在着不足，结合下面的表一来论述KMP模式匹配算法的改进。假设模式串前4个字符与主串的第i+1..i+4匹配成功，第5个字符匹配失败，此时前缀函数f(4)=1，下一次匹配将从第i+4开始，并直接将模式串中的第2个字符与主串中的第i+5个字符进行比较，从表1中可知，匹配必将失败，此次比较是多余的。这说明此时的前缀函数f(x)并不是最优，需要对前缀函数进行改进。实质上，所谓对KMP算法的改进就是对其前缀函数的改进。
4结语
本文给出的算法较朴素匹配算法在效率上有了较大的提高，尤其是对重复字符出现较少的数据段进行模式匹配可取得较高的查找效率。应用于大型数据库的数据查询，会更加有效地缩短查找时间。
参考文献
[1]严蔚敏，吴伟民.数据结构[M].清华大学出版社，2001
[2]傅清祥，王晓东.算法与数据结构[M].电子工业出版社，1998
【关键词】深度挖掘匹配算法 毕业论文管理 应用
在毕业论文管理工作不断加强的情况下，注重管理模式的更新和合理选用，提高匹配算法的针对性，才能真正提高高校教务管理水平。因此，对深度挖掘匹配算法在毕业论文管理中的应用有比较全面的了解，才能为高校教务管理工作提供可靠参考依据。
1 深度挖掘匹配算法的相关分析
根据深度挖掘匹配算法在毕业论文管理中的应用情况进行全面分析来看，其主要包括如下两个方面：
1.1 志愿自动匹配算法的相关分析
对学生和课题的选择关系进行合理分析可知，两者的最优、最大匹配，最好是根据学生的实际情况量身定做，才能真正实现课题与学生的最完美匹配。因此，教师提出相关题目时，需要对学生的情况、特性和要求等进行全面分析，才能在学生对课题的特性、关联性等有一定了解的情况下，提高课题与学生的匹配概率，最终让学生选定最合适的课题。在实践过程中，志愿自动匹配算法的合理运用，需要根据毕业论文的管理流程，从教师出题开始。一般情况下，教师应该先提出大题让学生自由选择，在匹配学生确定好以后将大题分成几个小题，从而将每个小题分配给合适的学生。在这种情况下，教师设定的课题需要从修读课程达到的分数、难度、所属类别等多个方面确定，并从教务管理系统中获取学生的成绩和选题积分点等，才能根据分数线来判定学生是否符合相关选题。其中，选题的难度在简单、一般、难、很难和非常难几个等级，对应的成绩是及格、良好、优秀、极好。在实际进行选题时，学生可以根据自己的情况选择三个题目作为志愿，以在系统完成匹配后，自定将题目下发给学生。在实践过程中，初始化志愿显示的是学生的第一志愿，在经过while、if、else、break、continue等流程后，系统会将题目和学生进行适当分类，以确保题目与学生的匹配最合理、最科学。由此可见，志愿自动匹配算法是优先对具有课题相关能力的学生进行匹配的，在学生人数低于匹配数量的情况下，可继续为积分点高、能力稍差的学生进行匹配，对于确保课程成绩与积分点的完美结合有着极大影响。
1.2 调剂学生算法的相关分析
在经过上述算法进行匹配后，根据学生的实际情况进行深层挖掘，可以实现课题与剩余学生的完美调剂。因此，对上述阶段中匹配失败的学生志愿所选的教师、课题类别、难度等因素进行深度挖掘，并将搜索结果作为匹配课题的依据，才能在缩小搜索范围的情况下，找到与剩余学生最合适的课题。如果出现相近课题较多的情况，则需要有学生、工作人员共同协商，以确定最终和最适合学生的课堂。在实践应用中，调剂学生算法的运用需要对需要调剂的学生进行合理分析，并通过if、else、return、while、continue、else等多个流程，才能真正匹配出最适合学生的课题。
2 深度挖掘匹配算法在毕业论文管理中的实际应用
根据深度挖掘匹配算法的实际应用来看，在毕业论文管理中学生可以了解到最适合自己的课题信息，教师可以根据学生的积分点和成绩等确定课题，从而避免选择某一课题的学生过多或过少的情况出现，对于提高第一志愿自动匹配成功率有着极大作用。因此，在实际应用中，注重教师、课题类别、难度的合理设定，确保它们的排序科学，将课堂与学生的匹配关系看作是二分图，并且，每个学生可以选择的课题有三个，系统可以根据学生的实际情况进行自动匹配，最终深度挖掘与学生志愿匹配的课题。例如：志愿自动匹配和调剂学生的总数都为102人，通过深度挖掘匹配算法匹配成功的人数分别为72人和90人，成功率达到了70%、88%。在不使用任何算法进行匹配的情况下，两者的成功率是52%左右。由此可见，在毕业论文管理系统中，深度挖掘匹配算法在科学应用，可以为教务管理工作提供可靠参考依据，对于提高毕业论文管理工作人员的工作效率有着重要影响。
3 结语
综上所述，在深度挖掘匹配算法不断推广的情况下，其在毕业论文管理中的实际应用受到了很多教务管理工作人员的青睐。因此，充分发挥深度挖掘匹配算法的作用，提高深度挖掘匹配算法在毕业论文管理中的应用效果，才能更好的满足学生的选题需求。
参考文献
[1]冯丽慧，冯立智.数据挖掘在毕业论文成绩管理中的应用研究[J].电脑知识与技术，2012，30：7150-7153.
[2]徐章韬.用信息技术深度挖掘课程内容――以数学学科为例[J].教育发展研究，2015，12：29-33.
[3]连伊娜.深度挖掘高校档案文化内涵，更好为教育事业发展服务[J].黑龙江史志，2013，11：104-105.
作者简介
刘冰洁（1983-），女，江西省南昌市人。工程硕士学位。现为江西交通职业技术学院副教授。研究方向为大数据、系统集成、智能化技术。
关键词： 无线传感器网络； 数据收集； 单边匹配； 贪婪算法； 最优解
中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）15?0008?06
Abstract： The various applications of wireless sensor networks （WSNs） are restrained by the sensor′ battery in severe environment， and the WSNs face various difficulties in data collection， so the wireless energy transfer technology used to replenish the energy of sensor cluster is proposed. Aiming at the wireless rechargeable senor cluster deployed in severe environment， an efficient data collection scheme is proposed. In the scheme， the unmanned aerial vehicle （UAV） is used to arrive at the site of the sensor cluster in severe environment， after that the data is collected， and the sensors corresponding to the cluster are charged. In this paper， the utility function of data collection is defined to describe the data collection problem as an optimal problem taking utility maximization of data collection as the target， and the greedy algorithm based on bilateral preference matching and unilateral preference matching algorithm are proposed to solve the above problems. The theoretical analysis and simulation experiment results show that the matching relation of UAV and sensor cluster determined with the proposed greedy algorithm can generate the optimal solution of making data collection utility maximum， and can realize the efficient collection of sensor data.
Keywords： wireless sensor network； data collection； unilateral matching； greedy algorithm； optimal solution
0 引 言
在过去10年间，无线传感器网络（Wireless Sensor Network，WSN）获得了人们的广泛关注[1?2]。究其原因，一方面是因为WSN部署简单，另一方面是因为在战场侦察、环境监测、生物观察等领域具有巨大的应用潜力[3?4]。数据处理和计算技术的进步，使传感器可以测量多种领域中的数据（比如温度、压力、光照、湿度及红外线等）。但是电池技术进展缓慢，使电量有限的传感器受到严重的能量约束。此外，人们还希望利用WSN对广大区域实现无人值守式观察。虽然传感器部署简单（比如通过飞机散播在广大区域上），但是使WSN保持长时间运行，在大面积部署区域尤其是恶劣环境条件下实现传感数据的高效收集（比如高温沙漠、密林、雪山），难度很大[5]。
为了避免传感器的能量消耗完，学者们已经提出了多种能量节约[6]、环境能量利用[7?8]和增量部署算法[9]。然而，能量节约算法只能延缓能量被消耗的步伐，无法补充能量。对太阳能、风能和振动能等环境能量进行利用时，会受到这些能量可用性的约束，且这些能量的可用性往往不受人力控制。此外，部署的传感器节点可能会污染环境，因此增量部署算法对环境不够友好。
无线能量传输技术在近期取得突破[10]，为WSN的传感器能量补充提供了一种有力途径。具体来说，文献[11]中提出了3种无线能量传输技术，即：感应耦合技术、电磁辐射技术及磁共振耦合技术，同时介绍了这些技术在WSN中的应用。美国国家航空航天局（NASA）的电磁辐射实验[12]证明了能量远距离高效传输的可行性：在Goldstone网络实验中，NASA在1.5 km的距离上传输了34 000 W的能量，效率达到82%。另外，无人机（Unmanned Aerial Vehicle，UAV）技术越来越成熟，成本也不断下降。在此背景下，文献[13]利用一个无人机携带充电设备，周期性地访问传感器集群，对传感器实施无线充电，进而使WSN永久工作。文献[14]设计了一种移动式无线充电车，并通过实验验证了无线充电车在为WSN补充能量方面的性能。虽然在这些创新性研究中传感器能量得以补充，但WSN将数据以多跳方式从数据源向Sink节点传输时仍然浪费了大量能量。此外，对于部署在恶劣环境中的传感器集群，无线充电设备到达这些区域并收集这些感应数据将会消耗大量时间和成本。针对以上不足，本文并不是使用无线充电车，而是提出使用无人机携带无线充电器（如图1所示），同时利用UAV选择传感器集群，飞往被选择的传感器集群，并对集群中的传感器进行充电，同时将这些集群中的感应数据传输给Sink节点。本文的主要工作如下：
（1） 提出利用携带无线充电传输设备的UAV收集部署于恶劣环境下的传感器集群的感应数据，同时对相应集群中的传感器补充能量。具体而言，本文根据UAV到传感器集群间的距离、从传感器集群收集到的数据以及集群内传感器的剩余能量，定义了数据收集效用函数，并将数据收集问题描述为以数据收集效用函数最大化为目标的优化问题。
（2） 提出单边匹配算法和基于双边偏好匹配的贪婪算法解决上述问题，并通过理论分析和仿真实验验证了利用本文贪婪算法确定UAV和传感器集群间的匹配关系可生成使数据收集效用最大化的最优解，且可实现传感器数据的高效收集。
1 网络模型
假设在感应/监测应用中，多个传感器集群部署于恶劣环境中。每个集群包括一个中央Sink节点和一组传感器，其中传感器将其感应到的数据周期性地发往Sink节点。为了补充传感器的能量损耗、收集传感器的感应数据，利用一个或多个UAV飞往传感器集群，对集群中的传感器进行充电，通过相应集群中的Sink节点收集传感器感应数据。网络模型如图2所示。
2 本文算法
下面以匹配理论为基础，提出两种分布式算法来获得上述问题的最优解。首先给出单边偏好匹配算法，然后根据文献[15]中的Gale?Shapley算法将单边偏好匹配算法扩展为基于双边偏好匹配的贪婪算法。最后通过理论分析证明了算法的正确性。
2.1 匹配定义
匹配理论主要是解决如何将一组不可分的物品分配给一组申请人。每个申请人可能有多种偏好。以上述匹配概念为基础，可将本文研究的数据收集问题阐述如下：
设有一个实例[I]表示一组UAV[N=UA1，UA2，…，UAn]及一组传感器集群[?=SC1，SC2，…，SCm]。实例[I]中的主体是[??N]中的UAV和传感器集群。可接受的UAV?SC匹配对为集合[ε?N×?]。每个UAV[UAi∈N]有一组可接受的传感器集群[AUAi，]其中[AUAi=][SCj∈?：UAi，SCj∈ε]。类似地，每个集群[SCj∈?]有一个可接受的申请人[ASCj，]其中[ASCj=][UAi∈N ：UAi，SCj∈ε]。本文将[UAi]和[SCj]的匹配关系定义如下：
定义1 匹配关系[Φ]为如下函数：
[ΦUAi∈???，]且[ΦUAi∈0，1，…；ΦSCj∈][N ??，][ΦSCj∈0，1，]其中[ΦUAi=SCj]且[ΦSCj=][UAii∈N， j∈?]。
该定义表明，如果函数的输入是[SCj，]则[Φ]是一个单对单匹配。另一方面，如果函数的输入是[UAi，]则[Φ]是一个多对单匹配。在匹配理论中，本文中的主体（即UAV和SC）需要一个偏好列表才能开始匹配过程。因此，本文在选择传感器集群进行能量补充和数据收集前，要求每个[UAi]根据自己相对所有集群的效用形成一个降序排列的偏好列表。
2.2 单边偏好匹配算法
单边偏好匹配算法如下，分为两步：第一步，计算UAV的效用函数，然后，构建降序排列的偏好列表[UALISTi，]同时构建一组未匹配的传感器集群[UNMATCH；]第二步，根据偏好列表[UALISTi]构建匹配关系。[UAi]向[UALIST]中层次最高的未匹配集群[SCj]做出申请，并将[SCj]从[UNMATCH]中移除。如果[UNMATCH≠?]，则算法回到第2步开始。算法不断进行匹配过程的迭代，直到[UNMATCH=?]。
3. 算法结束
2.3 贪婪算法：双边偏好匹配
第2.2节从UAV角度给出了单边偏好匹配算法。为了进一步提升系统效用，本文进行双边偏好匹配，即从UAV和传感器集群两个角度进行匹配。
传感器集群也可以构建它们自己的偏好列表。然后，每个[UAi∈N]或每个[SCj∈?]均有一个按严格次序排列且互不相同的偏好列表。
文献[15]提出一种可以始终找到稳定性匹配关系的Gale?Shapley算法。本文以该算法为基础提出一种贪婪算法。在第一阶段，它计算UAV和传感器集群的效用函数。然后，构建按降序排列的偏好列表[UALISTi]和[SCLISTj]。它还构建未匹配传感器集群组成的集合UNMATCH。根据偏好列表[UALISTi，][UAi]向[UALISTi]列表中之前从未拒绝过自己且层次最高的集群[SCj]做出申请。如果[SCj]还未被匹配，则保留配对[UAi，SCj]。如果[SCj]已经被匹配，则[SCj]检察新采用的[UAi]和上一次迭代时的[UAi]的等级。[SCj]与其[SCLISTi]列表中等级较高者匹配，排除另外一个。被拒绝的[SCj]添加到UNMATCH中，等待下一轮匹配过程。如果[UNMATCH≠?，]则算法回到第2步。即使[UNMATCH=?，]但[UAi]还没有结束对所有[SCj（j∈?）]的申请，则算法仍然回到步骤2。只有[UNMATCH=?]且每个UAV均申请过所有[SCj（j∈?）]时，算法才终止。
3.算法结束
2.4 理论分析
为了便于分析，下面首先给出了“最优匹配”的定义。
定义2 最优匹配：如果在约束条件[j∈?xij≤1]下，对匹配关系[Φ，]式[i∈Nj∈?UUAji]被最大化，则认为[Φ]为最优匹配。
以该最优匹配定义为基础，有如下理论：
定理1 贪婪算法获得的匹配关系[Φg]为最优匹配。
证明：如果对匹配关系[Φ，]在约束[j∈?xij≤1]下，式[i∈Nj∈?UUAji]最大化，则每个[SCj]必与其偏好列表中层次最高的[UAi]相匹配，现将其表示为[UAjf]。
假设[Φ]最优，但是至少有一个[SCj]不与其[UAjf]匹配。根据贪婪算法，在第一轮中，[SCj]与向其申请且等级最高的[UAi]匹配，现将其表示为[UAjrh]。在下一轮中，如果新申请的[UAjrh]级别高于[UAjrh，]则[SCj]将会与[UAjrh]匹配且[UAjrh]被拒绝。因此，发现[SCj]总是与UAV中级别最高且向[SCj]做出申请的UAV相匹配。每个[UAi]有一个偏好列表包括所有的[SCjj∈?]，这说明所有的UAV将会向各个[SCj]做出申请。于是，每个[SCj]均与其[UAjf]匹配，与至少有一个[SCj]不与其[UAjf]相匹配的结论相矛盾。所以，贪婪算法获得的匹配关系[Φg]是最优匹配。证毕。
3 性能评估
3.1 仿真配置
本文利用部署在10 km[×]10 km区域上的UAV和传感器集群进行仿真实验。电池容量为[emax=70 J，][SCj]中传感器节点的剩余能量为[ejk∈60，65 J]。每个集群中的传感器数量为[SCj∈50，100]。发射功率为[Si=1.2 W，]UAV的速度为120 km/h。对于其他参数，传感器的数据率从[1，10] Kb/s中随机生成。在网格拓扑和随机拓扑结构上分别进行了仿真实验，取20次仿真结果的平均值作为最终的实验结果。
3.2 结果和分析
为了评估本文算法的性能，对最优匹配、贪婪算法、单边匹配算法以及随机匹配算法进行了比较。图3给出了UAV数量固定时的仿真结果，此时传感器集群数量为25～40个，传感器集群分别部署于网格拓扑和随机拓扑结构上。从图3中可以发现，本文提出的贪婪算法的性能和最优匹配的性能一样，而单边匹配算法的性能远优于[UAii∈N]和[SCjj∈?]的随机匹配算法。因为单边匹配算法考虑了UAV的偏好列表，每个[UAii∈N]有机会向其[UALISTi]偏好列表中的最高级别[SCj]做出申请，所以单边匹配算法的性能优于随机匹配算法。此外，贪婪算法的性能优于单边算法。在贪婪算法中，集群在构建偏好列表时的效用函数与UAV进行决策时的效用函数相同。[SCj]可拒绝向其做出申请的[UAi，]选择可显著提升系统效用的更为合适的UAV。
图4给出了系统效用随网络规模的变化关系。当网络规模增加时，系统效用增加。此外，当网络规模增加时，贪婪算法与单边算法及随机匹配算法间的性能差异增加。这表明，当UAV的数量和位置固定时，相比于单边匹配算法和随机算法，本文贪婪算法更适用于大规模WSN。当网络规模增加时，受欢迎传感器集群的数量也在增加（在所有UAV偏好列表中均有较高等级的集群定义为受欢迎集群）。无论在单边匹配算法还是随机匹配算法，受欢迎集群均无法拥有其偏好列表。因此，传感器集群很可能做出非最优决策，降低系统效用。
图5给出了匹配决策和航行时间之间的关系。为便于讨论，这里只给出包含两架UAV的情况。采用贪婪算法确定UAV和集群间的匹配。星星表示UAV飞到每个集群处的时间，方形表示飞到与[UAi]相匹配的[SCj]处的航行时间，圆圈表示飞到未被匹配[SCj]处的航行时间，该时间至少比一个被匹配的[SCj]短。在图5中发现虽然部分集群与UAV较近，但它们未与任何UAV相匹配，这是因为匹配决策不仅与航行时间有关，还与充电时间和传感器集群的数据量有关。匹配关系并不只存在于相距最近的UAV和传感器集群间。此外，在图3中还发现最优算法的曲线与贪婪算法的曲线相吻合。仿真实验证明了贪婪算法确定的匹配关系是最优匹配这一结论。
4 结 语
本文研究了如何使用UAV高效收集部署于恶劣环境中的无线可充电传感器集群的感应数据。通过考虑无线能量传输的特点，将高效数据收集问题描述为多种约束条件（即UAV和集群间的距离，集群中Sink节点处汇集的数据量以及集群中传感器的剩余能量）下的优化问题。为了使上述问题中的系统效用最大，提出两种基于匹配理论的分布式算法，单边匹配算法和贪婪算法，同时证明贪婪算法最优。仿真实验验证了本文的理论分析结果，证明本文算法可实现感应数据的高效收集，同时可对恶劣环境中的传感器集群充电。在下一步工作中，将分析移动Sink条件下传感器节点无线充电与数据收集质量的关系，研究面向高效数据收集的移动Sink路径规划算法。
参考文献
[1] 李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）：1?15.
[2] 郭忠文，罗汉江，洪锋，等.水下无线传感器网络的研究进展[J].计算机研究与发展，2010，47（3）：377?389.
[3] 张豫鹤，黄希，崔莉.面向交通信息收集的无线传感器网络节点[J].计算机研究与发展，2008，45（1）：110?118.
[4] GUO S， HE L， GU Y， et al. Opportunistic flooding in low?duty?cycle wireless sensor networks with unreliable links [J]. IEEE transactions on computers， 2014， 63（11）： 2787?2802.
[5] ZHAO M， LI J， YANG Y Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks [J]. IEEE transactions on mobile computing， 2014， 13（12）： 2689?2705.
[6] BOUABDALLAH F， BOUABDALLAH N， BOUTABA R. Cross?layer design for energy conservation in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Communications. Dresden： IEEE， 2009： 1?6.
[7] PARK C， CHOU P H. AmbiMax： autonomous energy harves?ting platform for multi?supply wireless sensor nodes [C]// Proceedings of 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston： IEEE， 2006： 168?177.
[8] FAN K W， ZHENG Z， SINHA P. Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks [C]// Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. Raleigh： ACM， 2008： 239?252.
[9] PENG Y， LI Z， ZHANG W， et al. Prolonging sensor network lifetime through wireless charging [C]// Proceedings of 2010 31st IEEE Real?Time Systems Symposium. San Diego： IEEE， 2010： 129?139.
[10] BEH T C， KATO M， IMURA T， et al. Automated impedance matching system for robust wireless power transfer via magnetic resonance coupling [J]. IEEE transactions on industrial electronics， 2013， 60（9）： 3689?3698.
[11] XIE L， SHI Y， HOU Y T， et al. Wireless power transfer and applications to sensor networks [J]. IEEE wireless communications， 2013， 20（4）： 140?145.
[12] WANG R， YE D， DONG S， et al. Optimal matched rectifying surface for space solar power satellite applications [J]. IEEE transactions on microwave theory and techniques， 2014， 62（4）： 1080?1089.
[13] XIE L， SHI Y， HOU Y T， et al. Making sensor networks immortal： an energy?renewal approach with wireless power transfer [J]. IEEE/ACM transactions on networking （TON）， 2012， 20（6）： 1748?1761.
Key words： highway freight;vehicle cargo match;information platform
0 引言
公路货物运输业一直是国民经济发展中的一个基础性和先导性产业。统计公报显示，2017全年货物运输总量479亿吨。公路货物运输总量368亿吨，同比增长10.1%;可见公路运输的占比在所有交通运输方式中是最高的。随着我国货运总量连年提升，公路货运的占比也在不断提高。但目前我国货车实载率不及60%，远低于发达国家 80%～95%的水平。传统线下物流大多数存在着多、小、散、弱等问题，人找车难、车找货难的问题也屡见不鲜。随着中国互联网飞速发展，“互联网+”、大数据、云计算等早已深入货运行业。车货匹配信息平台有效的缓解了信息不对称，减少了车辆空载和社会成本，同时为车货双方提供了货物配载信息服务，但目前还不具备按双方需求实现快速智能匹配的功能。为了解决当前物流需求多样性，服务对象不确定性，车货匹配信息不对称及车货匹配效率低等问题，减少较大的经济损失和社会资源浪费。本文从车货匹配的决策建模，理论方法及信息平台等三个方面，汇总了针对车货匹配的国内外学者观点，并且囊括近些年来相关领域的优化问题，回顾了相关成果的研究热点、模型特征，并提出了未来公路车货匹配研究中应该关注的主要问题。
1 车货匹配决策建模理论研究
车货的有效匹配可以提高物流资源的利用率，降低运输车辆的空驶率。本文主要从车货匹配决策建模方面对前人的研究文献做简要综述。
陈进博等人[1]基于信息、功能及效益三大模块并应用MA-OWA算子进行权重赋值，结合车货匹配网站的业务流程构建了评价指标体系。姚国龙[2]提出结合精益物流思想特征和专家调查法对车货匹配中的具体要素进行评价，采用定性与定量的AHP模糊综合评价法分析过程中的问题。张庆英等人[3]，采用权重分析法对物流企业和个体用户交易指标进行打分，以承运商和托运方估值之和作为车货信息匹配交易的撮合机制。孙彬[4]通过构建智能匹配模型及指标体系实现了基于地域因素的第四方物流平台的供需智能匹配。李慧[5]运用理论分析法，模糊综合评价法和多目标匹配排序法为供需匹配模块建立以货源方、车源方为主的车货两层筛选匹配指标体系。胡觉等人[6]提出了利用信息评价体系，大小数量规模下的TS算法和PSO算法，PSO-TS混合算法等证明了TS算法在车货匹配问题上的有效可行性。郭静妮[7]，利用三角模糊数及清晰化的效用函数构建了车货双方多指标语言评价体系。黄美华[8]等人根据车货信息平台的特点用最小二乘支持向量机来匹配需求信息，并建立了车货信息匹配模型。吴广盛[9]以货源方和车源方为主导偏好因素提出车货供需匹配排序模型，并提出匹配指标和信誉评价体系。牟向伟等[10]提出了利用量子进化算法对车货匹配模型进行设计与改进，并采用约束惩罚的适应度衰减方法解决了量子群初期无强可行解时最优量子个体的选择问题。陈火根[11]等人讨论了在电子交易市场上利用网络服务信息建立了子目标任务，人工干预交易协商，并实现车货匹配资源自动配对。陆慧娟等人[12]利用软件及服务（SaaS）与计算机支持的协同工作（CsCw）相结合，采用车辆混合禁忌搜索算法，构建“货找车”的高智能车货匹配系统。王训斌等人[13]构建了多目标多层级公路车货匹配系统，并采用车辆混合禁忌搜索算法对其进行优化。陆江[14]研究了基于虚拟物流平台的公路零担运输车货匹配模型，选定遗传算法作为模型的求解算法，并使用Java语言实现了算法。张涛和赵冰洁[15]运用遗传算法对车辆调度实际问题进行研究。李建民[16]等人针对车货配载过程中的货选车和混载的问题构建了多目标规划模型，并提出运送价格和车主可靠程度是其重要的影响因素。顾佳倩[17]利用Java程序，以语义网本体和自定义推理规则为知识导向搭建了车货基于语义的相互匹配。张璐[18]通过了解交易双方策略，研究并分析了基于公路货运信息平台的组合拍卖机制对运力资源的订单分配等领域问题。蒋忠中等人[19]分析了多属性商品交易中存在的模糊信息，并建立了的新的交易匹配模式。常连玉，陈海燕[20]基于主体诉求和运价机制，利用神经网络和微粒子群智能算法对运力组织优化模型进行了求解。Karen Renee Smilowitz[21]通過分析研究实例UPS路网对多式联运运输系统网络发表了最新的见解。Lao和Goh[22]用JAZZ技术实现了一个基于智能匹配的网上支持4PL业务的系统。研究成果提出了很多建模决策方法例如 “语义网技术”，禁忌算法，模糊综合评价法，层次分析法，神经网络，微粒子群等。对车货智能匹配功能和车货双方的多指标评价体系也进行了较丰富的研究。
2 车货匹配相关理论方法研究
在合理的市场机制下双方能够基于各自的偏好进行稳定的市场匹配称之为双边匹配理论，以其为基础导向从车货匹配平台与车、货双方关系出发，运用分析方法和建模，能够有效的解决实际问题。所以本文重点探讨双边匹配理论在车货匹配问题上的研究。
国内相关研究成果：贾兴洪等人[23]基于双边市场和演化博弈理论，构建了车货匹配平台双边用户交易博弈模型，提出平台用户单归属比率提升的最优控制。宋娟娟等人[24]提出物流信息平台具有双边服务、交叉网络外部性等特性，并建立配套信用机制对平台用户资质进行认证。赵保燕[25]以双边市场理论为基础构建了车货物流平台并用平衡计分卡模型对模式的各个维度进行评价。李铭洋等人[26]基于车货双方的序值偏好，构建了主体序值和最小的目标函数模型。樊治平等人[27]基于双边匹配稳定满意的出发点，建立了以满意度最大化为目标的双边匹配模型。张振华和汪定伟[28]从权匹配的角度阐述了稳定性匹配问题，提出按重要性从大到小排序，使每一个结点上的匹配主体都尽量得到最优匹配。
国外相关研究成果：Roth[29]最早明确公开提出双边匹配的概念，在1985年发表的文章“Conflict and conflicting interests in two sided matching markets”中界定了“双边匹配”和“双边”的概念，并分析了双边匹配的现实例子。Gale和Shapley[30]于1962年在“American Mathematical Monthly”上“大学录取和稳定婚姻匹配问题”。Rochet等人[31]在其working paper中首先从价格结构的不对称性角度给出了双边市场的定义。Armstrong [32]进一步强调了双边市场中一边用户对另一边用户数量的依赖性。 Gardenfors [33]以指派理论为依据研究了双边匹配问题。Vate[34]在研究中指出最大化线性目标函数的稳定匹配能够通过线性规划计算出来，认为稳定匹配是一个线性规划问题。Fleinr[35]提出可以用不动点理论来解释双边匹配问题并分析了Gale-Shapley的稳定婚姻理论与Tarsk不动点理论的联系。Roth[36]在双边匹配市场的理论基础上创新性的提出了如何识别非空内部点的方法，同时在Shapley和Shubik[37]研究的转让市场的理论核心基础上得出一套固定点。Korkmaz等人[38]提出双边匹配模型是将雇员和雇主进行有效匹配并使每一边都接受匹配结果，还指出双边匹配理论可以用在指派问题中。
双边匹配理论为匹配的稳定性，线性规划都做了开拓性的研究。车货匹配依据双边匹配理论可以分为一对一匹配，一对多匹配，多对多匹配模型。但双边匹配理论针对车货匹配问题的研究尚处于探索阶段，已有的成果还存在不足之处。
3 车货匹配信息平台研究
当下我国公路货运成本居高不下，存在大量物流资源的浪费，而其中很重要的原因就是物流信息不对称。车货匹配信息平台的设计就是为了减少或消除信息不对称，实现车货在最优条件下的匹配。本文主要是从车货匹配信息平台方面进行阐述。
刑鹏[39]针对车货匹配信息平台问题提出加强云计算与配送之间的联系，从而产出云配送模式。熊然[40]分析了部分地区公路货运行业的主要问题，不仅指出了车货匹配信息平台给车货双方和社会带来的正面意义还提出交易安全性和信息真实性的重要性。王博，朱杰[41]分析了代表性行业的物流现状，对物流信息平台与车货匹配信息平台进行对比，强调了资源整合的重要性 。张松[42]针对货运配载行业的发展现状提出了影响公路货运返程配载效率的因素，并比较分析了南京主流的配载模式。汪逸敏[43]从公路货运平台经济的角度出发，指出配货需求不能局限于落地配等单一模式应当趋于随机与碎片化模式。熊宜强[44]提出利用“反馈式竞争法”进行权重改进，研究了车货匹配排序诚信激励机制和信号博弈模型等级划分机制。
在车货匹配信息平台中物联网、云计算、大数据及移动互联网技术扮演着重要的角色，不仅能够为系统结构提供科学依据，还可以为未来智能发展方向，及运作机理提供建设性思路。
【关键词】藏文分词 匹配算法 哈希表 词典机制
1 引言
藏文信息处理存在着分词的问题，而藏文分词是对藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理的基础。藏文分词的效果会对进一步研究的藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理软件的性能和效果产生影响。
为了提高分词的准确率，需要有一个足够大的词库，面对足够大的词库，对词库中的词语的搜索技术就显得十分重要，对词库中词语的搜索速度直接关系到分词系统的性能。词库目前主要是采用索引的机制来实现的，一般用到的索引结构的包括线性索引、倒排表、Trie树、二叉树等。线性索引、倒排表都是静态的索引结构，不利于插入、删除等操作。
2 分词
2.1 词典机制算法
本系统采用的是基于Hash索引的分词词典。分词词典机制可以看作包含三个部分：首字Hash表、词索引表、词典正文。词典正文是以词为单位txt文件，匹配过程是一个全词匹配的过程。首先，通过首字Hash表确定该词在词典中的大概位置，然后根据词索引表进行定位，进而找到在词典正文中的具置。该系统是采用Myeclipse10平台，使用Java语言进行实现的，直接调用Java里的hashmap创建函数，找到该词之后，然后进行字符串匹配。
2.2 基于匹配算法分词
主流的分词方法有三种：分别为基于语言学规则的方法、基于大规模语料库的机器学习方法、基于规则与统计相结合的方法，鉴于目前藏文方面还没有超大型的句子语料库。该系统便采用了基于语言学规则的根据词典进行匹配的方法对藏文进行分词。
根据匹配的方向不同，分为正向和逆向两种匹配算法。本系统采用的是正逆向匹配算法相结合的减字匹配法对藏文进行分词的，因为藏文在每个字的结束时，都会以“”作为分界；每个句子会以“”或者“” 作为分界。因此，对藏文进行分词的减字算法首先以藏文的字符“”或者“”切分出句子，如此一来，原文就被分为相应的若干个句子了。接下来，再对每一个句子进行词典的匹配，如果没有匹配成功就根据藏文字符中“”从句末尾减去一个字符，然后再次进行匹配，直到匹配成功为止。对每个句子重复这些流程，直到每个句子全部分解为词为止。逆向最大匹配是从句子的末尾选择计算最大词的长度，从后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。
为了提高切分的精度，该系统使用的是正向最大匹配和逆向最大匹配相结合的方法进行分词，先分别采用两种方法分词，然后根据概率比较两种分词结果，选择概率较大的那种匹配算法作为分词结果。
本系统的逆向最大匹配和正向最大匹配均是采用减字匹配算法，减字算法实现简单，切分效果也比较理想，流程如图1所示。
正向最大匹配（MM） 对于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判别CD是否属于W，若是，则就切分为AB/CD，如果不是，则切分为AB/C/D。其中W 为分词的词典。逆向最大匹配对于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W为分词的词典，那么就取切分 AB/CD，根据藏文词组最长的为6个字符组成的，所以进行匹配算法的时候，初始化藏文最大字符串长度为6，流程图如图2所示。而逆向最大匹配算法是从句子的末尾开始进行匹配，其核心算法与正向最大匹配算法相同，只不过开始匹配的方向不同而已。
无论是正向匹配（MM）算法还是逆向匹配（RMM）算法都会产生大量的歧义字段。我们很容易举出这样的例子，如：（五十六个民族心连心）这一句藏语，采用正向匹配算法分词的结果为：，采用逆向匹配算法的分词结果为：，在采用逆向匹配的时候，将会被划分为，而（五十六）实际是一个词，不该划分，诸如此类的藏文句子还有很多，例如 等，无论使用正向最大匹配算法或者使用逆向最大匹配算法都会产生歧义，这种歧义称为组合歧义。为了减少这种歧义的影响，本系统使用两种分词方法相结合的方式。首先分别使用两种算法进行分词，然后通过统计的方法消除部分歧义。具体实现为：设正向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为；设逆向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为。如果，则选择正向最大匹配算法所切分的结果，反之，则选择逆向最大匹配算法所切分的结果。
3 结果和分析
结合26个大小不同的实验文本，对基于哈希表索引和匹配算法的分词系统的准确率进行了分析，准确率如图3所示。结果显示，该分词系统的准确率在92%以上。由此可得基于哈希表索引和匹配算法的分词系统在准确率上有不错的效果。
参考文献
[1]华却才让.基于树到串藏语机器翻译若干关键技术研究[D].陕西师范大学，2014.
[2]石方夏，邱瑞，张|，任帅.藏文信息隐藏技术综述[J].物联网技术，2014，12：28-32.
[3]王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006，05：24-30.
[4]陈硕，桂腾叶，周张颖等.信息检索在论文写作和项目申报中的应用[J].科技展望，2015，13：274-275.
[5]黄昌宁，赵海.中文分词十年回顾[J]. 中文信息学报，2007，03：8-19.
[6]奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011，02：41-45.
[7]贺艳艳.基于词表结构的中文分词算法研究[D].中国地质大学（北京），2007.
[8]戴上静，石春，吴刚.中文分词中的正向增字最大匹配算法研究[J].微型机与应用，2014，17：15-18.
[9]刘遥峰，王志良，王传经.中文分词和词性标注模型[J].计算机工程，2010，04：17-19.
作者简介
陈硕（1995-），男，自治区拉萨市人。本科在读，主研领域为自然语言处理，数学建模及其应用。
周欢欢（1994-），女，湖南省衡阳市人。本科在读，研究方向为数学建模及其应用、交通运输规划与管理。
通讯作者简介
赵栋材（1976-），男，现为大学藏文信息技术研究中心副教授。主要研究方向为藏文信息处理。
作者单位
关键词：毕业论文；KM算法；选题系统
中图分类号：TP311.52
1 引言
在现有的毕业论文选题系统中，一个学生只能选择一个题目作为自己最终的题目，同样，一个题目只能分配给一个学生。如果最后题目由学生自己确定，那就会出现先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说很不公平。如果学生选择自己的志愿，最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如何采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，会大大提高选题的效率。
汤颖曾在《毕业设计立项与选题管理及其支持系统》中提出，采用模糊匹配技术进行学生-题目的自动匹配；潘志方在《一种改进的Ford-Fulkenson算法在选题系统中的应用研究》中将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现题目与学生的自动匹配。以上两种方法只考虑了学生与题目之间的最大匹配值，并没有考虑学生的整体满意度最优的情况。
本文将通过采用最优匹配算法（KM）确定一种匹配方案，使得学生的整体满意度最高。具体方法概括如下：学生预选多个题目，并根据自己对题目的满意度由高到底排序，这样，满意度成为二分图的一分值，如图1所示：
2 系统功能模块设计
根据前期的可行性分析，本系统主要进行以下模块的设计：系统管理员模块、专业负责人管理模块、指导教师管理模块和学生选题模块。
系统管理员模块主要负责对系统参数的设置及用户的管理。主要实现以下功能：
（1）系统设置：对系统标题、毕业生、选题参数设置；
（2）学院及专业设置：完成学院、专业的添加、删除、修改操作；
（3）数据字典的维护：教师信息、选题难度、选题方向灯信息的维护；
（4）教师和学生的管理：完成教师、学生信息的添加、删除和修改操作；
（5）文件文化建设管理：日志文件查看、上传文件的管理。
专业负责人管理模块与系统管理员权限相似，但操作的数据只能针对于指定专业，无法浏览及操作整个学院的课题及学生信息。最重要的功能是实现题目的审核。
导师管理模块主要用于选题以及选择自己选题学生的审核确认。
（1）个人中心管理：如信息修改及密码重置；
（2）选题管理：选题的增加、修改、删除以及选题类型的设置；
（3）学生选题查询及审核。
学生模块主要实现学生选题的选择及确认。
（1）学生个人信息的修改；
（2）学生选题及确认信息查询；
（3）学生留言及咨询。
3 KM算法在系统中的实现
KM算法由Kuhn和Munkras分别提出来，这是一种问题。经典的算法。该算法由通过每个顶点一个顶标（A[i][j]）来求最大权匹配的问题转化为不断寻找增广道路以使二分图的匹配数达到最大的完备匹配。KM算法的关键在于不断寻找二分图中的可增广道路。如果找到一条可增广道路，就可以额将属于和不属于相等子图的边取相反，从而相等子图里就是增加一条边，一直到所有的顶点都进入相等子图为止。
KM算法可以很好地解决选题系统中，题目与学生最优匹配的问题。下面以国际商学院09级本科学生选题为例。
在匹配过程中，设学生的集合为X={X1，X2，X3……Xn}，选题的集合设置为Y={Y1，Y2，Y3……Yn}，学生对自己选题的满意度为二维矩阵Z[m][n]，其他题目规定权值为0。系统规定学生最多可预选3个题目，并按照满意度分别设置0.9，0.7，0.5。以下表1是对国际经济与贸易专业使用不同算法得出的学生满意程度。
下面对以上数据进行说明。如采用手工分配的方式，使得681名学生中414名同学分的了题目，满意度为60.82%；如果采用最大匹配算法进行分配，可以使分配数达到最大，有517名学生分得题目，满意度上升为79.99%；最有用最有匹配算法进行分配，使总体满意度达到78.24%，533人。需要说明的一点是，KM算法只是找到了整体最优匹配而不是最大数匹配，如果整体最优情况下匹配数和最大匹配数相差得太大的话，那么整体最优方案显得不太可取。所以，最好的情况就是同时考虑最优匹配和最大匹配来同时控制两者的大小。
4 结语
本系统实现了毕业论文选系统工作的各个管理功能，通过实现教师与学生的双向选择，使用KM算法，提高选题的质量和效率，为学院充分利用网络完成毕业论文选题工作提供了便利的平台。
参考文献：
[1]汤颖.毕业设计立项与选题管理及支持系统[J].合肥工业大学学报，2006，29（5）.
[2]潘志方.一种改进的ford算法在选题系统中应用研究[J].计算机应用与软件，2007，24（9）.
关键词：双边匹配理论；发展；应用；金融市场
中图分类号：F830 文献标识码：A 文章编号：1674-2265（2013）06-0020-04
2012年的诺贝尔经济学奖得主研究的一个重要问题是如何使不同的市场主体匹配起来，并且达到一个稳定的状态。同其他市场一样，金融市场的一项重要的功能就是把市场的一方主体与另一方主体匹配起来。但是如何使双方达到一个稳定匹配的状态，使匹配更有效率，是当前金融市场面临的一个核心问题。本文将对双边匹配理论的发展与应用进行梳理，并重点对该理论在金融市场的应用问题进行研究。
一、关于双边匹配理论
（一）双边匹配理论的起源与发展
罗思（Roth，1985）是最早明确公开提出双边匹配概念的，他不仅明确地界定了“双边”和“双边匹配”的概念，而且分析了双边匹配的现实案例。罗思认为双边就是指事先被指定好的两个互不相交的集合，而双边匹配是指在这些市场中双边人的匹配。
2012年诺贝尔经济学奖的颁布丰富了双边匹配问题的研究方法。诺贝尔经济学奖得主提出了“稳定匹配”的概念，从而使匹配由“个人理性匹配”①走向了“稳定匹配”。沙普利（Shapley）采用合作博弈理论，在比较了不同匹配方法的基础上，用“G—S算法”来保证总能获得稳定的匹配，这一算法还可对各方试图操纵匹配过程的做法加以限制。罗思在沙普利的理论基础上，通过一系列的研究，发现稳定是市场机制运行成功的关键因素，并运用这些研究成果重新设计了现有的很多市场匹配机制，使匹配更有效率。
（二）双边匹配理论与搜寻—匹配理论的关系
搜寻—匹配理论与双边匹配理论都起源于20世纪60年代，搜寻—匹配理论研究的是在“摩擦市场”中，哪些因素会影响求职者的求职策略、工作搜寻强度及失业持续时间，以及如何匹配市场上的空缺职位和失业者；而双边匹配研究的是在具有双边市场特征的市场上，如何使市场双方主体匹配起来，并且形成稳定的状态。戴翔（2012）指出，搜寻—匹配理论的核心思想是：因为现实中存在着各种交易摩擦，从而产生了搜寻与匹配成本，这最终会致使交易的不顺利；双边匹配理论的核心是双边市场的双方人如何达到一个稳定的匹配状态。搜寻—匹配理论的研究方法包括匹配函数、劳动力市场基准模型——DMP基准模型；双边匹配理论的研究方法包括G-S算法、H-R算法、线性规划方法等；搜寻—匹配理论主要应用在网络金融信息等方面，双边匹配理论的应用方面更广，主要包括劳动力市场、人与组织匹配、电子商务、器官捐献和金融市场的风险投资、企业合并、银行信贷等方面。
（三）稳定的双边匹配与有效配置②的关系
有效配置状态就是指处于帕累托最优状态。稳定匹配的概念强于帕累托最优匹配，因为每个稳定匹配是帕累托最优的，然而不是每个帕累托最优匹配都是稳定的。帕累托最优要求没有两个人希望匹配在一起并且需要对方的同意。相比之下，稳定匹配要求没有两个人希望匹配在一起，无论对方是否同意。
二、双边匹配理论在国内外的应用
学者们对双边匹配问题进行深入研究并加以提炼，针对现实中的双边匹配问题进行了分析，尝试用双边匹配决策理论来解释具体的现象和问题。双边匹配理论的研究结合实际应用背景进行了有实用意义的扩展，广泛地应用于很多领域。
（一）双边匹配理论在国外的应用
1. 实习生与医院的双边匹配。实习生与医院的匹配是匹配理论较早的运用。在美国有一个制度，医学院的学生毕业后都要到各医疗机构实习。在早期，医学院毕业生实习市场比较无序，双方匹配很不稳定。为了达到稳定匹配，这个市场引入了“全国住院医生匹配项目（NRMP）”，刚开始比较成功，但后来NRMP也遇到了问题。1995年罗思和他的同事合作，对已有的匹配算法进行了改进，从而使这个市场运行更加稳定。
2. 学生与学校的双边匹配。学生入学匹配问题也是较早提出的双边匹配问题之一，匹配双方是学校和学生。学生在学校的录取优先权排序是学校对学生的偏好排序，而学生对学校的偏好排序是传统匹配理论中的排序，匹配的目标是使学生与学校都达到满意的结果。张、塞特曼和谭（Teo、Sethuraman和Tan，2001）对新加坡小学生升入中学进行了研究，研究发现小学生和学校在匹配过程中诚实地表达自己的偏好有利于形成稳定的匹配结果。
3. 人—组织双边匹配理论的应用。关于人—组织的双边匹配，目前主要有两种观点：大多数学者认为人—组织的匹配就是组织成员的个人特征与组织特征之间的相互包容性；少数学者认为人—组织的匹配是组织成员的个人特征与组织特征之间的互补性。克里斯托夫（Kristof，1996）认为一致性匹配就是组织的价值观、目标、文化等基本特征与个人的价值观、目标、人格等基本特征在很大程度上都一样，而互补性特征就是组织和个人双方的特征可以互为补充。另外，卡普兰（Caplan，1987）构建了关于个人—组织匹配的模型，包括需要—提供匹配和要求—能力匹配两种模型。其中需要—提供匹配就是组织能提供满足个人需要的岗位；要求—能力匹配是个体的能力能够适应组织的需要。
4. 电子商务中双边匹配的应用。匹配理论在电子商务方面的运用起于20世纪，并一直运用到现在，而且运用面更广、更灵活。郑（Jung，2000）用人工智能的方法来研究电子商务中的双边匹配问题，并且获得了稳定的匹配结果。萨尔尼和克劳斯（Sarne和Kraus，2008）建立了在电子商务中面向多个人的分布式的双边匹配机制。
（二）双边匹配理论在国内的应用
国内关于双边匹配的研究起步较晚，相关的理论研究相对滞后，研究成果主要是应用方面，但是应用研究范围相对较窄，研究的领域主要包括高考招生、劳动力市场、电子商务和金融市场等。
1. 高考招生中的双边匹配理论应用。双边匹配理论在高考招生中应用的研究范围涵盖了稳定匹配方案的存在性、研究方法的选择、信息环境对匹配效率的影响等。温忠麟（2006） 使用操作性方法验证了校方优先方案和考生优先方案，即稳定匹配的方案是存在的。李坤明（2010）分析了完全信息条件和不完全信息条件下考生的偏好，表明信息环境对高考录取机制配置效率有重要的影响，反过来高考录取机制又对信息环境具有依赖性。
2. 劳动力市场中双边匹配理论应用。张成（2010）借鉴双边匹配理论在国外劳动力市场的应用，并结合国内劳动力市场的特点，利用双边匹配理论的语言建立模型对我国大学毕业生劳动力市场进行描述。赵希男等（2008）构建了组织中人—岗匹配的纵向匹配度和横向匹配度测算模型来测算人与岗位的匹配程度，并通过实际案例证实了模型的有效性。
3. 电子商务中的双边匹配理论应用。近年来电子商务飞速发展，在电子商务中基于电子中介买卖双方的匹配问题，是一个典型的双边匹配问题。对双边匹配理论在电子商务中应用的研究是由理论到实证层层推进的。徐晓辉和陈剑（2000） 从产品和服务的标准化程度、顾客对产品网上销售的态度和顾客体验度三个方面，提出了一个判断产品是否适合在网上销售的标准框架，从而开启了对产品电子商务匹配度的初步探讨。基于电子商务业务的特殊性，可能出现多对多的情况，张振华、贾淑娟等（2008） 将Gale-Sharply和H-R算法从理论上扩展到了“p-k”的情况，以处理多对多双边匹配问题。
三、双边匹配理论在金融领域的应用
在我国金融领域，有些市场是研究双边匹配理论的天然场所，但是国内外学者们对双边匹配理论在金融领域的应用只有一些具体金融方面的研究，至今未形成一个体系。目前的研究主要在风险投资项目、企业并购、投资以及银行信贷方面得到应用。
（一）双边匹配理论在风险投资中的应用
在市场经济活动中风险投资商与风险投资项目或者创业者的匹配是一种典型的双边匹配模式，最优秀的风险投资商期望能够选择最好的风险投资项目，最好的项目也期望能有一个最优秀的风险投资商对其投资。 索伦森（Sorensen，2007） 采用定量分析方法分析了风险投资商与风险投资项目的双边匹配效应，认为双边匹配模式对风险投资商和风险投资项目产生双向的正的积极影响。在国内，曹国华、胡义（2009）认为，风险投资家和创业者的合作都是为了获得最大价值，所以两者之间建立稳定的匹配关系非常重要。他们根据自身的评价标准选择与对方建立匹配关系的理论基础，建立了风险投资家和创业者之间的双边匹配模型，并加以应用。
（二）双边匹配理论在企业并购中的应用
目前，双边匹配理论在企业并购中应用的研究比较零散，大都是从企业并购活动的某一个方面来研究的，如战略匹配、资源匹配等单个方面的研究，缺乏一个系统性的研究。
刘仲英等（2004）研究了企业并购活动中的战略匹配问题，建立了EKMS柔性和环境不确定性的匹配模型。马锐军、张勇（2006）分析了企业并购中人力资源匹配的问题，他认为人力资源的匹配要以人的能力为核心的管理和人力资源能力建设为主要内容。张海珊（2007）将企业并购活动中的资源匹配分为资产匹配和能力匹配，并通过建立BP神经网络模型来判断并购双方总体的匹配性。
（三）双边匹配理论在银行信贷中的应用
双边匹配理论在银行信贷方面应用的研究比较少。文胜（2006） 认为我国银行信贷市场存在着两个有完全不同运行机制的市场——目标客户信贷市场和非目标客户信贷市场。目标客户信贷市场的议价过程可以采用递延接受算法，结果稳定；非目标客户信贷市场如果采用递延接受算法，运行结果不稳定，因此需要设计一个中央化的匹配程序以保证结果的稳定。张继军（2011）通过分析中小企业贷款现状和贷款难的原因及城市商业银行为中小企业贷款的实际案例，认为小银行和中小企业的贷款需求是匹配的。
银行和贷款客户之间的稳定匹配，对于银行来说，可以规避客户的违约风险、减少银行的不良贷款、实现银行的稳健经营；对于贷款客户来说，稳定匹配可以减少贷款客户的搜寻成本、贷款成本，实现企业的持续稳定经营。所以学者们有必要深入的研究双边匹配理论在银行信贷中的应用。
四、结论与启示
通过对目前国内外关于双边匹配研究文献的回顾与综述可以发现，国外学者对双边匹配问题进行了大量探索性的研究，并取得了一系列的研究成果。学者们在研究中明晰并扩展了双边匹配理论的应用背景，探索了匹配的目标和获得稳定匹配结果的算法，并尝试在研究中用双边匹配思想来阐明并解决现实中大量存在的、不同参与主体之间的匹配问题。2012年诺贝尔经济学奖的颁布必然将双边匹配理论的研究和应用推向一个新的阶段。
毋庸置疑，双边匹配理论尚处于发展过程中，还有许多尚待进一步明确的具体问题。另外，国内学者对双边匹配问题的关注和研究还相对较少，研究内容也较为分散。但是，在我国金融领域，有许多市场是研究双边市场理论的天然场所，尤其是在双边市场条件③下运作的银行卡市场。作为一种典型的双边市场，市场需求和供给均呈现独特性，发卡机构必须围绕双边用户的联合需求提品和服务、必须协调双边用户的需求以达到均衡。因此，加强对发卡机构、特约商户、持卡人、银行卡组织等多方匹配机制的研究，能从根本上提高银行卡市场的匹配效率，这对于竞争不断加剧的银行卡市场④而言，无疑是增强银行卡市场竞争力的有效途径。
注：
①匹配研究是从“个人理性匹配”概念入手的。如果每个人对其派遣结果是可接受的，这就是个人理性匹配。
②有效配置意味着在资源和技术条件限制下尽可能满足人类需要的运行状况。帕累托最优状态表示，当事物的状态在给定的约束条件内时，通过重新改变这种事物的状态使之满足可用的约束条件，已经不可能使任何一个人的处境按照自己的观点来说变得更好。
③罗切特和蒂罗勒（Rochet和Tirole，2004）将双边市场定义为，通过一个或几个平台能够使最终用户相互作用，并通过合理地向每一方收费而试图把双方维持在平台上的市场。双边市场涉及到两种类型截然不同的用户，每一类用户通过共有平台与另一类用户相互作用而获得价值。
④截至2011年底，银行卡发卡量累计超过28.5亿张，同比增长18%。银行卡跨行交易全年超过16万亿元、104亿笔，同比分别增长44%、24%。其中，POS跨行交易13.4万亿元，同比增长47%；ATM跨行交易2.3万亿元，同比增长37%。刷卡消费额超过16万亿元，同比增长超过50%，占社会消费品零售总额的比重预计超过40%，比2010年提高约6个百分点——中国行业研究网。
参考文献：
[1]Gale，Shapley.1962.College Admissions and the Stability of Marriage [J].American Mathematical Monthly， 69，（1）.
[2]Roth，mon and Conflicting Interests in Two-sided Matching Markets[J].European Economic Review，27，（1）.
[3]Teo C.P，Sethuraman.J，Tan.W.P.2001.Gale-Shapley stable marriage Problem revisited：issues and applications[J].Management Seienee，47（9）.
[4]李坤明. 基于双边匹配理论的中国高考录取机制研究[D].华南理工大学硕士论文，2010.
[5]张成. 双边匹配理论及其在我国大学应届毕业生劳动力市场的应用[D].华南理工大学硕士论文，2010.
[6]赵希男，温馨，贾建锋. 组织中人岗匹配的测算模型及应用[J].工业工程与管理，2008，（2）.
[7]徐晓辉，陈剑. 关于产品电子商务匹配度的研究[J].南开管理评论，2000，（4）.
[8]张振华，贾淑娟，曲衍国. 基于稳定匹配的电子中介匹配研究[J].控制与决策，2008，（4）.
[9]李晓慧. 基于优先级的双边匹配方法在B2B电子商务中的应用研究[D].西安电子科技大学硕士论文，2010.
[10]张海珊. 战略并购双方的匹配性研究[D].北京交通大学博士论文，2007.
