9

エントリ 0、1、2 を持つ長さ 12 のベクトルの空間を検索しています。たとえば、そのようなベクトルの 1 つは
001122001122 です。約 1000 個の良いベクトルと約 1000 個の悪いベクトルがあります。悪いベクトルごとに、最も近い良いベクトルを見つける必要があります。2 つのベクトル間の距離は、一致しない座標の数です。優れたベクトルは特にうまく配置されているわけではなく、それらが「優れている」理由はここでは役に立たないようです。私の主な優先事項は、アルゴリズムが高速であることです。

単純な徹底的な検索を行うと、約 1000*1000 の距離を計算する必要があります。かなり頭が固いようです。

最初に適切なベクトルを使用して Dijkstra のアルゴリズムを適用すると、空間内のすべてのベクトルに対して最も近いベクトルと最小距離を計算できるため、悪いベクトルごとに簡単なルックアップが必要になります。しかし、空間には 3^12 = 531,441 個のベクトルがあるため、事前計算は 50 万回の距離計算になります。あまり節約できません。

より良い方法を考えるのを手伝ってもらえますか?

編集: 人々が彼らを「良い」ものにする理由を真剣に尋ねたので: 各ベクトルは、立方体の 3D 配置の 2D 画像である 6 つの正三角形の六角形の図の説明を表します (一般化された Q-bert を考えてください)。正三角形は、立方体 (45-45-90) の面の半分であり、遠近法に傾いています。座標のうち 6 つは三角形の性質 (知覚される床、左の壁、右の壁) を記述し、6 つの座標は辺の性質 (知覚される連続性、知覚される 2 種類の不連続性) を記述します。1000 個の適切なベクトルは、立方体を遠近法で見たときに確認できる六角形を表すものです。検索の理由は、三角形でいっぱいの 16 進マップにローカル補正を適用することです...

4

5 に答える 5

4

物事を大局的に保ち、不要なものを最適化していないことを確認するために、最適化なしのブルートフォースアプローチは私のマシンで12秒かかります.

Mathematica のコード:

bad = Table[RandomInteger[5, 12], {1000}];
good = Table[RandomInteger[2, 12], {1000}];
distance[a_, b_] := Total[Sign@Abs[a - b]];

bestMatch = #[[2]] & /@ 
   Position[
    Table[Ordering@
      Table[distance[good[[j]], bad[[i]]], {j, Length@good}], {i, 
      Length@bad}], 1] // Timing

ご想像のとおり、Time は O(n^2) の法則に従います。

代替テキスト

于 2010-11-19T03:28:28.507 に答える
1

これは、スペルチェッカーがしなければならないこととよく似ています。秘訣は、一般に、 try を悪用することです。

あなたができる最も基本的なことは、適切なベクトルに対してトライを構築し、フラッドフィルを実行して、不一致の少ないブランチを優先することです。これは、近くにベクトルがある場合は非常に高速であり、最も近いベクトルが非常に遠くにある場合は力ずくで退化します。悪くない。

しかし、私はあなたがもっとうまくやれると思います。同じ接頭辞を共有する悪いベクトルは、同じ初期分岐作業を行うので、それも共有しようとすることができます。そのため、悪いベクトルに対してもトライを構築し、それらをすべて一度に実行します。

アルゴリズムとコードの両方が私の頭の上から外れているため、これが正しいという保証はありません。

var goodTrie = new Trie(goodVectors)
var badTrie = new Trie(badVectors)
var result = new Map<Vector, Vector>()
var pq = new PriorityQueue(x => x.error)
pq.add(new {good: goodTrie, bad: badTrie, error: 0})
while pq.Count > 0
  var g,b,e = q.Dequeue()
  if b.Count == 0: 
      //all leafs of this path have been removed
      continue
  if b.IsLeaf:
      //we have found a mapping with minimum error for this bad item
      result[b.Item] = g.Item
      badTrie.remove(b) //prevent redundant results
  else:
      //We are zipping down the tries. Branch to all possibilities.
      q.EnqueueAll(from i in {0,1,2}
                   from j in {0,1,2}
                   select new {good: g[i], bad: b[j], error: e + i==j ? 0 : 1})

return result

最終的な最適化は、ベクトルを並べ替えて、悪いベクトル間で一致度の高い位置が最初に来て、より多くの作業を分担するようにすることです。

于 2010-11-19T04:07:54.733 に答える
1

3^12 はそれほど大きな検索空間ではありません。速度が重要で、アルゴリズムの汎用性が重要でない場合は、各ベクトルを 0..531440 の範囲の int にマップし、それを「最も近い適切なベクトル」の事前計算済みテーブルへのインデックスとして使用できます。

そのテーブルの各エントリに 32 ビット ワード (これで十分です) を与えると、ほぼ瞬時の「計算」と引き換えに、テーブルに約 2 MB が必要になります。

編集:これは質問が示唆する事前計算と大差ありませんが、私のポイントは、アプリケーションによっては、特にアプリケーションが実行される前にすべての事前計算を行う場合、必ずしもそのようにすることに問題があるとは限らないということです。

于 2010-11-19T14:27:42.403 に答える
0

ベクトルのパック表現を想定すると、1 つの距離計算 (1 つの適切なベクトルと 1 つの悪いベクトルを比較して距離を算出する) は、約 20 クロック サイクル以下で完了できます。したがって、このような 100 万回の距離計算は、2,000 万サイクルまたは (2 GHz の CPU を想定) 0.01 秒で実行できます。これらの数字は役に立ちますか?

PS:- 20 サイクルは保守的な過大評価です。

于 2010-11-19T17:26:38.053 に答える
0

私の計算幾何学は非常に大雑把ですが、次のことができるはずです。

  1. 適切なベクトルのセットのボロノイ図を計算します。
  2. ダイアグラムのセルのBSP ツリーを計算します。

ボロノイ図は、そのベクトルに最も近いすべての点を含む適切なベクトルごとに 12 次元の凸包を提供します。

BSP ツリーを使用すると、ベクトルがどのセル内にあるか、したがってどのベクトルに最も近いかをすばやく判断できます。

編集:ユークリッド距離の代わりにハミング距離を使用していることに気付きました。これがその制約に適合するようにどのように適応できるかはわかりません。ごめん。

于 2010-11-19T03:16:41.970 に答える