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

Question

我必须根据彼此之间的相似性（由系数表示）对元素序列进行重新排序，以使每个元素与其每个邻居最相似。我必须找到算法而不是代码。

示例，为下面的每对元素计算10个元素和相似系数：

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

我尝试过的：

1. 找到系数最高的一对。在示例中：T3（左端）和T5（右端）为0.98
2. 找到左端和其余元素之间的最大系数
3. 找到右端和剩余元素之间的最大系数
4. 取最大值在2.和3之间。
5. 如果maximum是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-相似系数）视为“距离”。