algorithm - 在通过顺序保留关系的同时对数组中的符号进行排序的棘手算法

Question

问题

我有多个指定符号关系的组..例如:

[A B C]

[A D E]

[X Y Z]

这些组的意思是(对于第一组)符号 A、B 和 C 彼此相关。 (第二组)符号 A、D、E 相互关联……等等。

鉴于所有这些数据，我需要将所有唯一 符号放入一个一维数组中，其中以某种方式彼此相关的符号将彼此靠近放置。鉴于上面的例子，结果应该是这样的:

[B C A D E X Y Z]

或

[X Y Z D E A B C]

在这个结果数组中，由于符号 A 具有多重关系(即与一组中的 B 和 C 以及另一组中的 D 和 E)，它现在位于这些符号之间，某种程度上保留了关系。

请注意顺序并不重要。结果，X Y Z 可以放在第一个或最后一个，因为这些符号与任何其他符号无关。然而，重要的是相关符号的接近程度。

我需要什么帮助

我需要帮助来确定采用符号关系组的算法，然后使用上述逻辑输出一维数组。我正在努力解决如何做到这一点，因为对于真实数据，关系组中的符号数量可能会有所不同，关系组的数量也没有限制，并且符号可以与任何其他符号有关系。

进一步的例子

为了进一步说明我的困境的棘手之处，如果您在上面的示例中添加另一个关系组。比方说:

[C Z]

现在的结果应该是这样的:

[X Y Z C B A D E]

请注意，符号 Z 和 C 现在靠得更近了，因为附加数据加强了它们之间的关系。所有以前的关系也仍然保留在结果中。

Answer 1

您需要做的第一件事是精确定义您想要的结果。

您可以通过定义一个结果的好坏来做到这一点，这样您就知道哪个是最好的。从数学上讲，您可以通过成本函数 来做到这一点。在这种情况下，通常会选择相关元素之间的距离之和、这些距离的平方和或最大距离。那么代价函数值较小的列表就是想要的结果。

目前尚不清楚在这种情况下是否可以通过某种特殊方法计算最佳解决方案(也许如果您选择最大距离或距离之和作为成本函数)。

无论如何，通过标准方法应该很容易找到一个好的近似值。

一个简单的 greedy approach 是将每个元素插入到整个列表的成本函数最小的位置。

一旦您有了一个好的起点，您就可以尝试通过修改列表以实现更好的解决方案来进一步改进它，例如通过交换元素或旋转列表的部分(local search、hill climbing、simulated annealing、other)。