由网友(宁愿孤独也不再牵你的手)分享简介：在修桥问题表述如下：目前运行水平，通过一个区域的河流。有一组城市的上方和下方的河流。以上的河流每个城市匹配与下面的河城，您将得到该匹配为一组对。There is a river that runs horizontally through an area. There are a set of cities abo...

在修桥问题表述如下：

目前运行水平，通过一个区域的河流。有一组城市的上方和下方的河流。以上的河流每个城市匹配与下面的河城，您将得到该匹配为一组对。

There is a river that runs horizontally through an area. There are a set of cities above and below the river. Each city above the river is matched with a city below the river, and you are given this matching as a set of pairs.

您有兴趣制作了一组桥过河的最大连接数的匹配对城市的，但是你必须的方式，没有任何两个桥彼此交叉做到这一点。

You are interested in building a set of bridges across the river to connect the largest number of the matching pairs of cities, but you must do so in a way that no two bridges intersect one another.

设计一个算法尽可能有效解决这个问题成为可能。

Devise an algorithm to solve this problem as efficiently as possible.

我听说，这个问题是关系到最长递增子的问题，但我看不出如何在这里使用它。例如，如果我们考虑到对

I have heard that this problem is related to the longest increasing subsequence problem, but I don't see how to use it here. For example, if we're given the pairs

2  5  8  10
6  4  1  2

随后序列我们考虑LIS？

Then which sequence do we consider for LIS?

谢谢！

推荐答案

要累积到你如何使用时间最长递增子序列算法来解决这个问题，让我们用一些直觉开始，然后建立一个解决方案。既然你只能在匹配指数建立城市之间的桥梁，你能想到的设置，你最终建立成对的大集合桥梁的你可以找到不包含任何过境。那么在什么情况下，你会拥有一个路口？

To build up to how you'd use the longest increasing subsequence algorithm to solve this problem, let's start off with some intuition and then build up to a solution. Since you can only build bridges between cities at matching indices, you can think of the set of bridges that you end up building as the largest set of pairs you can find that don't contain any crossing. So under what circumstance would you have a crossing?

让我们看的时候会发生这种情况。假设我们排序全部由自己的第一座城市建造的桥梁。如果两个桥交叉，那么我们就必须有一些桥（一个我，B 我），使得其他一些桥（A Ĵ，B Ĵ）以下情况之一成立：

Let's see when this can happen. Suppose that we sort all of the bridges built by their first city. If two bridges cross, then we must have that there is some bridge (ai, bi) such that for some other bridge (aj, bj) one of the following holds:

在我＆LT;一个Ĵ和b 我> B Ĵ 在我>一Ĵ和b 我＆LT; b Ĵ ai < aj and bi > bj ai > aj and bi < bj

此第一例说，有一个桥，其顶部城市进一步是比我们桥的开始和其底部城市进一步是向左比我们桥的端部的右侧，而第二壳体处理相反的情况下

This first case says that there is a bridge whose top city is further to the right than the start of our bridge and whose bottom city is further to the left than the end of our bridge, and the second case handles the opposite case.

鉴于此属性需要持有，我们需要确保对每一套桥梁，我们有以下两种属性只有一个持有任何一桥（A 我，B 我），（A Ĵ，B Ĵ）：无论是

Given that this property needs to hold, we need to ensure that for every set of bridges, we have that exactly one of the two following properties holds for any pair of bridges (ai, bi), (aj, bj): either

在我和乐;一个Ĵ和b 我和乐; b Ĵ ai ≤ aj and bi ≤ bj

或

在我＆GE;一个Ĵ和b 我＆GE; b Ĵ ai ≥ aj and bi ≥ bj

在换言之，如果我们将通过第一坐标，该组第二坐标将总能增加桥梁排序。同样，如果我们将通过第二coordiante桥排序，第一个坐标将总能增加

In other words, if we were to sort the bridges by their first coordinate, the set of second coordinates would always be increasing. Similarly, if we were to sort the bridges by their second coordiante, the first coordinate would always be increasing.

