在封闭path上定位点,以最大化加权点样本的距离总和
我正在做一个简单的困惑游戏的人工智能,需要有效地解决以下问题(小于1秒的范围指定,因为我需要在游戏中做很多迭代)。 从左上角开始以1个单位间隔在正方形(0至200,000,000)的边上分布N(1至100,000)个强度为1至10,000的怪物的样本。 将英雄移动到正方形上的一个点X上,以最大化加到怪物上的距离的总和。 每个怪物的加权距离由MonsterStrength * ShortestDistanceToX(顺时针或逆时针)计算。 X也必须在1单位间隔标记上,怪物和英雄只在广场的两侧移动 我已经尝试了几种方法,但都不够快或不够准确。 这个问题的可能的补充(最小化到距离原始集合中每个对应怪物最远距离处的距离总和)似乎与寻找几何中值,设施位置问题,Weber问题等有关。 线性编程也是可能的,但可能太慢而且过度。 有没有人有一个好方法的想法? 这里是长度为3的两边正方形的插图: 1 ——- 2(M / 3)——- 3 —— 4(M / 1) | | 12(M / 2)5 | | 11(M / 1)6 | | 10 ——– ——— 9 8(X)——- 7 如果你把一个3的强度为2的怪物,一个在4的强度1,一个在12的强度2,一个在11的强度为1,英雄(X)在8,加权distne的总和是:3 * 6 + 1 * 4 + 1 * 3 + 2 * 4 […]