游戏开发论坛

 找回密码
 立即注册
搜索
查看: 3466|回复: 8

[讨论] 【每周一题】修路

[复制链接]

11

主题

162

帖子

164

积分

注册会员

Rank: 2

积分
164
发表于 2010-5-17 21:17:00 | 显示全部楼层 |阅读模式
在一个特定区域内有M个村庄,现在要在P点建一所学校,然后在学校和村庄之间修建道路,使得各村庄到学校的路程之和最短。请问要如何确定学校的位置?

0

主题

2

帖子

0

积分

新手上路

Rank: 1

积分
0
发表于 2010-5-18 09:35:00 | 显示全部楼层

Re:【每周一题】修路

如果一个村庄那就在存在里面建,如果2个在中间建,如果三个要看位置,如果一条线上那就在中间存在建,如果构成一个面,那就在三角形中间建,如果4个。。。不知道了哈

3

主题

86

帖子

86

积分

注册会员

Rank: 2

积分
86
发表于 2010-5-18 10:33:00 | 显示全部楼层

Re:【每周一题】修路

画圆

5

主题

1461

帖子

1526

积分

金牌会员

Rank: 6Rank: 6

积分
1526
发表于 2010-5-18 11:11:00 | 显示全部楼层

Re:【每周一题】修路

这个好像是跟图论有关的吧?大学时候非必修课学了些,十几年之后的现在,全都还给老师了。。。。。。。。

8

主题

663

帖子

674

积分

高级会员

Rank: 4

积分
674
发表于 2010-5-18 11:16:00 | 显示全部楼层

Re:【每周一题】修路

在不确定村庄个数和分布情况的情况下,个人的做法是:将村庄两两相连,然后再找这个图形的中心点。。。

1

主题

422

帖子

423

积分

中级会员

Rank: 3Rank: 3

积分
423
发表于 2010-5-18 11:20:00 | 显示全部楼层

Re:【每周一题】修路

是叫拓扑图还是什么傅里叶算法了的,记得信号学过,不过我挂了...

15

主题

207

帖子

283

积分

中级会员

Rank: 3Rank: 3

积分
283
发表于 2010-5-18 16:27:00 | 显示全部楼层

Re:【每周一题】修路

费尔马点

或者广义的费尔马点

13

主题

832

帖子

1875

积分

金牌会员

空想家

Rank: 6Rank: 6

积分
1875
发表于 2010-5-18 18:34:00 | 显示全部楼层

Re:【每周一题】修路

实际求解的话,是不是可以以学校尺寸作为单元,取各村庄坐标后遍历所有位置来得到基本位置。
或者取所有位置的值后,除以一个比例常量后再遍历也是一样。

8

主题

205

帖子

238

积分

中级会员

Rank: 3Rank: 3

积分
238
发表于 2010-5-20 14:59:00 | 显示全部楼层

Re:【每周一题】修路

首先确定大致位置
在这些点内找到一个坐标,保证:以此点为坐标原点,其他所有点的坐标均匀分布在4个象限内。
第二步: 在+-Y方向 找到一个最靠近X轴的两个点 分别设量条平衡与X轴的线 为 Y =X1  Y=X2
         同理+-X方向。。。。。。。。。。。。。。。。。。。。。。。。 为 X =Y1  X=Y2
那么学校的建立地在两个相交的面形成的正方形中。
之后的计算较为复杂。 需要以原点为圆心计算每个象限内的点密度。保证象限内点密度最相近。

以上纯属于个人判断,不代表正确答案。可作参考。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2025-8-15 13:32

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表