应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 信息科学 » 程序算法 » 求助一个算法问题
91/1返回列表
查看: 1729  |  回复: 8
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

yy_nju

金虫 (正式写手)

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

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

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2013-11-11 20:35:43
已阅   回复此楼   关注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
赞一下(1人) 回复此楼
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 的主题更新
91/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考博] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +6 GDBe8tDZqE8z 2026-09-28 6/300 2026-09-29 14:41 by etmYJ6d2rquH
[考研] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 3/150 2026-09-29 14:24 by etmYJ6d2rquH
[找工作] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +6 IDs3scOF0tjC 2026-09-28 6/300 2026-09-29 14:13 by etmYJ6d2rquH
[博后之家] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +6 IDs3scOF0tjC 2026-09-28 7/350 2026-09-29 14:07 by etmYJ6d2rquH
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +4 IDs3scOF0tjC 2026-09-28 5/250 2026-09-29 13:50 by etmYJ6d2rquH
[教师之家] 某top大学教授说“能够在市场中兑现的能力才是真能力”无比同意！ +8 zju2000 2026-09-26 9/450 2026-09-29 13:47 by ahsoarli
[教师之家] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +4 GDBe8tDZqE8z 2026-09-28 4/200 2026-09-29 09:49 by JzYBbHIXWSrW
[考研] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:42 by ZvyPK8n6Nfki
[找工作] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:34 by ZvyPK8n6Nfki
[找工作] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:28 by ZvyPK8n6Nfki
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:18 by ZvyPK8n6Nfki
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 tqUTOxClQUMF 2026-09-28 3/150 2026-09-28 23:46 by b8fCuTHqckEt
[考研] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 GDBe8tDZqE8z 2026-09-28 3/150 2026-09-28 23:12 by b8fCuTHqckEt
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 4/200 2026-09-28 22:55 by ez6fGg9abYaj
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +4 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 22:55 by ez6fGg9abYaj
[找工作] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 5/250 2026-09-28 22:32 by ez6fGg9abYaj
[博后之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 3/150 2026-09-28 22:21 by ez6fGg9abYaj
[考博] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 6/300 2026-09-28 22:15 by ez6fGg9abYaj
[论文投稿] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 3/150 2026-09-28 19:08 by 9lS3ad5oOymn
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 18:51 by 9lS3ad5oOymn
信息提示
关闭
请填处理意见
关闭