喜欢算法的都来挑战下吧（求最短路径）
有一张游戏地图，起点和终点（红色的点），两点之间分布着很多小怪（灰色的点），人物释放技能范围为R（灰色圆圈为范围）,释放一次技能，范围R内的怪物都会死亡，移动速度固定，
要求：人从 起点 移动到 终点 的过程中消灭所有怪物，求 人走的最短路径？
下图我随便标出了一组路径 ：起点-A-B-C-终点，这个路径不一定是最短的。 fishcany 发表于 2016-7-22 20:27
1 怪物坐标按圆分组，分出最少的圆
2 最短路径把所有圆心走一遍
嗯，现在最少的圆怎么分啊，这个好难，不知道怎么搞啊 fishcany 发表于 2016-7-22 21:42
while 怪物坐标列表不为空
从怪物坐标列表中取出任意点p
枚举围着P转一圈的半径r圆
嗯，但是这样还不是最小的结果啊，所得的圆心点一定是怪物点的坐标，故一定不是最短路径 fishcany 发表于 2016-7-22 21:55
那就枚举所有圆 所有点呗
这怎么枚举啊，打怪时候的点是任意的啊，就是要确定打怪时候的点啊 fishcany 发表于 2016-7-22 22:07
该说的都说了
应该有更好的方法吧
嗯，谢谢了，我再查下资料 给自己顶{:10_256:}{:10_256:} fishcany 发表于 2016-7-24 01:01
有新想法没啊{:5_91:} 不明觉厉啊= = qq554123053 发表于 2016-8-2 00:10
不明觉厉啊= =
{:10_243:} 太难了、无能为力、楼主找到解决办法分享一下、
主要是没办法证明贪心的正确性、 lx_Zz 发表于 2016-8-3 16:01
太难了、无能为力、楼主找到解决办法分享一下、
主要是没办法证明贪心的正确性、
我有个想法，但是不知道怎么证明是不是最短距离
第一步，以怪物点以半径R做圆，求出交集（路径中的点一定在里面）
第二部，以最短旅行商的问题为基础，进行改造，用贪婪算法求得（这个不好表达）
TSP问题本身是个NP难问题、
你这个点还不是整数点、涉及到精度的问题、建图都没法建、
首先你要解决建图的问题、你要考虑交集是不是可以只取四个方向的端点、
如果不行、就得是一段弧线、然后就得用积分、
然后就得看各种论文。。。
不想了、你去问问那些acm神牛吧、
PS：感觉这道题的模型蛮经典的、可能比赛出过这种题、我计算几何渣、只会简单凸包。。。 起点-〉B-〉C-〉A-〉终点 把这些点连起来，围成的面积最小就可以了，圆心的连线应该就是 大天使 发表于 2016-8-11 09:53
把这些点连起来，围成的面积最小就可以了，圆心的连线应该就是
圆心点都是任意的哦，我是随便确定的ABC几个点的 丹小怪 发表于 2016-8-10 22:48
起点-〉B-〉C-〉A-〉终点
ABC点都是任意的哦，我随便取的几个点 ligen超越 发表于 2016-8-11 10:08
ABC点都是任意的哦，我随便取的几个点
{:5_106:} ligen超越 发表于 2016-8-11 10:07
圆心点都是任意的哦，我是随便确定的ABC几个点的
没事啊，就是把怪围起来圈面积啊 大天使 发表于 2016-8-11 11:10
没事啊，就是把怪围起来圈面积啊
面积求出来之后再怎么办呀 用最少的圆，圈出来
页:
[1]
2