algorithm - 对字符串进行排序，以使相邻字符串之间的汉明距离较小

问题:

我有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)

关于问题的想法

我感到不好，这不是一个小问题。如果我们将每个字符串视为一个节点，并将与其他字符串的距离视为一条边，那么我们正在研究一个旅行商问题。大量的字符串意味着预先计算所有成对距离可能是不可行的，我认为将问题变成更像Canadian Traveller Problem。

目前，我的解决方案是使用VP tree查找该问题的贪婪最近邻居类型解决方案

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

但初步结果似乎不佳。散列字符串以使更相似的字符串更接近可能是另一种选择，但是我对这种解决方案将提供多好的解决方案或将其扩展到这种大小的数据的方法知之甚少。

最佳答案

即使您认为这个问题与旅行商问题(TSP)类似，我相信汉明距离也会遵循三角形不等式(Hamming(A，B)+ Hamming(B，C)≤Hamming(A，C))，因此，您实际上只在处理∆TSP(度量旅行推销员问题)，为此，有许多算法可以给出理想结果的良好近似值。特别是，Christofides algorithm将始终为您提供一条路径，该路径最多为最小可能长度的1.5倍。