建筑桥梁问题说明如下:
我听说此问题与longest increasing subsequence问题有关,但是我在这里看不到如何使用它。例如,如果我们得到了对
2 5 8 10
6 4 1 2
那么我们考虑LIS的顺序是什么?谢谢!
最佳答案
为了增强如何使用最长的增长子序列算法来解决此问题的方法,让我们从一些直觉开始,然后构建一个解决方案。由于您只能在匹配索引的城市之间建立桥梁,因此可以将最终构建的桥梁集合视为可以发现的最大对,其中不包含任何交叉。那么在什么情况下您会过马路?
让我们看看何时会发生这种情况。假设我们对第一座城市建造的所有桥梁进行了排序。如果有两个桥相交,那么我们必须有一个桥(ai,bi),使得对于另一个桥(aj,bj),下列条件之一成立:
第一种情况是说,有一座桥,其顶部城市比我们的桥的起点靠右,而其底部城市比我们的桥的终点靠左,而第二种情况则处理相反的情况。
鉴于需要保留此属性,因此我们需要确保对于每组桥,对于任何一对桥(ai,bi),(aj,bj),我们都具有以下两个属性之一:
要么
换句话说,如果我们要按桥的第一坐标对桥进行排序,那么第二坐标的集合将一直在增加。同样,如果我们要按桥的第二坐标对桥进行排序,则第一坐标将一直在增加。
我们刚刚定义的属性定义了桥集合上的部分排序≤both,如果ai≤aj且bi≤bj,则说(ai,bi)≤both(aj,bj)。请注意,这不是总排序-例如,(1,2)与(2,1)是不可比的-但这是部分排序,因为它是自反的,反对称的和可传递的。
鉴于此,问题的目标是找到可以通过这种关系完全排序的最大元素集,因为如果我们有一个包含两个不可比元素的元素集,那么这些元素必须代表跨桥。换句话说,我们希望以偏序找到最长的链。一种方法是,在O(n2)时间内,将每个元素彼此比较,并查看哪些元素可以≤≤both。这将产生一个有向无环图,其中(ai,bi)对具有(aj,bj)iff(ai,bi)≤both(aj,bj)的边。一旦有了这个有向无环图,我们就可以找到longest path in the graph来找到最大的元素集,这些元素的可比性≤两者都可以,从而给出了问题的解决方案。因此,总运行时间为O(n2)。
但是,我们可以做得更好。上述算法的问题在于,我们无法轻易分辨出元素之间的比较方式,因此我们必须明确地将每个城市与另一个城市进行比较。
2 5 8 10
6 4 1 2
让我们按底行对城市进行排序:
8 10 5 2
1 2 4 6
现在,这是非常酷的观察。如果我们将元素按其底行排序,则可以通过查看它们在顶行中的位置来判断两对元素是否均≤。如果第一对在第二对的左边,我们立即知道第一对的第二个元素小于第二对的第二个元素,因为我们已经按照第二个坐标对它们进行了排序。然后,如果第一对中的第一个元素小于第二对中的第一个元素,则可以将这对元素构建在一起。因此,如果我们想找到一组可以一起建造的桥,我们正在寻找最上面一行的子序列,因为在这种情况下,当我们从中间移开时,对中的第一和第二个元素都在增加。从左到右。找到最长的增长子序列即可解决此问题。由于我们可以按O(n log n)中的第二个字段对对进行排序,并找到O(n log n)中最长的递增子序列,因此这是该问题的O(n log n)解决方案!
ew!希望这个答案能详细解释一切!
关于algorithm - 搭建桥梁的问题-如何应用最长的递增子序列?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7288585/