多类别复合资源的空间匹配  

Spatial matching on multi-type resource

作　　者：蔡华林[1] 陈刚[1] 陈珂[1] 

机构地区：[1]浙江大学计算机科学与技术系,浙江杭州310027

出　　处：《浙江大学学报（工学版）》2015年第1期69-78,共10页Journal of Zhejiang University：Engineering Science

基　　金：国家"863"高技术研究发展计划资助项目(SS2013AA040601)

摘　　要：针对现有的空间匹配(SPM)问题中无法适用于多类别资源的不足,提出并解决了多类别复合资源的空间匹配问题.假设度量空间下有资源提供者和用户2个对象集合,资源提供者能够提供多类别的资源,并且受限于有限的容量,用户对各种资源有不同数量需求.多类别复合资源的空间匹配将资源提供者与资源需求者进行匹配,使资源利用效益最大化,同时要求这个匹配是稳定匹配,稳定匹配是指每个用户优先与距其最近的资源提供者匹配,且所需资源未被比该用户更近的其他用户所耗尽.提出利用网络流、最近邻等方法来解决该问题的有效算法.通过大量的实验验证了这些算法的正确性和有效性,对这些算法以及特殊情形下的已有解决方法进行比较.A new problem called generalized spatial matching（GSPM）was proposed and solved aiming at the existing spatial matching（SPM）problem that cannot be applied to the multi-type resource.Assume there are two sets of objects in an arbitrary metric space.One set of objects indicate services providers and each of them provides several services constrained by a finite capacity.The other set of objects indicate the customers needing different quantity of service.GSPM assigns each providers capacity to the customers with the services it provides,aiming at maximizing the resource utilizing.The assignment is made stable which means that we assign each customer to its nearest provider who can provide at least one of the needed services,among all the providers whose capacities have not been exhausted in serving other closer customers.Several algorithms were developed to settle the problem.Our algorithms were verified with extensive experiments.Results showed that the proposed solutions efficiently solved the problem.

关 键 词：网络流 最近邻 空间匹配(SPM) 稳定婚姻问题 空间数据库 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]