e****d 发帖数: 333 | 1 已知:
1.一段实数域上的线段:[A,B].
2.另外一些线段,两端点在[A,B]以内,且长度小于等于[A,B]的线段。[a,b],[c,d],[e
,f]......
求一个由2里面的线段组成的集合,这个集合满足:
1.覆盖[A,B]
2.互不相交(端点除外)。
3.线段数最小。
已知这样的集合存在。
有没有好算法?
谢谢。 | e****d 发帖数: 333 | 2 我是按照起始点先排序,然后比较结束的那个端点和其他的起始点。。。。
觉得比较低效。 | b***e 发帖数: 1419 | 3 We define a follower relation between each 2 line segments:
l1 follows l2 iff l1.start == l2.end. We use l2 < l1 to denote l1
follows l2.
Let start = [A, A], and end = [B, B], and consider set of line
segments extened with start and end.
The follower relation naturally leads to a partial order on the all
the line segments, which is, in fact, a direct acyclic graph. Now the
only thing you need to do is to find a shortest path from start to
end, which can be done using standard bfs graph travers | s*****g 发帖数: 5159 | 4 decision version is NP hard reduction to partition problem?
[e
【在 e****d 的大作中提到】 : 已知: : 1.一段实数域上的线段:[A,B]. : 2.另外一些线段,两端点在[A,B]以内,且长度小于等于[A,B]的线段。[a,b],[c,d],[e : ,f]...... : 求一个由2里面的线段组成的集合,这个集合满足: : 1.覆盖[A,B] : 2.互不相交(端点除外)。 : 3.线段数最小。 : 已知这样的集合存在。 : 有没有好算法?
| e****d 发帖数: 333 | 5 你说的是什么意思?
我不是很懂,能不能解释一下。谢谢。
【在 s*****g 的大作中提到】 : decision version is NP hard reduction to partition problem? : : [e
| e****d 发帖数: 333 | 6 要这么搞?这个我还真没想到。
这种问题有没有个标准的解法?找一个完全覆盖的集合并且子集相邻但不相交,子集个
数最小。
【在 b***e 的大作中提到】 : We define a follower relation between each 2 line segments: : l1 follows l2 iff l1.start == l2.end. We use l2 < l1 to denote l1 : follows l2. : Let start = [A, A], and end = [B, B], and consider set of line : segments extened with start and end. : The follower relation naturally leads to a partial order on the all : the line segments, which is, in fact, a direct acyclic graph. Now the : only thing you need to do is to find a shortest path from start to : end, which can be done using standard bfs graph travers
| g*****u 发帖数: 298 | 7 这个看起来像set cover,其实不然
【在 e****d 的大作中提到】 : 要这么搞?这个我还真没想到。 : 这种问题有没有个标准的解法?找一个完全覆盖的集合并且子集相邻但不相交,子集个 : 数最小。
| b***e 发帖数: 1419 | 8 这个图上最短路的reduction还不够标准么? 你这个问题只不过是对图的一个奇怪的输
入表示罢了.
【在 e****d 的大作中提到】 : 要这么搞?这个我还真没想到。 : 这种问题有没有个标准的解法?找一个完全覆盖的集合并且子集相邻但不相交,子集个 : 数最小。
| l***i 发帖数: 1309 | 9 This problem cannot be NP-hard.
Assume the intervals are (a1,b1) (a2,b2) ... and a1<= a2 <=a3 ...
if not we can sort them.
Then if I pick (a1,b1), then the next interval has to start with a_i = b1,
or the collection will not be able to cover interval [A, B].
Like what others mentioned, create a graph with each interval represented by
a vertex, there is an edge from vertex u=(a_i,b_i) to vertex w(a_j,b_j) if
b_i == a_j.
Then the problem is asking for a shortest path from a source, which can be
an | d*****l 发帖数: 8441 | 10 很简单啊,就是已经知道存在一串糖葫芦,让你把它找出来,不过要找葫芦最少的组合。 |
|