n维匹配算法 [英] n-dimensional matching algorithm

问题描述

寻找一些建议在这里。有谁知道一个好地方开始寻找到在n维空间匹配算法。例如，任何约会站点那里必须使用某种算法来匹配2人。我读的是我们可以映射在一个多维数组中配点方式为每特性的人的特征。一旦我们有一个人所有（可用）的特点，我们可以重新present此人在n维数组中的一个点。然后，以配合2人会很简单，如发现该n维数组2点之间的最短距离。有没有人有在实施这类算法的任何参考？什么是在写这几样东西最好的语言？

Looking for some advice here. Does anyone know a good place to start looking into matching algorithm in a n-dimensional space. For example, any dating site out there must be using some sort of algorithm to match 2 people. What I have read is that we can map characteristics of a person in a n-dimensional array with a point system for each characteristic. Once we have all (available) characteristics of a person, we can represent this person in a point within a n-dimensional array. Then, to match 2 person would be as simple as finding the shortest distance between 2 point in this n-dim array. Does anyone has any reference in implementation of these kind of algorithm? What's the best language to write these kind of stuff in?

推荐答案

如果你想找到最匹配的一个人，宾利和放大器; Shamos发表了多维分而治之的方法：分而治之在O（N日志N）时间：的分而治之在第八次年度ACM研讨会论文集多维空间在计算1976年的理论如果不能得到一份拷贝的这个也可能会有帮助。

If you want to find the closest match for one person, Bentley & Shamos published a multi-dimensional divide-and-conquer method: Divide-and-conquer in O(N log N) time: Divide-and-conquer in multidimensional space in Proceedings of the eighth annual ACM symposium on Theory of computing 1976. If you can't get a copy this may also be helpful.

不过，对于您的示例应用程序真正找到最近的邻居似乎并不成为最大的问题 - 很多棘手的是测绘投入的尺寸。例如，如果一个维度是喜欢动物，你给别人谁喜欢狗和放什么样的价值;猫，但不能站在马？怎么样的人谁爱马，狗想都行，就是讨厌猫，是模棱两可的金鱼？

However for your example application actually finding the nearest neighbour doesn't seem to be the biggest problem - much trickier is mapping inputs into dimensions. For example if one dimension is "likes animals", what value do you give to someone who likes dogs & cats but can't stand horses? What about someone who loves horses, thinks dogs are OK, is annoyed by cats and is ambivalent about goldfish?

这篇关于n维匹配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！