鱼C论坛

 找回密码
 立即注册
查看: 5774|回复: 27

喜欢算法的都来挑战下吧(求最短路径)

[复制链接]
发表于 2016-7-22 17:07:56 | 显示全部楼层 |阅读模式
50鱼币
有一张游戏地图,起点和终点(红色的点),两点之间分布着很多小怪(灰色的点),
人物释放技能范围为R(灰色圆圈为范围),释放一次技能,范围R内的怪物都会死亡,移动速度固定,
要求:人从 起点 移动到 终点 的过程中消灭所有怪物,求 人走的最短路径?
下图我随便标出了一组路径 :起点-A-B-C-终点,这个路径不一定是最短的。

示意图.jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-22 20:37:19 | 显示全部楼层
fishcany 发表于 2016-7-22 20:27
1 怪物坐标按圆分组,分出最少的圆
2 最短路径把所有圆心走一遍

嗯,现在最少的圆怎么分啊,这个好难,不知道怎么搞啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-22 21:51:43 | 显示全部楼层
fishcany 发表于 2016-7-22 21:42
while 怪物坐标列表不为空
    从怪物坐标列表中取出任意点p
    枚举围着P转一圈的半径r圆

嗯,但是这样还不是最小的结果啊,所得的圆心点一定是怪物点的坐标,故一定不是最短路径
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-22 22:01:49 | 显示全部楼层
fishcany 发表于 2016-7-22 21:55
那就枚举所有圆 所有点呗

这怎么枚举啊,打怪时候的点是任意的啊,就是要确定打怪时候的点啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-22 22:58:01 | 显示全部楼层
fishcany 发表于 2016-7-22 22:07
该说的都说了
应该有更好的方法吧

嗯,谢谢了,我再查下资料
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-23 23:08:31 | 显示全部楼层
给自己顶
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-7-24 21:14:22 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-2 00:10:02 | 显示全部楼层
不明觉厉啊= =
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-8-3 09:54:02 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-3 16:01:13 | 显示全部楼层
太难了、无能为力、楼主找到解决办法分享一下、
主要是没办法证明贪心的正确性、
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-8-5 13:59:32 | 显示全部楼层
lx_Zz 发表于 2016-8-3 16:01
太难了、无能为力、楼主找到解决办法分享一下、
主要是没办法证明贪心的正确性、

我有个想法,但是不知道怎么证明是不是最短距离
第一步,以怪物点以半径R做圆,求出交集(路径中的点一定在里面)
第二部,以最短旅行商的问题为基础,进行改造,用贪婪算法求得(这个不好表达)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-5 20:30:27 | 显示全部楼层
TSP问题本身是个NP难问题、
你这个点还不是整数点、涉及到精度的问题、建图都没法建、
首先你要解决建图的问题、你要考虑交集是不是可以只取四个方向的端点、
如果不行、就得是一段弧线、然后就得用积分、
然后就得看各种论文。。。
不想了、你去问问那些acm神牛吧、
PS:感觉这道题的模型蛮经典的、可能比赛出过这种题、我计算几何渣、只会简单凸包。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-10 22:48:43 | 显示全部楼层
起点-〉B-〉C-〉A-〉终点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-11 09:53:20 | 显示全部楼层
把这些点连起来,围成的面积最小就可以了,圆心的连线应该就是
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-8-11 10:07:26 | 显示全部楼层
大天使 发表于 2016-8-11 09:53
把这些点连起来,围成的面积最小就可以了,圆心的连线应该就是

圆心点都是任意的哦,我是随便确定的ABC几个点的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-8-11 10:08:09 | 显示全部楼层
丹小怪 发表于 2016-8-10 22:48
起点-〉B-〉C-〉A-〉终点

ABC点都是任意的哦,我随便取的几个点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-11 10:38:41 | 显示全部楼层
ligen超越 发表于 2016-8-11 10:08
ABC点都是任意的哦,我随便取的几个点

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-11 11:10:50 | 显示全部楼层
ligen超越 发表于 2016-8-11 10:07
圆心点都是任意的哦,我是随便确定的ABC几个点的

没事啊,就是把怪围起来圈面积啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2016-8-11 12:00:57 | 显示全部楼层
大天使 发表于 2016-8-11 11:10
没事啊,就是把怪围起来圈面积啊

面积求出来之后再怎么办呀
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2016-8-11 13:41:31 | 显示全部楼层
用最少的圆,圈出来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 22:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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