（在有人问之前，这不是作业。）
假设您有 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 因此它们也“连接”。
（图片提供：belisarius）
一个数组中的每个元素在第二个数组。 将数组中的每个元素想象为一个顶点，这些连接作为从一个数组绘制到另一个数组的边。
我需要找到一个一组边（最大尺寸），这样任何“边”（或线）都不会相交。
在上面的示例中，请注意，
-
Edge 1 和 Edge 2 将相交。
-
边 6 将与边 3、边 4、边 5 相交。
因此，解决方案可以是 1,3,4,5 或 2,3,4,5 (size = 4)，因为这些线都不会彼此相交。可以有多种解决方案，但我只需要一种。
我的问题是，是否有任何已知的与此类似的 CS 问题？我应该使用什么算法？
我试图用一个例子来解释我的问题，但是，如果仍然不清楚，我会澄清任何疑问。
提前致谢。
(Before anyone asks, it's not homework.)
Say you have 2 Arrays y0 and y1 where
y0 = [1,2,3,4,5,6] and
y1 = [2,1,6,3,4,5]
Notice y0[0] = y1[1] = 1, it essentially means y0[0] is connected to y1[1]. Similarly, y0[2] = y1[3] = 3 so they are "connected" as well.
(Image courtesy : belisarius)
Each element in one array has a corresponding entry in the second array. Imagine each element in the array as a vertex, and these connections as Edges being drawn from one array to the other.
I need to find a set of edges (of maximum size) such that none of the "edges" (or lines) will intersect.
In the above example, notice,
Edge 1 and Edge 2 will intersect. Edge 6 will intersect with Edge 3, Edge 4, Edge 5.
Therefore, the solution can be be 1,3,4,5 or 2,3,4,5 (size = 4) since none of those lines will intersect each other. There can be multiple solutions, but I need just one.
My Question, Is there any known CS Problem that resembles this? What algorithm should i be using?
I've tried to explain my problem with an example, however, incase it's still not clear i'll clarify any queries.
Thanks in advance.
发布评论
评论（3）
假设单个数组中没有重复的元素，这就是最长递增子序列。
不失一般性，假设第一个数组 A1 只是
[1, 2, 3, ..., n]。使用哈希集可以在 O(n) 内完成此转换，或者使用 BST 可以在 O(nlogn) 内完成此转换。请注意，我们的集合有一个交叉当且仅当它包含
i和j并且iij但j出现在第二个数组 A2 中的i之前（我们知道，因为i < j，i< /code> 出现在 A1 中的j之前。那么如果一个集合没有交叉，它显然对应于 A2 的递增子序列，反之亦然。
最长递增子序列有一个简单的 O(n^2) 解和一个稍微复杂的 O(nlogn) 解。
Assuming that no element is repeated in a single array, this is simply longest increasing subsequence.
Without loss of generality, assume that the first array, A1, is just
[1, 2, 3, ..., n]. This transformation can be done in O(n) with a hash-set, or O(nlogn) with a BST.Note that our set has a crossing if and only if it contains
iandjwithi < jbutjappearing beforeiin the second array A2 (we know sincei < jthatiappears beforejin A1).Then if a set has no crossing it clearly corresponds to an increasing subsequence of A2 and vice versa.
Longest increasing subsequence has a simple O(n^2) solution and a slightly more complex O(nlogn) solution.
它基本上是计算反转问题的数量。[来源 - 第 5.3 节，算法设计，Kleinberg 和 Tardos。 http://books.google.co.in/books/about /Algorithm_Design.html?id=25p3mHu3ij8C]
It is basically counting number of inversions problem.[Source - Section 5.3, Algorithm Design, Kleinberg and Tardos. http://books.google.co.in/books/about/Algorithm_Design.html?id=25p3mHu3ij8C]
您所描述的内容被称为二分图的匹配问题。我怀疑这个问题有一些（尚未阐明的）使得它难以解决。到目前为止，您实际上还没有对可以使用哪些边进行任何限制。假设有某些边（不是全部）可用，那些“可能的”边形成一个图，而您决定使用的边形成最大匹配。在图中查找最大匹配是一项多项式时间算法，并且对于二分情况进行编码特别容易。
标题听起来好像环境可能会强加一些情况，因此“不相交”的边可能不可行（“最少边相交”）。也许您想要边缘覆盖（或 1-覆盖），即每个顶点都属于至少一条边缘。那么，如果两个“顶点”数组的长度不同，就不会出现“完美匹配”，即同时也是覆盖的匹配。经典结果霍尔婚姻定理描述了二部图中存在完美匹配的情况。如果图是正则图（所有顶点的度数相等），则柯尼希定理告诉我们存在完美匹配（以及更多）。
补充：
可能值得说明一下图片似乎所说的关于选择边缘的限制。两组顶点的坐标为 {(i,0) | i=1,..,N} 且 {(j,1) | j=1,...,N}。当 y0[i] = y1[j] 时，有 N 条可用的边、连接 (i,0) 和 (j,1) 的线段。尽管主题行说“最少边缘交叉”，但解决方案是这些边缘的最大子集，不允许交叉，最大 平面直线图包含在给定的排列图中。
它与此处考虑的 2 级交叉最小化问题有关：
分层图上交叉最小化的替代方法 - P. Mutzel
“我们建议...删除最小数量的边，以便生成的图是 k 级平面...在本文中，我们解决了情况 k = 2... [W]e 解决在给定 2 级图中提取最大权重的 2 级平面子图的问题。这个问题是 NP 困难的。”
当前问题在两个顶点集中施加相同数量的点，基本图是1度规则的，并且在点的编号或位置上不允许选择。所以不可能得出它像上面论文中描述的那么难的结论。然而，它确实引导我们使用所谓的“分支定界”方法来精确解决此类问题。
让我们将原始问题的“边”视为新图的“节点”，其中两个节点相邻（当且仅当原始边相交）。 [这是交集图的示例。] 重述的问题现在是找到 新图的最大独立集。这类问题一般都是 NP 困难的，但我们再次怀疑当前问题的程度可能不那么普遍。
怀疑多项式时间算法可能存在的一个原因是，对于平面凸集的有限集合的交集图的最大独立子集，多项式时间近似算法的可用性：
二维凸对象的独立交集图 -- P. Agarwal 和 M Mustafa
“在本文中，我们提出了独立的近似算法-设置平面内线段和凸物体的交集问题。”
关于当前问题的特殊性还有一项进一步的观察，该观察似乎使其可以在多项式时间内解决。 圆形图是可以绘制为圆的弦的线段的交集图。通过扰动论证，可以这样绘制排列图的直线边缘，而不会丢失或引入交集。
现在圆图的最大独立集问题可以在多项式时间内解决。上面链接的维基百科文章提供了此参考：
纳什，尼古拉斯； Gregg, David (2010)，“计算圆图最大独立集的输出敏感算法”，Information Processing Letters 116 (16): 630–634
我还在 Google 图书中找到了此参考文献：
Valiente, Gabriel (2003)，“圆图上最大权重独立集问题的一种新简单算法”，算法与计算：第 14 届研讨会，ISAAC 2003 年京都
What you are describing is known as the matching problem for bipartite graphs. I suspect there is something (as yet unstated) about the problem which makes it difficult to solve. So far you really haven't placed any restriction on what edges can be used. Supposing that there are certain edges (not all) available, those "possible" edges form a graph, and the ones you decide to use form a maximum matching. Finding a maximum matching in a graph is a polynomial time algorithm, and it is particularly easy to code for the bipartite case.
The title makes it sound as though circumstances might impose some circumstance so that "disjoint" edges might not be feasible ("least edge intersections"). Perhaps you want edge covering (or 1-cover), i.e. that every vertex belongs to at least one edge. Then, if the two "vertex" arrays are of different length, there will not be a "perfect matching", i.e. a matching that is also a cover. A classic result Hall's Marriage Theorem characterizes when there are perfect matchings in a bipartite graph. If the graph is regular (all vertices have equal degree), then König's Theorem tells us there is perfect matching (and more).
Added:
It may be worth stating what the picture seems to say about the restrictions on choosing edges. Two sets of vertices have coordinates {(i,0) | i=1,..,N} and {(j,1) | j=1,..,N}. There are N available edges, line segments that connect (i,0) and (j,1) whenever y0[i] = y1[j]. Although the subject line says "least edge intersections", a solution is a maximum subset of these edges that admits no intersections, a largest planar straight-line graph contained in a given permutation graph.
It is related to the 2-level crossing minimization problem considered here:
An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel
"We suggest... removing the minimal number of edges such that the resulting graph is k-level planar... In this paper we address the case k = 2... [W]e address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard."
The present problem imposes an equal number of points in the two vertex sets, the base graph is regular of degree 1, and no choice is allowed in the numbering or positioning of points. So it is not possible to conclude it is as hard as the one described in the above paper. However it does direct us to so-called "branch and bound" methods for the exact solution of such problems.
Let's consider the "edges" of the original problem as "nodes" of a new graph where two nodes are adjacent iff the original edges intersect. [This is an example of an intersection graph.] The problem as restated is now to find a maximum independent set of the new graph. The problems of that kind are in general NP-hard, but again we suspect the extent of the present problems may not be so general.
One reason to suspect a polynomial time algorithm could exist is the availability of polynomial time approximation algorithms for maximum independent subsets of intersection graphs for finite collections of planar convex sets:
Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa
"In this paper, we present approximation algorithms for the independent-set problem on intersection graphs of line segments and convex objects in the plane."
There is one further observation about the specialness of the present problem that seems to make it solvable in polynomial time. A circle graph is the intersection graph of line segments that can be drawn as chords of a circle. By a pertubation argument the straight-line edges of a permutation graph can be so drawn, without loss or introduction of intersections.
Now the maximum independent set problem for circle graphs can be solved in polynomial time. The Wikipedia article linked above gives this reference:
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
I also found this reference in Google Books:
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