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 很简单啊，就是已经知道存在一串糖葫芦，让你把它找出来，不过要找葫芦最少的组合。 |
|
