0

我有一个动物数据库，每个动物都有许多从 0 到 1 的属性——这些属性是大小、速度、毛羽等。给定一组输入属性，以及每种属性的权重，我需要找到一组动物中“最接近”的匹配。是否有一种算法可以在比 O(n) 时间更好的时间内完成此任务？

我特别想做的是通过将它们与已经存在的动物相匹配，为游戏中的遗传算法产生的“动物”找到合适的纹理。我所说的“最接近”是指属性差异的加权和最小的动物。数据库和权重在应用程序启动时是已知的，因此可以投入大量时间来准备数据。

我已经找到了给定用户偏好的字符串匹配和产品匹配算法，但要么我没有找到我正在寻找的东西，要么我不明白如何将这些概念重新应用到我的困境中。也许图论世界有一些东西可以帮助我？

任何帮助将不胜感激！

4

4 回答 4

2

您可以将这些项目视为高维空间中的点，并将它们全部插入到 BSP 树中，例如kd 树。要使用属性权重，您只需将它们乘以相应的坐标：(w1*x, w2*y, ...)

准备：（来自维基百科，python代码）

def kdtree(point_list, depth=0):

    if not point_list:
        return None

    # Select axis based on depth so that axis cycles through all valid values
    k = len(point_list[0]) # assumes all points have the same dimension
    axis = depth % k

    # Sort point list and choose median as pivot element
    point_list.sort(key=lambda point: point[axis])
    median = len(point_list) // 2 # choose median

    # Create node and construct subtrees
    node = Node()
    node.location = point_list[median]
    node.left_child = kdtree(point_list[:median], depth + 1)
    node.right_child = kdtree(point_list[median + 1:], depth + 1)
    return node

搜索：（来自gist，基于维基百科算法）

# method of the Node-class

def closest_point(self, target, point, best=None):
    if target is None:
        return best

    if best is None:
        best = target

    # consider the current node
    if distance(target, point) < distance(best, point):
        best = target

    # search the near branch
    best = self.child_near(point).closest_point(point, best)

    # search the away branch - maybe
    if self.distance_axis(point) < distance(best, point):
        best = self.child_away(point).closest_point(target, point, best)

    return best

阅读更多：

于 2012-11-01T23:56:49.983 回答
1

您可能会将其视为最大权重匹配问题，但找到最小此类匹配的复杂度的下限将比O(n). 想多了就好O(n^3)。

如果我不得不尝试解决这个问题，我会考虑根据权重成对匹配相同类型的属性（即，在输入的“hairy”属性和数据集中所有其他“hairy”属性之间创建加权边缘，使用输入权重的某些因素以及查询“hairy”值与匹配的“hairy”值之间的差异的倒数）。此时，您可以合并所有通往特定动物的边缘，并将边缘权重的总和作为匹配分数。

例如：

Monkey:  
A1: 0.5 
B1: 0.25
C1: 1.0

Giraffe:
A2: 0.2
C2: 0.9
D2: 0.1

Input query:
Ai: 0.4 with weight 0.8
Di: 0.2 with weight 0.25

所以我们创建了下图：

Ai --> A1 with weight 0.8 * 1/abs(0.5-0.4) (i.e., 8.0)
Ai --> A2 with weight 0.8 * 1/abs(0.2-0.4) (i.e., 4.0)

Di --> D2 with weight 0.25 * 1/abs(0.1-0.2) (i.e., 2.5)

然后我们折叠同一目标动物中具有属性的所有边，以获得我们的候选者：

Monkey: 8.0
Giraffe: 4.0 + 2.5

它不漂亮，而且比O(n)（可能是您尝试匹配的属性数量）更差，但它可能是开始优化更好解决方案的起点。mm

于 2012-11-01T23:21:52.500 回答
1

如果您可以花时间整理数据，则可以按分数对动物进行排序（O(nlogn)及时但只完成一次），然后对分数应用二分搜索以及时找到最接近的匹配O(logn)项。

如果您从 SQL 数据库中获取动物列表，则可以通过在查询中使用ASCorDESC关键字来获取排序列表。

于 2012-11-01T22:47:13.150 回答
0

如何找到线性反转的数量？因此，您将拥有 2 只动物的线性数据集，并且您想通过对它们进行排序来了解它们的相似或不同之处。复杂性与归并排序相同。对于“n”只动物，您将计算 nC2 倒位。

于 2012-11-01T23:26:50.680 回答