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

Question

问题:

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

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

Answer 1

即使您将此问题视为类似于旅行商问题 (TSP)，我也相信汉明距离将遵循三角不等式 (Hamming(A,B) + Hamming(B,C) ≤ Hamming(A,C) ))，所以你实际上只处理 ∆TSP(公制旅行商问题)，有许多算法可以给出理想结果的良好近似值。特别是 Christofides algorithm将始终为您提供最多 1.5 倍最小可能长度的路径。