Ben*_*tal 6 algorithm math graph
我有多个组来指定符号的关系..例如:
[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),它现在位于这些符号之间,稍微保留了这种关系.
请注意,订单并不重要.在结果中,XYZ可以放在第一个或最后一个,因为这些符号与任何其他符号无关.然而,相关符号的接近程度是重要的.
我需要帮助确定一个采用符号关系组的算法,然后使用上面的逻辑输出一维数组.由于使用实际数据,关系组中符号的数量可以变化,关系组的数量也没有限制,符号可以与任何其他符号有关系,因此我不知道如何执行此操作.
为了进一步说明我的困境的棘手问题,如果你在上面的例子中添加另一个关系组.让我们说:
[C Z]
结果现在应该是这样的:
[X Y Z C B A D E]
请注意,符号Z和C现在更接近,因为它们的关系通过附加数据得到了加强.之前的所有关系仍保留在结果中.
您需要做的第一件事是精确定义您想要的结果.
你可以通过定义结果的好坏来做到这一点,这样你就知道哪个是最好的.数学上你通过成本函数来做到这一点.在这种情况下,通常会选择相关元素之间的距离之和,这些距离的平方和或最大距离.然后,具有较小的成本函数值的列表是期望的结果.
目前尚不清楚在这种情况下是否可以通过某种特殊方法计算最佳解决方案(可能选择最大距离或距离之和作为成本函数).
无论如何,通过标准方法很容易找到一个很好的近似值.
一个简单的贪婪方法是将每个元素插入到整个列表的结果成本函数最小的位置.
一旦你有了一个好的起点,你可以尝试通过修改列表以获得更好的解决方案来进一步改进它,例如通过交换元素或旋转列表的部分(本地搜索,爬山,模拟退火,其他).