類似度で行と列をソートするアルゴリズム

Question

連続した行と列の間の変更回数を最小限に抑えるために、バイナリデータを含む行列の行と列を並べ替える方法について説明したa spreadsheetになりました。例えば

が始まる：

spreadsheedのタブで説明15の手動手順は、次の表が得られた後

：

私がしたいです知っている：

1. このアルゴリズムまたはメソッドの共通名は何ですか？
2. 大きなテーブルに適用する方法（2^nがオーバーフローする...）
3. Levenshtein distanceなどの非バイナリデータに一般化するにはどうすればよいですか？
4. コードへのリンク（エクセルVBA、Pythonの、...）すでにこれを実装する（そうでない場合、私はそれを書くよ...）

感謝がある場合は！

Answer 1

あなたはベクトルL = [1, 1, 0, ... 1]により各行を表し、そして次いでL0とL1間で異なる対応する位置における要素の数で二行d(L0, L1)間の距離を定義することができます。これはバイナリHamming distanceとして知られています。非バイナリデータがある場合は、距離の定義を拡張するだけで、はい、Levenshtein距離がオプションになります。

距離が明確に定義されていれば、残りの問題は連続する行の間隔を最小限に抑えることです。これはちょうどNP-hard（http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/EKP85.pdf）であることが知られているTraveling salesman problemです。

直接解答（すべての順列を参照）はO（n！）ですが、たとえばHeld–Karp_algorithmのような動的プログラミングを使うと簡単に行うことができます。 Nearest_neighbour_algorithmのような近似アルゴリズムもあり、最適ではない解を迅速に計算します。

最後に、実装のために、 "travel salesman excel/python"を簡単にgoogleして、多くのチュートリアルと例を見つけることができます。