我将其发布到 StackOverflow、cstheory.stackexchange.com 和 math.stackexchange.com,因为我不确定它最适合哪里。我希望没关系。
我有一个 2D 网格(每个地图的大小不同,范围从 10X10 到 20X20,必须是正方形),其中每个单元格包含每个单元(10 到 50,具体取决于地图)的概率(0 到 1)在那个地点。
有两种主要类型的单位,一些大单位的行为由你希望能帮助我的算法控制,还有一些小单位只能移动或在帮助下改变其(布尔)状态的大单位。所有单位都属于团队,但任何大单位都可以移动任何小单位。根据较小单位的位置和状态对比赛进行评分。每个单元都知道自己的坐标。
在多个指定单元中的任何一个中拥有一个小单元都会获得积分,并且根据占用的相邻单元的数量奖励奖金 - 注意相邻并不一定意味着相邻单元的坐标,并且将根据地图确定。
我已经有一个路径系统,所以这不是问题,计算移动的时间成本也不是问题,尽管出于性能原因应该最低限度地调用它。
我的意图是让计划系统输出一系列所需的状态/动作。例如,在 (9,4) 处以 43 度角,然后在 (12,4) 处以 12 度角启用小单元。
我正在尝试确定〜5个竞争主要单位中的每一个的最佳移动,以在时间用完时优化他们团队的终结位置。这些单元具有填充概率位置的模拟传感器,因此收集信息是一个有效的举措。
理想情况下,该算法会向前看几步,并考虑诸如特定动作是否使您处于执行下一步动作的好位置之类的事情-位置的这种“优点”将与路径成本相反。
性能在这里相当重要,我很可能愿意用解决方案质量来换取显着的性能提升。
到目前为止,这是我的想法:
最完整的解决方案是详尽的搜索,但性能排除了这一点。
我应该计算每个合理可能的当前状态的重要性,这样我就可以确定哪些信息是重要的。
如果可能,平均现代 PC 上的每个单元的运行时间应该 <= 25 毫秒 - 不是一成不变的 - 这是 C++,所以它相当快。
适应国际象棋算法可能是一个好方法。
我不擅长这个,我应该上网问问。
最好的方法几乎肯定是估计。
如果一个动作有 10% 的机会获得 20 倍于任何其他动作的点数,那么冒险是值得的——除非另一个动作几乎可以保证良好的结束位置并且时间快到了。
我的问题有点冗长。
我觉得到目前为止我一定有更多的想法,但我无法为我的生活思考它们是什么。
最后一点押韵了。
如果你还在读这篇文章,那么我可能愿意嫁给你。
虽然如果有人为此提供完整的解决方案会很棒,但我绝对愿意接受我能得到的任何帮助/提示,并且会接受让我走得最远的答案,不管那有多远。我对算法而不是代码感兴趣,因为我现在是一个大女孩,所以我可以自己处理。