算法最边缘交叉口

Question

（有人问之前，这不是功课。）

假设你有2个阵列y0和y1其中

y0 = [1,2,3,4,5,6]和 y1 = [2,1,6,3,4,5]

通知y0[0] = y1[1] = 1，这基本上意味着y0[0]连接到y1[1]。同样，y0[2] = y1[3] = 3也是“连接”的。

（图片提供：贝利萨留）

在一个阵列中的每个元件具有第二阵列中的相应条目。 想象阵列中的每个元素为顶点，并且这些连接为边缘从一个阵列绘制到另一个阵列。

我需要找到一组边缘（最大尺寸），以使“边缘”（或线条）不会相交。

在上述示例中，通知，

1. Edge 1和Edge 2将相交。
2. Edge 6将与Edge 3, Edge 4, Edge 5相交。

因此，该解决方案可以是为由于无那些线将相互交叉的1,3,4,5或2,3,4,5（大小= 4）。可以有多种解决方案，但我只需要一个解决方案。

我的问题，是否有任何已知的CS类似这样的问题？我应该使用什么算法？

我试着用一个例子来解释我的问题，但是，如果它仍然不清楚，我会澄清任何疑问。 在此先感谢。

Answer 1

假设没有元素在单个阵列中重复，这简直是最长的子序列。

不失一般性，假设第一个数组A1仅为[1, 2, 3, ..., n]。这个转换可以在O（n）中用散列集来完成，或者用O（nlogn）用BST来完成。

请注意，我们的设置有交叉，如果只有它是否包含i和j与i < j但j第二列A2（我们知道，因为这i < j在i A1 j之前出现）的出现i前后。

然后，如果一组没有交叉，它显然对应于A2的增加的子序列，反之亦然。

最长的增长子序列有一个简单的O（n^2）解决方案和一个稍微复杂的O（nlogn）解决方案。

Answer 2

你所描述的是被称为 matching problem for bipartite graphs。我怀疑有什么东西（至今没有说明），这个问题很难解决。到目前为止，您还没有对可以使用哪些边进行限制。假设有某些边（不是全部）可用，那些“可能的”边形成一个图形，并且您决定使用的边形成最大匹配。在图中寻找最大匹配是一个多项式时间算法，并且对于二分情况编码特别容易。

标题使听起来好像情况可能会施加某些情况，以致“不相交”的边缘可能不可行（“最小边交点”）。也许你想要边缘覆盖（或1覆盖），即每个顶点至少属于一个边缘。那么，如果两个“顶点”数组长度不同，就不会有“完美匹配”，即匹配也是一个封面。经典结果 Hall's Marriage Theorem表示何时在二分图中存在完美匹配。如果图是规则的（所有顶点具有相同的度数），那么 König's Theorem告诉我们有完美的匹配（以及更多）。

补充：

这可能是值得说明的图片，似乎要说什么关于选择边缘的限制。两组顶点的坐标为{（i，0）| i = 1，...，N}和{（j，1）| J = 1，...，N}。当y0 [i] = y1 [j]时，有N个可用边，连接（i，0）和（j，1）的线段。尽管主题行称“最小边交点”，但解决方案是这些边的最大子集，它不允许交集，最大的 planar straight-line graph包含在给定的 permutation graph中。

它与这里考虑的2级交叉最小化问题：

An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel

“我们建议......除去最小数量的边缘，使得所得图是K-水平平面。在本文中，我们解决了案例k = 2 ... [W] e解决了在给定的2级图中提取最大权重的2级平面子图的问题，这个问题是NP难的。

目前的问题在两个顶点集合中强加了相同数量的点，基本图形是1级正则，并且在点的编号或定位中不允许选择。所以不可能断定它与上述文章中描述的一样难。然而，它确实将我们引向所谓的“分支和界限”方法，以精确解决这些问题。

让我们考虑原始问题的“边缘”作为新图的“节点”，如果原始边相交，则两个节点相邻。 [这是一个交集图的例子。]现在重新解决的问题是找到新图的 a maximum independent set。这类问题总体上是NP难度的，但我们再次怀疑目前问题的严重程度可能不那么普遍。

一个理由怀疑一个多项式时间算法可能存在是多项式时间近似算法用于平面凸集的有限集合相交曲线的最大独立子集的可用性：

Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa

“在本文中，我们在平面中的线段和凸对象的相交图上提出了独立集问题的近似算法。“

关于目前问题的特殊性，似乎可以在多项式时间内解决这个问题还有一种观察。 A circle graph是可以绘制为圆的和弦的线段的交集图。通过摄影论证，可以绘制置换图的直线边缘，而不会丢失或引入交叉点。

现在圈图的最大独立集问题可以用多项式时间求解。维基百科的文章上面链接给出了这样的参考：

Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634

我还发现，在谷歌图书此引用：

Valiente, Gabriel (2003), "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs", Algorithms and computation: 14th Symposium, ISAAC 2003 Kyoto

Answer 3

它基本上是计数反演问题的数量。[来源 - 第5.3节，算法设计，Kleinberg和Tardos。 http://books.google.co.in/books/about/Algorithm_Design.html?id=25p3mHu3ij8C]