(N x M) 图表问题

Question

我需要一个算法来（高效地）解决我正在编写的一些绘图软件中出现的问题。我有两组节点N和M。每个在N中的节点n0最多与一个在M中独特的节点连接了M次。这些节点集将被排列在两条平行的水平线上，N节点在M节点的上面。连接将作为从N到M的直线绘制。

我需要重新排列N和M节点在它们的水平线内，以使交叉最少。是否有比仅单纯枚举所有可能的排列更有效率的方法（实际上，由于还必须检查每个连接的交叉，因此要更差，其时间复杂度为O(N!*M!))?

欢迎提供相关文献的参考，但需要说明其相关性。

正如已经指出的，一般情况下，这可以被认为是二分图（集合N和M）平面化算法。然而，这个具体问题比那个限制要严格得多（这希望能让它变得更快），并且需要产生额外的信息（这可能会使它变得更慢），如下所示：

1.图的限制是连接必须作为从N到M的直线绘制。在图论中，这实际上意味着连接不能穿过N或M中的节点，只能在它们之间。因此，四个连接的2x2案例可以在一般二分图情况下平面化，但在我的图中不能。

2.如果不能进行平面化，则需要一个最小交叉解（或接近最小）。通常，最小交叉算法与仅平面化的算法显着不同。

- RBarryYoung

Answer 1

你所描述的模型被称为二分图，而你所要求的是一个平面化算法。回答你的问题最好的方法是去谷歌一下。

- iehrlich

---

是的，它是一个二分图，感谢您的提醒。然而，绘图和图表并不完全相同，严格来说，这不是要求平面化算法，因为图表约束比那要严格得多。 - RBarryYoung

我理解这个问题，但我认为所要求的算法相当非通用，我只是在算法本身不存在的情况下指出了方向。你可能喜欢的是一些基于平衡树搜索N集合枚举的M集合覆盖N元素的算法（也许是贪婪算法）。 - iehrlich

我正在考虑这个。你有什么想法，这种方法平均会接近最优解吗？ - RBarryYoung

好问题。让我们将度量定义为交点的数量。只有当（x1！= x2）||（y1！= y2）时，“x1-> y1”和“x2-> y2”才能相交，这意味着首先您应该收集那些仅是特定Nj的子代的Mi，并将它们放置在相应的Nj下面。 M的其他Mk会导致可能的交点，因此问题自然地减少到（N，{Mk}）问题，其中每个Mk具有多个入边。如果对于特定的Mk，|IN（Mk）|= 2，则PRED（Mk）是两个候选项，可以在Mk附近放置它们之间。 - iehrlich

可以使用一些类似于布尔形式的反演覆盖方法。我认为（不要问我为什么），可以构建一个精度为2的算法。 - iehrlich

Answer 2

suddnely_me 是正确的，但也许你不需要一个完美的解决方案。你可以尝试一个非常简单的贪心算法。根据连接数量对所有节点进行排序，然后逐个添加到水平线上...虽然没有深入思考，但可能会导致一个简单的方法。

- duedl0r

---

这种方法接近最优解的程度如何？平均而言会有多接近？ - RBarryYoung

嗯...可能不是那么好。我无法证明，但我猜这并不是微不足道的 :) 只是一种感觉，贪心算法可能表现得不完全糟糕，因为你说你的连接性较低。 - duedl0r

我认为你的问题相当复杂，所以你也可以尝试使用遗传算法。缺点是，在每次重新计算后，你的图表看起来都不一样 :) - duedl0r

Answer 3

只要您不需要节点保持特定位置（即使您需要一些修改也可以实现），您的问题可以通过力图对齐来解决。

您需要改变的主要是将力对齐从2D变为1D，仅在X轴上对齐节点而不是在X和Y轴上对齐节点。

算法的前提是节点受到作用力，因此节点之间会产生排斥力，导致它们彼此远离。然而，连接在一起的节点之间会产生更大的吸引力。在每个循环中，您将这些力相加，使彼此相互吸引的节点靠近，而不被吸引的节点则会被排斥。当您总结出低于某个阈值（例如0.001）的总力时，您的对齐就完成了。

http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)

- Elijah Vankov

Answer 4

"N和M的大小是多少？有基于动态规划的解决方案，其运行时间为O(min(N,M)! * 2**max(N,M) * poly(N, M))，但我不确定您是否认为这比暴力搜索有显着改进。"

- zxc

---

通常在10到99的范围内，需要在典型PC（2GHz）上运行不超过5秒。好消息是平均连接较低，每个节点大约为2个（2 *（N + M））。因此，我可以吸收一些糟糕的性能，但不能太多。 - RBarryYoung