24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 651  |  回复: 2
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

evelynyin

新虫 (初入文坛)

[求助] 请较一下这个问题是否是NP-hardness问题,如何证明

给定二维空间上的n个点和常数r,若点p与q的距离小于等于r,则p和q相互覆盖。问题:找出数目最少的点,使得它们覆盖所有的n个点。
不知道这个问题是否为NP-hardness问题,如何证明。希望大家帮忙看一下.
回复此楼

» 猜你喜欢

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

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

evelynyin

新虫 (初入文坛)

谢谢楼上。不知道这个问题是否可归约到集合覆盖问题。原谅楼主愚笨,还请大家帮忙
3楼2014-05-25 10:13:45
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 3 个回答

ll550

木虫 (职业作家)

我觉得好像不是

[ 发自小木虫客户端 ]
livelong
2楼2014-05-24 23:42:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 339求调剂 +5 烤麦芽 2026-03-27 6/300 2026-03-28 09:17 by 星空星月
[考研] 材料与化工272求调剂 +4 阿斯蒂芬2004 2026-03-28 4/200 2026-03-28 09:15 by 乐呵呵的追梦人
[考研] 275求调剂 +10 jjjjjjjjjjl 2026-03-27 10/500 2026-03-27 23:47 by barnett0632
[考研] 275求调剂 +10 Micky11223 2026-03-25 13/650 2026-03-27 22:42 by Micky11223
[考研] 070300求调剂306分 +3 26要上岸 2026-03-27 3/150 2026-03-27 17:57 by arrow8852
[考研] 272求调剂 +7 脚滑的守法公民 2026-03-27 7/350 2026-03-27 17:23 by laoshidan
[考研] 07化学280分求调剂 +10 722865 2026-03-23 10/500 2026-03-27 15:51 by Plutoqq
[考研] 材料与化工(0856)304求B区调剂 +7 邱gl 2026-03-27 7/350 2026-03-27 15:27 by Joe率
[考研] 308求调剂 +7 墨墨漠 2026-03-25 7/350 2026-03-27 14:47 by 狂炫麦当当
[考研] 348求调剂 +4 小懒虫不懒了 2026-03-27 5/250 2026-03-27 12:47 by 果果妈咪
[考研] 材料学硕,求调剂 6+5 糖葫芦888ll 2026-03-22 10/500 2026-03-27 08:18 by hypershenger
[考研] 求调剂,一志愿 南京航空航天大学大学 ,080500材料科学与工程学硕 +4 @taotao 2026-03-26 5/250 2026-03-27 08:10 by hypershenger
[硕博家园] 招收生物学/细胞生物学调剂 +3 IceGuo 2026-03-26 4/200 2026-03-27 05:35 by user003
[考研] 343求调剂 +4 赠我一本书 2026-03-23 4/200 2026-03-27 00:40 by wxiongid
[考研] 一志愿郑州大学,080500学硕,总分317分求调剂 +4 举个栗子oi 2026-03-24 5/250 2026-03-26 23:15 by 不吃魚的貓
[考研] 总分322求生物学/生化与分子/生物信息学相关调剂 +5 星沉uu 2026-03-26 6/300 2026-03-26 19:02 by macy2011
[考研] 打过很多竞赛,085406控制工程300分,求调剂 +3 askeladz 2026-03-26 3/150 2026-03-26 09:08 by 给你你注意休息
[考研] 303求调剂 +6 蓝山月 2026-03-25 6/300 2026-03-25 22:47 by 418490947
[考研] 335求调剂 +4 yuyu宇 2026-03-23 5/250 2026-03-23 23:49 by Txy@872106
[考研] 275求调剂 +6 shansx 2026-03-22 8/400 2026-03-22 15:27 by barlinike
信息提示
请填处理意见