EB环境下的一个匹配模型及其算法研究.pdf

vol 第30卷第5期 电子科技大学学报 30No5 2001年10月 J叫m出ofUESTof China oct2001 EB环境下的一个匹配模型及其算法研究 王新庄4 (成都理工大学电子商务系成都610051) 【摘要】描述了基于相同属性的元素两两重复匹配在实际应用中的具体意义，提出了EB环境下基于相同 属性的元素两两重复匹配问题的基本概念，讨论了重复匹配的各种情况和最大重复匹配、最小重复匹配以厦 平凡匹配的定义和判定准则；分析了最大重复匹配(最小重复匹配)的精确求解算法，得出在m个元素、n种属 性的情况下，求解两两最小(最大)重复匹配算法的时间复杂性为晶“的结论；最后提出一十改进算法，其时间 复杂性为D(c)，改进后的算法还适宜于手工作业。 关键词电子商务； 最大重复匹配； 最小重复匹配； 算法： 算法分析 6 中图分类号TP301 1问题的提出 在电子商务(髓)环境下，往往要根据元素属性对元素实行比较或者匹配”4】，例如在商品比较 网站中，要根据商品的名称、规格、产地等属性对商品进行两两比较：在婚介交友模型中，要按 相同的兴趣爱好对会员进行两两匹配；再如具有多技能的人员在多项目环境下的人力资源的使用， 则要根据项目需求和人员的技能进行组合分配，这些问题都要涉及到元素的匹配，而两两匹配则 是这些匹配中的一种最为简单的形式，也是更为复杂匹配的基础。在网络计算环境下匹配方法的 优劣将对采集数据的利用效率产生极大的影响”一。 在讨论的问题中，设有m个元素的集合A=(吼，如，…，n。)∽1)，H种属性的集合正(^，如，…， 属性实现两两匹配，匹配的规则是：若元素q、口都具有属性“，则口。、口，两元素就可以按属性幞现 一次匹配，此后q、d，不能按属性^再与其他元素实现匹配。由于国、口，可能具有多个相同的属性， 故岛、d，之间可以按这些相同属性构成多次匹配，即允许卧d，之间重复匹配。对A中所有的元素两 两间都按上述规则将所有属性都匹配完毕，就构成了A上关于哟一个匹配方案。 假设属性^在所有元素的属性子集中共出现了q次，那么在A中元素关于属性‘的两两匹配总次 数ill“t，2)是一个常数。例如交友模型中，有7个人(元素)具有打乒乓球的爱好(属性)，则可以构成 c。，c：，…，c．次，则两两总匹配次数c=1 int(c／2)也是一个常数。 由于多个元素都具有同一属性t，这多个元素间关于^的两两匹配方式具有多种组合，从m个元 素中取2个元素的组合数记为＆c(m，2)。由于两两匹配时组合方式的不同，故元素间的两两重复匹 配次数也不相同。设在A上已经求得关于丁中属性的一个两两重复匹配方案F，该方案在s个二元组 上的重复匹配次数依次为≈，，岛，…，t(岛≥o)，则∑．女．=c，令4=y，砰，则可以给出匹配的三种 情况的定义如下： 1)最大重复匹配：若在A关于哟所有匹配方案中，方案F的4值最大，则方案蹴是一个最大 重复匹配，最大重复匹配也就是要将c个两两匹配尽可能地分配到相同的元组上去； 2)最小重复匹配：若在A关于珀g所有匹配方案中，方案F的4值最小，则方案蹴是一个最小 重复匹配，最小重复匹配也就是要将阶两两匹配尽可能地分配到不同的元组上去。值得注意的是， 最大(小)重复匹配的解并不是唯一的； 2001年4月23日收穑 ·男45岁大学副教授 万方数据 534 电子科技大学学报 第30卷 3)平凡匹配：若方案瑚d值介于最大重复匹配和最小重复匹配的4值之间，则方案蹴是一 个平凡匹配。由于平凡匹配的随意性，讨论的意义不大。 例会员匹配问题。设有4个会员(元素M=(Ⅱ，，4：，吗，口。)，5种兴趣(属性)的集合仁(f1，屯，b， b，f。，f，)。则A中的最大重复匹配、最