x*****p 发帖数: 1707 | 1 平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。
要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说
,让任何蓝点去连接任何红点,但各不相交。 |
g*********s 发帖数: 1782 | 2 一定存在解吗?
【在 x*****p 的大作中提到】 : 平面上有随机2000个点,其中1000蓝点,1000红点。但任何三点都不同线。 : 要求寻找一种最优化的算法,生成1000条互不相交的连接蓝点和红点的线段。换句话说 : ,让任何蓝点去连接任何红点,但各不相交。
|
x*****p 发帖数: 1707 | 3 是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。 |
f*******4 发帖数: 1401 | 4 那个vehicle pickup/deliver解法是什么样的?
二分图最大匹配好像跟这个没关系啊
【在 x*****p 的大作中提到】 : 是的,以前有一个回帖,提出一种算法,是肯定能找到解的,只是复杂度太高了。
|
g*********s 发帖数: 1782 | 5 我觉得这个不是简单的图论问题,而是计算几何的问题。这个两两不交的限制很强。
【在 f*******4 的大作中提到】 : 那个vehicle pickup/deliver解法是什么样的? : 二分图最大匹配好像跟这个没关系啊
|
x*****p 发帖数: 1707 | |
g*********s 发帖数: 1782 | 7 三角化?
【在 x*****p 的大作中提到】 : 需要用到三点不共线这个非常强的条件。
|
x*****p 发帖数: 1707 | 8 缘起: 我有一个当教授的朋友,他偶然向我提到这个题目,说是和另一个美国教授聊天
的时候那个教授提出的,他也没解法。但数学上证明解的存在性是很容易的。因为我是
研究算法的,所以我这个朋友就来问我。我想了十几分钟也没思路就放弃了。一周后,
我的朋友打电话问我想的怎么样了,我本来是很羞愧的说不知道的,谁知当时灵光一闪
,想到一个复杂度为O(n^2)的算法可以解决这个问题。后来把算法整理写给我的朋友。
现在回想,恐怕有更好的O(nlnn)的算法,但不确定。这个版大牛多,上来问问,5个包
子答谢。 |
g***s 发帖数: 3811 | 9 抛砖引玉一下:
解法一:
这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O
(N^3).
解法二:
分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对
两部分分治。
如何找到这样的两点(先给一个nlgn的算法)
1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。
2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。
3. 把所有点求tan,排序。
4. 从小到大进行count,一直到找到这么一条边(A->B)。(易知一定存在这么一条边)
f(n) = max{ f(k) + f(n-k) + nlgn } k=1..n-1
f(n) = O(nlgn * n) = O(n^2 * lgn)
改进找B点的算法
3. 建立一最大堆,和一最小堆
4. 轮流从最大堆最小堆来进行查找,直到找到B
f(n) = max { f(k) + f(n-k) + (n + k*lgn)} k = 1..n/2
f(n) = O(n^2)
O(nlgn)感觉很难。 |
x*****p 发帖数: 1707 | 10 这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为
以后递归的话,这个序是不会变的。 |
|
|
O*N 发帖数: 207 | 11 能解释一下为什么第四步一定能找到满足条件的B点?
如何保证分成的两部分中,红点和兰点的数量一定相等?
=O
【在 g***s 的大作中提到】 : 抛砖引玉一下: : 解法一: : 这题可以看作是二分图的最大匹配的最小值路径匹配问题。用KM算法可以知道O(N*M)=O : (N^3). : 解法二: : 分治法。找到两点,把所有点分成两部分,每个部分都用相同多的红点和蓝点。然后对 : 两部分分治。 : 如何找到这样的两点(先给一个nlgn的算法) : 1. 找x值最小的一个点A(如果有多个x值相同,取y值最小),把它作为其中一点。 : 2. 把A作为原点。其它所有点对于A(都减去Ax,Ay),都相当会落入第一和第四象限。
|
g***s 发帖数: 3811 | 12 assume the A is blue, it scan from bottom to up for all the rest N-1
point.
count=1
+1 for blue point
-1 for red point.
So, there are 499 times +1 and 500 times -1. count will reach 0 at some
point.
The point that makes count = 0 is the B. the worse case is the B is the
last one. then all N-2 points are in the one side and 0 point in the other
side.
【在 O*N 的大作中提到】 : 能解释一下为什么第四步一定能找到满足条件的B点? : 如何保证分成的两部分中,红点和兰点的数量一定相等? : : =O
|
g***s 发帖数: 3811 | 13 因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还
是回变的。
【在 x*****p 的大作中提到】 : 这个解法二是当时我的思路,只是上面第三步的排序,其实只需要一次排序即可,因为 : 以后递归的话,这个序是不会变的。
|
x*****p 发帖数: 1707 | 14 是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一
个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。
【在 g***s 的大作中提到】 : 因为他们是相对与A的tan值。当递归(分治)的时候,是一个新的A。他们的tan的序还 : 是回变的。
|
g***s 发帖数: 3811 | 15 给个反例。
【在 x*****p 的大作中提到】 : 是的。但要注意的是,我们永远选择最左边的点作为新的原点。这样,所有点相当于一 : 个平移操作,虽然角度发生了变化,但序是不变的。这个可以做出数学证明。
|
x*****p 发帖数: 1707 | 16 Good example.
Then the algorithm can not be improved to O(nlnn) |