通过相似性对行和列进行排序的算法

Question

我遇到了一个电子表格,该电子表格解释了一种方法,用于对包含二进制数据的矩阵的行和列进行排序,以便最小化连续行和列之间的更改次数.

例如,从以下开始:

在传感器选项卡中描述的15个手动步骤之后,获得下表:

我想知道:

1. 这种算法或方法的通用名称是什么？
2. 如何将它应用于更大的表(2 ^ n将溢出...)
3. 如何将它推广到非二进制数据,例如使用Levenshtein距离？
4. 如果有任何代码链接(Excel VBA,Python,...)已经实现了这个(否则我会写它...)

谢谢 !

Answer 1

您可以用向量 表示每一行L = [1, 1, 0, ... 1]，然后通过和d(L0, L1)之间对应位置的元素数量来定义两条线之间的距离。这称为二进制汉明距离。如果您有非二进制数据，您只需扩展距离的定义，是的，编辑距离将是一个选项。L0L1

\n\n

一旦明确定义了距离，剩下的问题就是最小化连续行之间的距离。这正是旅行商问题，已知为 NP 困难问题（http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/EKP85.pdf）。

\n\n

直接解决方案（访问所有排列）是 O(n!)，但您可以通过使用动态规划轻松地做得更好，例如Held\xe2\x80\x93Karp_algorithm。还有近似算法，例如可以快速计算非最优解的Nearest_neighbour_algorithm 。

\n\n

最后，对于实现，您可以轻松地谷歌“旅行推销员excel/python”并找到许多教程和示例。

\n