11

問題：

私はN（〜100k-1m）の文字列をそれぞれD（例：2000）文字の長さと低いアルファベット（例：3つの可能な文字）で持っています。これらの文字列を並べ替えて、隣接する文字列間の変更ができるだけ少なくなるようにします (たとえば、ハミング距離が低くなるようにします)。解決策は可能な限り最善である必要はありませんが、近いほど良いです。

例

N=4
D=5
//initial strings
1. aaacb
2. bacba
3. acacb
4. cbcba

//sorted so that hamming distance between adjacent strings is low
1. aaacb
3. acacb (Hamming distance 1->3 = 1)
4. cbcba (Hamming distance 3->4 = 4)
2. bacba (Hamming distance 4->2 = 2)

問題についての考え

これは些細な問題ではないと感じています。各文字列を節点、他の文字列までの距離を辺と考えると、巡回セールスマン問題を見ていることになります。文字列の数が多いということは、すべてのペアごとの距離を事前に計算することは潜在的に不可能であることを意味します。この問題をカナダ旅行者問題のようなものに変えると思います。

現時点での私の解決策は、VPツリーを使用して、問題に対する貪欲な最近傍タイプの解決策を見つけることでした

curr_string = a randomly chosen string from full set
while(tree not empty)
    found_string = find nearest string in tree
    tree.remove(found_string)
    sorted_list.add(curr_string)
    curr_string = found_string

しかし、最初の結果は悪いようです。文字列をハッシュして、より類似したものを近づけることも別のオプションかもしれませんが、これがどの程度優れたソリューションを提供するか、またはこのサイズのデータ​​にどれだけうまくスケーリングするかについてはほとんど知りません.

4

2 に答える 2

2

この問題を巡回セールスマン問題 (TSP) に似ていると考えても、ハミング距離は三角形の不等式 (Hamming(A,B) + Hamming(B,C) ≤ Hamming(A,C)) に従うと思います。そのため、理想的な結果で適切な近似を与えるアルゴリズムが多数ある ∆TSP (メトリック巡回セールスマン問題) のみを実際に扱っています。特に、Christofides アルゴリズムは、可能な限り最小の長さの最大 1.5 倍のパスを常に提供します。

于 2012-01-05T07:19:06.297 に答える
1

はい、これは巡回セールスマンの問題ですが、 TSP ソース コード ライブラリに含まれる多数のプログラムのいずれかが 、プラグイン メトリックを使用して 100 万点を達成できるかどうかはわかりません 。

考えられる 2 段階のアプローチ:

1)最近隣検索で 1M ポイントを 50 個のクラスターに分割し ます。50 のクラスター センターで TSP を実行します。

2) すべての 1M - 50 ポイントを 2 つの最も近いセンターの間に置きます。1M / 50 の各文字列で TSP を実行します。ここで、「50」は 100 または 1000 の可能性があります。1000 が大きすぎる場合は、再帰します。1000 をそれぞれ約 30 個の 30 個のクラスターに分割します。

K-means は 1M ポイントをクラスター化できますが、プラグイン メトリックを使用した高速な実装については知りません。ただし、 scikit-learn クラスタリングを参照してください

|centre - all other| を最小化する N ポイントのセントロイドを見つけるには、たとえば sqrt(N) のランダム サンプルの最良のものを取得するだけで O(N^2) を打ち負かすことができます。これで十分です。（またはグーグル/高速近似重心について別の質問をする）。

最初にデータを密にパックして、フロー全体でメモリ アクセスを節約します。この場合、abc を 00 01 10 としてエンコードします (各ペア間のハミング距離 = 1): 2000 x 2 ビット = 500 バイト。Fwiw、min Hammingdist(4k ビット、10k x 4k) を見つけるには、私の Mac ppc で ~ 40 ミリ秒かかります。

于 2012-01-05T09:53:31.213 に答える