algorithm - 对字典进行排序以最大化相邻单词之间的共同字母

Question

这是我之前的问题的更具体、更容易表达的形式。

从字典中获取具有常见字母长度的单词列表。
如何重新排序此列表以保持相邻单词之间尽可能多的共同字母？

示例1:

AGNI, CIVA, DEVA, DEWA, KAMA, RAMA, SIVA, VAYU
reorders to:  
AGNI, CIVA, SIVA, DEVA, DEWA, KAMA, RAMA, VAYU  

示例2:

DEVI, KALI, SHRI, VACH
reorders to:
DEVI, SHRI, KALI, VACH

最简单的算法似乎是:选择任何东西，然后搜索最短距离？
但是，DEVI->KALI(1 个公共(public))相当于 DEVI->SHRI(1 个公共(public))
选择第一个匹配将导致整个列表中的常见对更少(4 比 5)。

这看起来应该比full TSP简单吧？

Answer 1

您想要做的是计算完整加权图中的最短哈密顿路径，其中每个单词都是一个顶点，每条边的权重是这两个单词之间不同的字母数。

对于您的示例，图表的边权重如下:

     DEVI KALI SHRI VACH
DEVI   X    3    3    4
KALI   3    X    3    3
SHRI   3    3    X    4
VACH   4    3    4    X

然后，只需选择您最喜欢的 TSP solving algorithm 即可。 ，就可以开始了。