0

私は動物のデータベースを持っており、それぞれに0から1までの範囲の多くの属性があります。これらの属性は、サイズ、速度、毛羽立ちなどです。属性の入力セットと各タイプの属性の重みを考えると、見つける必要があります。動物のセットの中で「最も近い」一致。O（n）時間よりも長くこれを達成するアルゴリズムはありますか？

私が具体的にやろうとしているのは、ゲーム内の遺伝的アルゴリズムによって生成された「動物」に適したテクスチャを、既存の動物と照合することによって見つけることです。「最も近い」とは、属性の差の加重和が最小である動物を意味します。データベースと重みはアプリケーションの起動時にわかっているため、データの準備に多くの時間を費やすことができます。

ユーザーの好みに応じて文字列照合と製品照合のアルゴリズムを見つけましたが、探しているものが見つからないか、そのような概念をジレンマに再適用する方法がわかりません。おそらく、グラフ理論の世界から私を助けるために何かがありますか？

どんな助けでも大歓迎です！

4

4 に答える 4

2

アイテムを高次元空間のポイントとして扱い、それらすべてをkdツリーなどのBSPツリーに挿入することができます。属性の重みを使用するには、対応する座標を掛けるだけです。(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

検索:(要点から、ウィキペディアのアルゴリズムに基づく）

# 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(nlogn)時間内に、ただし1回だけ実行）、スコアに対して二分探索を適用して、時間内で最も近い一致を見つけることができますO(logn)。

SQLデータベースから動物リストを取得する場合は、クエリでASCまたはDESCキーワードを使用して、並べ替えられたリストを取得できます。

于 2012-11-01T22:47:13.150 に答える
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 に答える
0

線形反転の数を見つけるのはどうですか？したがって、2匹の動物の線形データセットがあり、それらを並べ替えることによって、それらがどれほど類似しているか、または異なっているかを調べたいと思います。複雑さはマージソートの複雑さと同じです。'n'の動物の場合、nC2の反転がカウントされます。

于 2012-11-01T23:26:50.680 に答える