求一问题的解题思路及涉及哪一数学领域_数学吧

数学吧关注：941,677贴子：9,463,163

一个平面上有互相交叉的若干长短不一的线段，这其中肯定有若干互不交叉的线段组成的线段子集，请问如何求得互不交叉的线段总长最长的线段子集，或者换一个方式，如何拿掉总长最短的线段使得剩余线段互不交叉

送TA礼物

IP属地:天津

1楼2011-09-08 17:22回复

如果所有的线段长度都是1，弱化的问题等价于求线段集S的intersection graph的独立集。这个问题是npc的，也就是很可能没有多项式非近似算法

2楼2011-09-08 18:07

不感兴趣

开通SVIP免广告

咱不懂别随便说啊。。
不知道线段长度范围如何，但是动态规划就可以做了，先按右端点排个序，然后F[i]表示以第i条线段为结尾，线段总和最多是多长，然后从1~i-1更新答案即可。。

3楼2011-09-08 19:01

那你告诉我转移方程是什么？你那方法明明是基于所有线段共线的

4楼2011-09-08 19:31

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