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

ligen超越 · 发表于 2016-7-22 17:07:56

有一张游戏地图，起点和终点（红色的点），两点之间分布着很多小怪（灰色的点），
人物释放技能范围为R（灰色圆圈为范围）,释放一次技能，范围R内的怪物都会死亡，移动速度固定，
要求：人从起点移动到终点的过程中消灭所有怪物，求人走的最短路径？
下图我随便标出了一组路径：起点-A-B-C-终点，这个路径不一定是最短的。

ligen超越 · 发表于 2016-7-22 20:37:19

fishcany 发表于 2016-7-22 20:27
1 怪物坐标按圆分组，分出最少的圆
2 最短路径把所有圆心走一遍

嗯，现在最少的圆怎么分啊，这个好难，不知道怎么搞啊

ligen超越 · 发表于 2016-7-22 21:51:43

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

嗯，但是这样还不是最小的结果啊，所得的圆心点一定是怪物点的坐标，故一定不是最短路径

ligen超越 · 发表于 2016-7-22 22:01:49

fishcany 发表于 2016-7-22 21:55
那就枚举所有圆所有点呗

这怎么枚举啊，打怪时候的点是任意的啊，就是要确定打怪时候的点啊

ligen超越 · 发表于 2016-7-22 22:58:01

fishcany 发表于 2016-7-22 22:07
该说的都说了
应该有更好的方法吧

嗯，谢谢了，我再查下资料

ligen超越 · 发表于 2016-7-23 23:08:31

给自己顶

ligen超越 · 发表于 2016-7-24 21:14:22

fishcany 发表于 2016-7-24 01:01

有新想法没啊

qq554123053 · 发表于 2016-8-2 00:10:02

不明觉厉啊= =

ligen超越 · 发表于 2016-8-3 09:54:02

qq554123053 发表于 2016-8-2 00:10
不明觉厉啊= =

lx_Zz · 发表于 2016-8-3 16:01:13

太难了、无能为力、楼主找到解决办法分享一下、
主要是没办法证明贪心的正确性、

ligen超越 · 发表于 2016-8-5 13:59:32

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

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

lx_Zz · 发表于 2016-8-5 20:30:27

TSP问题本身是个NP难问题、
你这个点还不是整数点、涉及到精度的问题、建图都没法建、
首先你要解决建图的问题、你要考虑交集是不是可以只取四个方向的端点、
如果不行、就得是一段弧线、然后就得用积分、
然后就得看各种论文。。。
不想了、你去问问那些acm神牛吧、
PS：感觉这道题的模型蛮经典的、可能比赛出过这种题、我计算几何渣、只会简单凸包。。。

丹小怪 · 发表于 2016-8-10 22:48:43

起点-〉B-〉C-〉A-〉终点

大天使 · 发表于 2016-8-11 09:53:20

把这些点连起来，围成的面积最小就可以了，圆心的连线应该就是

ligen超越 · 发表于 2016-8-11 10:07:26

大天使发表于 2016-8-11 09:53
把这些点连起来，围成的面积最小就可以了，圆心的连线应该就是

圆心点都是任意的哦，我是随便确定的ABC几个点的

ligen超越 · 发表于 2016-8-11 10:08:09

丹小怪发表于 2016-8-10 22:48
起点-〉B-〉C-〉A-〉终点

ABC点都是任意的哦，我随便取的几个点

丹小怪 · 发表于 2016-8-11 10:38:41

ligen超越发表于 2016-8-11 10:08
ABC点都是任意的哦，我随便取的几个点

大天使 · 发表于 2016-8-11 11:10:50

ligen超越发表于 2016-8-11 10:07
圆心点都是任意的哦，我是随便确定的ABC几个点的

没事啊，就是把怪围起来圈面积啊

ligen超越 · 发表于 2016-8-11 12:00:57

大天使发表于 2016-8-11 11:10
没事啊，就是把怪围起来圈面积啊

面积求出来之后再怎么办呀

大天使 · 发表于 2016-8-11 13:41:31

用最少的圆，圈出来

账号		自动登录	找回密码
密码			立即注册