algorithm - 绘制图形的遗传算法？职位分配问题

Question

我手头有一个分配问题，想知道应用局部搜索技术来达到理想的解决方案有多合适(搜索空间非常大)。

我有一个有向图(流程图)，我想在二维平面上以一种非常清晰、易于理解且易于人眼阅读的方式进行可视化。所以;我将为每个顶点分配 (x,y) 位置。我正在考虑使用模拟退火、遗传算法或您可以建议的任何此类方法来解决这个问题

输入:图 G = (V,E)
输出:一组分配，{(xi, yi) for each vi in V in}。换句话说，每个顶点将被分配一个位置(x，y)，其中坐标都是整数且 >= 0。

这些是我用来判断解决方案的标准(我欢迎任何建议):

• 相交边的数量应该最少，
• 所有边沿一个方向流动(即从左到右)，
• 高角度分辨率(两条边形成的最小角度 发生在同一个顶点)，
• 小区域 - 最不重要。

此外；我有一个初始配置(将位置分配给顶点)，是手工制作的。它非常困惑，这就是我尝试自动化该过程的原因。

我的问题是，

• 采用本地搜索技术有多明智？可能性有多大 它会产生预期的结果吗？

• 我应该从什么开始？模拟退火、遗传算法 还是别的？

• 我应该在开始时随机播种还是使用初始的 配置开始？

• 或者，如果您已经知道类似的实现/伪代码/东西，请指出我。

任何帮助将不胜感激。谢谢。

编辑:它不需要很快——不需要实时。此外; |V|=~200，每个顶点平均有大约 1.5 条出边。该图没有断开连接的组件。它确实涉及循环。

Answer 1

我建议查看 http://www.graphviz.org/Theory.php因为 graphviz 是领先的开源图形可视化工具之一。

根据任务的不同，也许完全使用 graphviz 进行可视化是有意义的。