2

这旨在成为我之前问题的更具体、更容易表达的形式。

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

示例 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 common) 等价于 DEVI->SHRI (1 common)
选择第一个匹配项会导致整个列表中的常见对更少（4 对 5）。

这似乎应该比完整的 TSP 更简单？

4

5 回答 5

3

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

对于您的示例，该图的边权重如下：

     德维·卡利·施里·瓦赫
德维 X 3 3 4
卡利 3 X 3 3
SHRI 3 3 X 4
瓦赫 4 3 4 X

然后，只需选择您最喜欢的TSP 求解算法，您就可以开始了。

于 2008-11-28T17:17:01.193 回答
1

我的伪代码：

  • 创建一个节点图，其中每个节点代表一个单词
  • 在所有节点之间创建连接（每个节点都连接到其他每个节点）。每个连接都有一个“值”，即常用字符的数量。
  • 删除“值”为 0 的连接。
  • 通过首选具有最高值的连接来遍历图表。如果您有两个具有相同值的连接，请递归尝试。
  • 将 walk 的输出与此特定结果中单词之间的距离总和一起存储在列表中。如果您可以简单地总结您使用的连接，我不能 100% 确定 ATM。你自己看。
  • 从所有输出中，选择具有最高值的输出。

这个问题可能是 NP 完全问题，这意味着算法的运行时间将随着字典的增长而变得难以忍受。现在，我只看到了一种优化方法：将图形切割成几个较小的图形，在每个图形上运行代码，然后加入列表。结果不会像您尝试每个排列时那样完美，但运行时会更好，最终结果可能“足够好”。

[编辑] 由于该算法不会尝试所有可能的组合，因此很可能会错过完美的结果。甚至有可能陷入局部最大值。比如说，你有一对价值为 7 的货币对，但如果你选择了这对货币，所有其他价值都会下降到 1；如果您不使用这对，大多数其他值将是 2，从而提供更好的整体最终结果。

该算法以完美换取速度。如果尝试每一种可能的组合都需要数年时间，即使使用世界上最快的计算机，您也必须找到某种方法来限制运行时。

如果字典很小，您可以简单地创建每个排列，然后选择最佳结果。如果它们超出一定的界限，你就完蛋了。

另一种解决方案是将两者混合。使用贪心算法找到可能还不错的“岛屿”，然后使用“完整搜索”对小岛屿进行排序。

于 2008-11-26T08:50:25.957 回答
0

您可能想看看BK-Trees，它可以有效地查找具有给定距离的单词。不是一个完整的解决方案，但可能是其中的一个组成部分。

于 2008-11-26T10:15:52.430 回答
0

这个问题有一个名字：n-ary Gray code。由于您使用的是英文字母，因此 n = 26。有关格雷码的 Wikipedia 文章描述了该问题并包含一些示例代码。

于 2008-11-26T11:45:48.927 回答
0

这可以通过递归方法来完成。伪代码：

Start with one of the words, call it w
FindNext(w, l) // l = list of words without w
  Get a list l of the words near to w
  If only one word in list
    Return that word
  Else
    For every word w' in l do FindNext(w', l') //l' = l without w'

您可以添加一些分数来计算常见对并更喜欢“更好”的列表。

于 2008-11-26T08:33:51.403 回答