24小时热门版块排行榜    

查看: 1816  |  回复: 8

yy_nju

金虫 (正式写手)

[求助] 求助一个算法问题

写论文遇到一个问题,好久不搞算法了,想不到好办法,问题如下:
  
平面上有n个点,每个点都有(x,y)坐标,每个点的都有一个权重值,求权重之和最大的x个点,要求这些点彼此之间的距离均大于s,算法要求输出这些点 (其中n和s都是给定的,x未知)
  
  
我只能想到一种复杂度为O(n!)的算法,求高手解答,谢谢!!!
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐,对您同样有帮助:

已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

feixiaolin

荣誉版主 (文坛精英)

优秀版主

等价于用直径为s的圆覆盖这些点,再微调一下。
2楼2013-11-11 20:47:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yy_nju

金虫 (正式写手)

引用回帖:
2楼: Originally posted by feixiaolin at 2013-11-11 20:47:58
等价于用直径为s的圆覆盖这些点,再微调一下。

是这个意思,有什么好办法吗?
3楼2013-11-11 21:33:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yongcailiu

金虫 (小有名气)

引用回帖:
3楼: Originally posted by yy_nju at 2013-11-11 21:33:56
是这个意思,有什么好办法吗?...

参见此书第一章和第四章,链接http://product.dangdang.com/9044572.html#catalog
4楼2013-11-11 22:21:46
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

dameng

银虫 (小有名气)

在水木上看到你了。如果是求最优解,貌似没法更好了。
研究方向:数据库。主要面向图数据管理、图数据挖掘、社会网络等。目前正在关注动态图算法。
5楼2013-11-11 23:05:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yy_nju

金虫 (正式写手)

引用回帖:
4楼: Originally posted by yongcailiu at 2013-11-11 22:21:46
参见此书第一章和第四章,链接http://product.dangdang.com/9044572.html#catalog...

能否指点一二,现在开始看书来不及发paper了
6楼2013-11-12 09:48:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yy_nju

金虫 (正式写手)

引用回帖:
5楼: Originally posted by dameng at 2013-11-11 23:05:45
在水木上看到你了。如果是求最优解,貌似没法更好了。

猿粪。。
你意思最优的算法就是O(n!)?
7楼2013-11-12 09:48:49
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yongcailiu

金虫 (小有名气)

引用回帖:
6楼: Originally posted by yy_nju at 2013-11-12 09:48:10
能否指点一二,现在开始看书来不及发paper了...

摘抄书上的一个结论:平面上任意一组共n个点的最小包围圆,可以在O(n)的期望运行时间内计算出来,而且为此需要的空间在最坏的情况下不会超过线性规模。书里面采用的是随机增量式算法。给的文献是 smallest enclosing disks(balls and ellipsoids),作者是E.Welzl
8楼2013-11-13 11:07:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yy_nju

金虫 (正式写手)

引用回帖:
8楼: Originally posted by yongcailiu at 2013-11-13 11:07:58
摘抄书上的一个结论:平面上任意一组共n个点的最小包围圆,可以在O(n)的期望运行时间内计算出来,而且为此需要的空间在最坏的情况下不会超过线性规模。书里面采用的是随机增量式算法。给的文献是 smallest enclosi ...

很谢谢你,我参考一下!你这个不是应助贴,我没法把金币给你,你再回一楼吧
9楼2013-11-13 14:33:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 yy_nju 的主题更新
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[教师之家] 为了不被淘汰,必须要开始第三次奋斗了 +8 lice_1987 2026-11-15 11/550 2026-11-19 21:32 by lice_1987
[考博] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +4 uKOSCocCb6Fm 2026-11-12 8/400 2026-11-19 17:38 by Equinoxhua
[考博] 售SCI文章,我:8O.5.5.1O.54,科目全,可十急 +4 SX5mJmPWDfOO 2026-11-13 4/200 2026-11-19 17:15 by Equinoxhua
[论文投稿] IVD领域内综述投稿推荐 100+3 小小筑梦 2026-11-16 5/250 2026-11-19 17:03 by hansi2025
[基金申请] 注意啦!用基金购买打印纸、硒鼓、优盘、移动硬盘、个人计算机属于违规了 +3 iaeyuan 2026-11-17 3/150 2026-11-19 08:45 by newfuzzy1
[教师之家] 征友后感触 +6 重新启 2026-11-17 7/350 2026-11-19 08:12 by m_zyj
[考博] 27博士申请(市政/环境) +4 ladf 2026-11-12 4/200 2026-11-18 20:18 by junqiang
[找工作] 售SCI一区T0P文章,我:8.O.55.1.O54,科目全,可伽急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-18 14:51 by UPDUsNlULsJZ
[考研] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 SX5mJmPWDfOO 2026-11-13 4/200 2026-11-18 13:55 by UPDUsNlULsJZ
[论文投稿] 售SCI一区T0P文章,我:8O.55.1.O.5.4,科目齐全,可+急 +5 SX5mJmPWDfOO 2026-11-13 5/250 2026-11-18 13:44 by UPDUsNlULsJZ
[硕博家园] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +5 SX5mJmPWDfOO 2026-11-13 6/300 2026-11-18 13:33 by UPDUsNlULsJZ
[考研] 售SCI一区文章,我:8.O.55.1.O.54,科目齐全,可伽急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 11:21 by Z1pODz48hoDV
[考博] 售SCI一区T0P文章,我:8.O.55.1.O.5.4,科目全,可+急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 10:37 by Z1pODz48hoDV
[考研] 售SCI一区T0P文章,我:8O.55.1.O.54,科目全,可伽急 +5 uKOSCocCb6Fm 2026-11-13 5/250 2026-11-18 10:15 by Z1pODz48hoDV
[论文投稿] 售SCI一区T0P文章,我:8O.55.1.O.5.4,科目齐全,可+急 +3 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-18 10:04 by Z1pODz48hoDV
[公派出国] 售SCI文章,我:8O5.5.1.O.54,科目齐全,可+急 +4 uKOSCocCb6Fm 2026-11-12 8/400 2026-11-18 09:53 by Z1pODz48hoDV
[考博] 27年药学 考博申请 +4 。12345 2026-11-14 5/250 2026-11-16 19:52 by 0611517sll
[硕博家园] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-16 11:06 by K7HMGGdOpylw
[公派出国] 售SCI一区文章,我:8.O.55.1.O.54,科目齐全,可伽急 +4 uKOSCocCb6Fm 2026-11-13 4/200 2026-11-16 10:44 by K7HMGGdOpylw
[公派出国] 售一区SCI文章T0P,我:8O.551.O54,科目全,可十急 +3 SX5mJmPWDfOO 2026-11-13 3/150 2026-11-15 08:29 by xSrQNSSjcgoX
信息提示
请填处理意见