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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 信息科学 » 通信科学 » 几何问题求解释
北京石油化工学院2026年研究生招生接收调剂公告
71/1返回列表
查看: 804  |  回复: 6
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

yanweicumt

银虫 (小有名气)

[求助] 几何问题求解释

note that, with Manhattan distance as our metric, each node has no more than 4d neighbors at distance d, and for a network of n nodes arranged in a square grid, the distance between any two nodes is bounded by 2*sqrt(n).

请大家帮忙看下这句话，我怎么就计算不出来这个4d和2*sqrt（n）呢
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-06-30 13:55:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军

【答案】应助回帖

yanweicumt(金币+3): 2011-06-30 22:27:31
自己画一下,曼哈顿距离是边长之和

例如如果是蓝色点,所有距离为2的点是黑色的,共4*2=8个,如果在靠近边上,会少于8个,很容易理解

边长为n的grid,任意2个点的曼哈顿距离绝对小于grid的对角线,不过这个上限应该是sqrt(2)*n啊,绿色那条
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-06-30 15:01:31
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yanweicumt

银虫 (小有名气)
引用回帖:
Originally posted by libralibra at 2011-06-30 15:01:31:
自己画一下,曼哈顿距离是边长之和

例如如果是蓝色点,所有距离为2的点是黑色的,共4*2=8个,如果在靠近边上,会少于8个,很容易理解

边长为n的grid,任意2个点的曼哈顿距离绝对小于grid的对角线,不过这个上限应该 ...

谢谢你的回复，很详细。
但我还有几个问题：
1， 这个grid的边长是多少呢？论文中这句话的意思应该是将n的节点放到单位正方形中吧
当如果距离d改为3，或者更大时，就到不了4d个邻居节点啊？
2，为什么你画的图里面是用n做边长？
3，曼哈顿是边长的和，所以如果得知正方形的边长是sqrt（n）的话，两个节点之间的距离就是2×sqrt（n），你觉得呢？
赞一下 回复此楼
3楼2011-06-30 22:27:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
引用回帖:
Originally posted by yanweicumt at 2011-06-30 22:27:04:
谢谢你的回复，很详细。
但我还有几个问题：
1， 这个grid的边长是多少呢？论文中这句话的意思应该是将n的节点放到单位正方形中吧
当如果距离d改为3，或者更大时，就到不了4d个邻居节点啊？
2，为什么你画 ...

呵呵,我粗心了,我刚看了遍,是n node.边长是sqrt(n),结果就对了
如果n node,矩形是x*y = n,当且仅当x==y = sqrt(n)是取到极值
此时斜边
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
4楼2011-06-30 22:38:47
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
另外,你说的第2点"当如果距离d改为3，或者更大时，就到不了4d个邻居节点啊？"就是我说的,靠近边的时候会肯定小于4*d的,但是,如果这个grid再大点,边长大于等于6的时候,你从中心点计算其neighbour是可以找到12个的,所以人家原文说的是"no more than 4d neighbors"

那段话是给出了2个boundaries:
1.grid中任意一个节点的曼哈顿距离为d的邻节点个数不会超过4*d.能不能取到这个极值,跟距离与边长和节点位置有关.可以想象,在一个无穷grid中,任意几点的邻节点个数都等于4*d;

2.n个nodes的grid中,任意2个节点之间的曼哈顿距离不会超过2*sqrt(n).上面分析了,假设这个grid长和宽分别是x,y,那么有 x*y = n, 这个grid中距离最远的2个节点是矩形的对角线上2个点.他们之间的曼哈顿距离就是 x+y.由不等式 x+y>=2*sqrt(x*y)=2*sqrt(n)就知道这个极值在x=y=sqrt(n)的时候取得.
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
5楼2011-06-30 22:47:01
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

yanweicumt

银虫 (小有名气)
引用回帖:
Originally posted by libralibra at 2011-06-30 22:47:01:
另外,你说的第2点"当如果距离d改为3，或者更大时，就到不了4d个邻居节点啊？"就是我说的,靠近边的时候会肯定小于4*d的,但是,如果这个grid再大点,边长大于等于6的时候,你从中心点计算其neighbour是可以找 ...

谢谢，可是为什么是x×y=n呢，n个节点和这个grid有什么关系啊？
赞一下 回复此楼
6楼2011-06-30 23:08:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
引用回帖:
Originally posted by yanweicumt at 2011-06-30 23:08:02:
谢谢，可是为什么是x×y=n呢，n个节点和这个grid有什么关系啊？

n个节点的grid,边长是x,y,肯定有x*y=n的
赞一下 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
7楼2011-06-30 23:32:53
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 yanweicumt 的主题更新
71/1返回列表
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 材料调剂 +8 一样YWY 2026-04-05 9/450 2026-04-06 07:24 by hmn_wj
[考研] 材料与化工371求调剂 +14 陪琳看海 2026-04-04 15/750 2026-04-06 06:59 by houyaoxu
[考研] 085600，320分求调剂 +15 大馋小子 2026-04-04 16/800 2026-04-06 06:34 by houyaoxu
[考研] 316求调剂 +5 yyx想调剂 2026-04-05 5/250 2026-04-05 22:22 by 咔咔咔咔9
[考研] 086000生物与医药298调剂求助 +9 元元青青 2026-03-31 12/600 2026-04-05 21:03 by 学员8dgXkO
[考研] 求调剂到0856材料工程 +3 程9915 2026-04-05 3/150 2026-04-05 18:15 by 蓝云思雨
[考研] 080200学硕，机械工程专业277分，求带走！ +7 瓶子PZ 2026-03-31 7/350 2026-04-05 17:49 by liucky
[考研] 一志愿西北农林畜牧专硕336分求调剂 +3 5ourr 2026-04-03 3/150 2026-04-05 10:40 by JOKER0401
[考研] 338求调剂 +7 晟功? 2026-04-03 7/350 2026-04-04 20:37 by 蓝云思雨
[考研] 368求调剂 +5 今华习 2026-04-03 7/350 2026-04-04 18:47 by imissbao
[考研] 322求调剂 +4 FZAC123 2026-04-03 4/200 2026-04-03 20:55 by zhq0425
[考研] 一志愿南昌大学324求调剂 +13 hanamiko 2026-04-01 13/650 2026-04-03 18:30 by ls刘帅
[考研] 326求调剂 +3 9ahye 2026-04-02 4/200 2026-04-03 08:43 by Jaylen.
[考研] 调剂 +3 好好读书。 2026-04-01 6/300 2026-04-02 15:49 by liumengping
[考研] 一志愿北京科技大学085601材料工程英一数二初试总分335求调剂 +9 双马尾痞老板2 2026-04-01 9/450 2026-04-02 12:14 by oooqiao
[考研] 0856初试324分求调剂 +6 想上学求调 2026-04-01 6/300 2026-04-02 11:42 by 星空星月
[考研] 一志愿北交大材料工程，总分358 +4 cs0106 2026-04-01 4/200 2026-04-02 07:42 by 尚水阁主
[考研] 安全工程 285 求调剂 +3 Xinyu56 2026-04-01 4/200 2026-04-01 21:50 by 静静静静静静静�
[考研] 349求调剂 +6 吃的不少 2026-04-01 6/300 2026-04-01 17:55 by JYD2011
[考研] 求0861交通运输专硕or材料专硕调剂 +4 勒布朗@ 2026-03-31 4/200 2026-04-01 09:54 by 一只好果子?
信息提示
关闭
请填处理意见
关闭