Tank的最优寻路策略【百度之星吧】

大家都知道从一点出发到一个目的地最好的算法是A*，但是对于该题来说，是多个目标（约13），如果想计算到所有矿点距离，从计算量上分析可知道，十几次的A*算法计算速度比一次Dijkstra还慢。
但是如果用一般的Dijkstra算法，每次坦克移动都需要重新计算，当然你可以把路径存储下来，但是如果中途遇到敌方坦克，还是可能会因进攻、逃跑等偏离了原始路线，之后还是要重新计算的。
实际上我们可以反过来考虑，不管哪方坦克最终的目标都是去占矿，而矿是不动的，因此，只需要以矿作为起点，应用优化的Dijkstra算法，计算出从矿点出发到所有位置的最短步数，并把它存储下来，如果把矿看成引力的源，那个每个位置的数字就是“势能”，所以，坦克只要沿着势能下降最快的方向移动即可。
每当地图有砖块变化时，从变化的位置扩散更新势能图即可。这样我们只要存储13张势能图，几乎不需要计算，即可知道敌、我各个坦克距离每一个矿的最短距离！
这样做还有个好处是，可以预测对方坦克的潜在目标以及路径，通过观察对方坦克距离各个矿的势能变化，使用贝叶斯方法不断更新先验概率，再结合打砖，就可以很精确的预测对方的目的矿点以及路线，深入的可以推测战局策略。很可惜我没能很好的利用这些信息，做出应对策略。

wym_0118_bdzd

回复：2楼
如果在一个坦克的时间里计算5*13的距离，肯能就有点悬了。我测试是超时了。用上述逆向Dijkstra就可以把计算省下来，用来做策略分析。

NotOnlySuccess

我从初赛开始就是做13次Dijkstra
现在演变成做23次Dijkstra了。。。
包括坦克，还有出生点到各个点的距离

游侠UFO

我是以坦克为起始点用bellman-ford算法计算的 - - 以坦克为起点的原因是 - - 因为很多策略并不以矿点为最终寻路目标 - - 而且 - - 不同情况下对权值矩阵的计算方法也不一样 - - 所以基本没法一开始就算好- - 囧 - -

游侠UFO

当然在众神牛面前，我的那些个策略似乎显得太小儿科了 - - 囧 - -   

zhouguoping3

楼主没有领会到A*的本质，自然没有对A*进行改良，完全可以对需要搜索的资源做一次A*计算啊，根本没有必要计算13次啊，我在本次测试50次A*计算还没超时问题，我现在程序中只需要不到10次的A*计算。完全可以应付。

zhouguoping3

回复：9楼
    应该是，我是在本机上测试的，服务器上应该比本机上要快8倍以上，个人估计：）

wym_0118_bdzd

回复：8楼
你说的完全可以，我提出的这种方法特点在于“逆向思维”，正向的A*在切换目标时候还是需要重新计算的。如果采用逆向的A*，A*依旧是比这种方法要慢的，因为多了一个估计距离，反倒没有直接的扩张松弛便捷。对于以矿作为目标的，用势能图计算量是最小的，节约时间做策略。当然，对于临时点到点的计算还是要用A*计算并保存路径的。


wym_0118_bdzd

使用势能图一个优点是无论自己坦克在那个位置，不用计算，可以直接看看脚下就知道该往哪里走，而且可以灵活多种选择，修正矿、砖周围的势能，可以避开不必要的矿视野、开砖，减少暴露；
第二个优点是同时监视了对方坦克离各个矿距离的变化，应用概率论里的贝叶斯公式可以预测对方的目标矿点，当其进入盲区可以计算在各个可能位置的概率，对策略有很大帮助。

NeuTopBoy

做了30余次DFS求最短路0毫秒的飘过
势能图只一个好听的称呼罢了。不就是计算每个点到矿的最短距离么。。。

网址：Tank的最优寻路策略【百度之星吧】 http://c.mxgxt.com/news/view/125274

相关内容

独家揭秘：明星肖像代言背后的百万级营销策略
明星经纪公司的商业策略：如何最大化明星价值？
明星宣传策略是指什么呢
问题明星的四大营销策略
明星应援广告的投放策略
深度解析：明星代言的营销策略与价值
企业明星代言策略：打造品牌与明星的共赢之道
深化明星代言效果：品牌营销策略的创新探索
明星宣传策略
娱乐圈深度解析：明星应对策略...@天马行空娱圈的动态

随便看看