将最相似的元素组合在一起

Question

我有一个二维的int数组,例如:

int [][] board=
{
{23,17,3,29,12,10},
{17,4,11,12,10,19},
{32,33,25,25,28,35},
{27,29,24,25,23,37},
{29,40,34,26,24,39},
{23,37,29,36,31,3}
}

我根本不想改变这个数组的列; 但是,我想交换行,以便将最相似的行组合在一起.在这种情况下类似意味着大多数相等的元素.

编辑:类似的行意味着,如果一行有1,2,3,4,5,6而另一行有1,2,3,4,9,10它们有4个相似之处.

最好的方法是什么？

注意:我在数组中拥有的行数大约为100,每行中的元素数量最多为10,因此复杂性与指出的一样重要!

Answer 1

这个问题减少了旅行商问题.如果您将每一行视为一个城市,然后定义一个距离函数来计算两行之间的距离.问题是如何对行进行排序以使距离最小化.这个问题是NP-Complete,并且在100行的合理时间内无法解决.对此的暴力解决方案需要O(N!)计算.有一些启发式算法(接近最佳答案的算法)将在合理的时间内解决这个问题.

旅游推销员问题(维基百科)

一个例子是使用贪心算法.随机选择一行,这是第1行.然后选择最接近第1行的行作为第2行.然后选择最接近第2行的行作为第3行.运行直到选择所有行.这不是一个非常理想的解决方案.