我需要一种算法来(有效地)解决我正在编写的某些图表软件中出现的问题。
我有两组节点，N 和 M。N 中的每个节点 n0 与 M 中的唯一(对于 n0)节点有 0 到 M 连接。这些节点集将排列在两条平行的水平线上， M 节点上方的行中的 N 个节点。连接将绘制为从 N 到 M 的直线。
我需要做的是在它们的水平线内重新排列 N 和 M 节点，以尽量减少交叉。他们有什么方法比单纯地枚举所有可能的安排更有效吗，这是 O(N!*M!)？ (实际上，它比这更糟糕，因为还必须检查每个连接是否交叉)。
也欢迎引用相关文献，但需要解释为什么需要相关文献。
正如已经指出的那样，在一般情况下，这可以被视为二分图(集合 N 和 M)平面化算法。然而，这个特定问题比那个更受限制(我希望可以让它更快)并且需要产生额外的信息(这可能会使它变慢)，如下所示:
该图的限制是必须将连接绘制为从 N 到 M 的直线。在图论中，这实际上意味着连接不能落后 N 或 M 中的节点，仅在它们之间。因此，具有四个连接器的 2x2 情况可以在一般二分图情况下进行平面化，但在我的图表中不能。
额外的信息是，如果它不能被平面化，我仍然需要一个最小交叉解决方案(或接近它)。通常，最小交叉算法与仅平面化的算法有很大不同。
最佳答案
suddnely_me 是对的，但也许您不需要完美的解决方案。你也可以尝试一个非常简单的贪心算法。根据连接数对所有节点进行排序。然后一个一个地添加到水平线..虽然没有想通..但可能会导致一个简单的方法..
关于algorithm - (N x M) 图表问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5611786/