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

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)

关于这个问题的想法

我有一种不好的感觉,这是一个非常重要的问题.如果我们将每个字符串视为一个节点并将其他字符串的距离视为边缘,那么我们就会看到一个旅行商问题.大量的字符串意味着预先计算所有成对距离可能是不可行的,我认为将问题转化为更像加拿大旅行者问题.

目前我的解决方案是使用VP树来找到问题的贪婪最近邻类型解决方案

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) \xe2\x89\xa4 Hamming(A ,C))，所以你实际上只是在处理 \xe2\x88\x86T​​SP （度量旅行商问题），对此有许多算法可以在理想结果下给出良好的近似值。特别是，Christofides 算法始终会为您提供最多 1.5 倍最小可能长度的路径。

\n