algorithm - 如何根据相似系数优化元素顺序？

Question

我必须根据彼此之间的相似性(用系数表示)对元素序列重新排序，以便每个元素与其相邻元素尽可能相似。我必须找到一种算法而不是代码。

具有 10 个元素和为以下每对元素计算相似系数的示例:

excel 文件可以在这里找到:https://1drv.ms/x/s!AtmZN4-kjgrPms99fqgaDwAS_F4uYw

我尝试过的:

1. 找到系数最高的一对。在示例中:T3(左端)和 T5(右端)为 0.98
2. 找到左端和剩余元素之间的最大系数
3. 找到右端和剩余元素之间的最大系数
4. 取 2. 和 3. 之间的最大值。
5. 如果最大值为 2，则在左侧添加对应于左端最大系数的元素。否则，在右侧添加右端最大系数对应的元素
6. 重复第 2 - 6 点，直到没有元素为止。

结果如下:

结果还不错。我看到的缺点之一是 0.99>0.98 与 0.99>0.01 的考虑方式相同。

我想到的第二个选项是最大化所有邻居之间的系数之和，但真的不知道从哪里开始。特别是当元素明显多于 10 个时。此外，它可能会导致更“扁平”的顺序，虽然总体上具有更好的相似性，但一些极其相似的元素可以彼此远离放置。

作为对此类问题的新手，我很确定这应该是现有解决方案的一个相当标准的问题。你能指出那些吗？

谢谢!

Answer 1

经过研究，我发现我的问题可以看作是“旅行商问题”(TSP)。更多信息:https://en.wikipedia.org/wiki/Travelling_salesman_problem

要应用它，您可以在我的示例中将“元素”视为 TSP 中的“城市”，并将(1-相似度系数)视为“距离”。