「ベクトル」のセットがあり、「類似性」に基づいて並べ替える必要があります。
次のように: ベクトル {1,0,0} {1,1,0} {0,1,0} {1,0,1} は非常に似ており、最終的には互いに近いはずですが、ベクトル {1 , 0, 0} {8, 0, 0} {0, 5, 0} - ではありません。
A と B の間のメトリックは max(abs(A[i]-B[i])) ですが、相対的な比較に基づいて物事を並べ替えることができるアルゴリズムはどのようなものでしょうか?
upd: 入力: N 個のベクトルの配列 出力: N 個のベクトル
の配列、ここでインデックス ベクトル (arr[i] arr[i+1] など) で最も近いものは 'similar' = arr[i] と arr[i+ の間のメトリック1] は、任意の i、j に対して可能な限り低くなります。
metric - ベクトル成分の最大差
upd2: 今のように、@jogojapan は正しかったようです。ベクトルをクラスター化する必要があり、その後、それらをいくつかの線形順序でグループごとに出力します。
これは、最大ノルム (別名 sup ノルムまたは l-無限ノルム)によって誘導される距離です。並べ替えが順序付けを意味する場合、距離は線形順序付けを作成するのに十分ではありません。
並べ替えは、本質的に 1 次元の問題です。ここで説明していることは、加重グラフのように聞こえますが、目標が何であるかは明確ではありません. 既知のベクトルに「最も近い」ベクトルを識別しようとしている場合、ハミング距離などの情報理論の概念が役立つこともあります。
まあ、明白なアプローチは、（私見の悪い名前の）「階層的クラスタリング」であり、これらのクラスターを常に最小距離でマージします。そこにメトリックをプラグインできます。ほとんどの実装は O(n^3) で行われるため、大規模なデータセットには役立ちません。さらに、読みにくい巨大な樹形図が得られます。
OPTICS を試してみてください。ウィキペディアで調べてください。実際にはポイントをソートするため、ニーズを十分に満たす可能性があります。あるクラスターから別のクラスターに移動し、実際には階層型 (「入れ子」のような) クラスター化を生成できます。適切な実装は、インデックス構造を使用せずに O(n^2) で実行し、インデックス アクセラレーションを使用して O(n log n) で実行する必要があります。
どのソート アルゴリズムでも、必要な結果が得られます。
問題は、ベクトルをどのように比較するかです。それらを大きさで比較したいだけですか？または、他の何か？