这是我们刚刚定义的属性定义一个偏序与乐;在集桥梁，在这里我们说的是：（a 我，B的 两个我）和乐; 两个（A Ĵ，B Ĵ）如果我和乐;一个Ĵ和b 我和乐; b Ĵ。请注意，这不是一个全序 - 例如，（1,2）是无法比拟的（2,1） - 但它是一个偏序，因为它是自反，反对称和传递

The property that we've just defined defines a partial ordering ≤both on the set of bridges, where we say that (ai, bi) ≤both (aj, bj) if ai ≤ aj and bi ≤ bj. Notice that this is not a total ordering - for example, (1, 2) is incomparable with (2, 1) - but it is a partial ordering because it is reflexive, antisymmetric, and transitive.

鉴于此，该问题的目标是发现，我们可以可完全通过该关系有序元素的最大集合，因为如果我们具有一组包含两个无可比拟元件那些元件必然重新present穿越桥梁。换句话说，我们要找出最长链中的偏序。要做到这一点的方法之一是，在为O（n 2 ）时，比较每个元素彼此的元素，看看哪些元素可以通过与乐订购; 两个。这将产生一个向无环图，其中对（我，B 我）具有边缘（A Ĵ，B Ĵ）当且仅当（A 我，B 我）和乐; 两个（A Ĵ，B Ĵ）。一旦我们有了这个向无环图，我们就可以发现，在图中的最长路径发现的最大的集元素是呼叫可比由＆乐; 两个，它赋予在解决问题的办法。总的运行时间因此为O（n 2 ）。

Given this, the goal of the problem is to find the largest set of elements that we can that can be totally ordered by this relationship, since if we have a set containing two incomparable elements those elements must necessarily represent crossing bridges. In other words, we want to find the longest chain in the partial order. One way to do this is to, in O(n2) time, compare each element to each other element and see which elements can be ordered by ≤both. This produces a directed acyclic graph, where the pair (ai, bi) has an edge to (aj, bj) iff (ai, bi) ≤both (aj, bj). Once we have this directed acyclic graph, we can then find the longest path in the graph to find the largest set of elements that are call comparable by ≤both, which then gives the solution to the problem. The overall runtime is thus O(n2).

不过，我们可以做大幅度比这更好的。上述算法的问题是，我们不能轻易告诉元素相互对抗的比较，所以我们必须明确每个城市对对方城市进行比较。

However, we can do substantially better than this. The problem with the above algorithm is that we can't easily tell how the elements compare against one another, so we have to explicitly compare each city against each other city.

2  5  8 10
6  4  1  2 

让我们的城市的最下面一行进行排序：

Let's sort the cities by the bottom row:

8 10  5  2
1  2  4  6

现在，这里是真正冷静的观察。如果我们具备的要素排序的最下面一行，那么我们可以说如果两个对是通过订购和乐; 两个通过查看他们的第一行中的位置。如果第一对是到第二对的左侧，我们立即知道第一对的第二元件小于所述第二对的第二元件，因为我们已经排序他们由第二坐标。然后，我们有一对元件可建在一起当且仅当该第一对的第一个元素是小于第二对的第一个元素。因此，如果我们想找到一组桥，可以一起建成，我们要寻找的最上面一排的递增子，因为在这种情况下，第一和第二对元素都在增加，因为我们从移动左到右。寻找最长递增子然后解决了这个问题。既然我们可以通过他们的第二场对在为O（n log n）的排序，找出最长递增子在为O（n log n）的，这是一个为O​​（n log n）的解决问题的方法！

Now, here's the really cool observation. If we have the elements sorted by their bottom row, then we can tell if two pairs are orderable by ≤both by looking at their positions in the top row. If the first pair is to the left of the second pair, we immediately know that the second elements of the first pair is less than the second element of the second pair, since we've sorted them by the second coordinate. We then have that the pair of elements can be built together iff the first element of the first pair is less than the first element of the second pair. Consequently, if we want to find a set of bridges that can be built together, we're looking for an increasing subsequence of the top row, since in that case both the first and second elements of the pairs are increasing as we move from the left to the right. Finding the longest increasing subsequence then solves this problem. Since we can sort the pairs by their second field in O(n log n) and find the longest increasing subsequence in O(n log n), this is an O(n log n) solution to the problem!

呼！希望这个答案将详细介绍的东西！

Whew! Hope that this answer explains things in detail!