algorithm - 在闭合路径上定位点以最大化到加权点样本的距离总和(游戏 AI)

Question

我正在为一个简单的益智游戏做 AI，需要有效地解决以下问题(在指定范围内不到 1 秒，因为我需要在游戏中进行多次迭代)。

A sample of N (1 to 100,000) monsters with strength from 1 to 10,000 are distributed on the sides of a square (0 to 200,000,000) at 1 unit interval starting from the upper left corner. Move hero to a point X on the square to maximize sum of the weighted distances to the monsters. A weighted distance to each monster is calculated by MonsterStrength*ShortestDistanceToX (by going clockwise or anticlockwise). X must also be on the 1 unit interval mark and the monsters and hero move on the sides of the square only

我尝试了几种方法，但都不够快或不够准确。

这个问题的可能补充(最小化与原始集合中每个相应怪物最远距离的点集的距离总和)似乎与寻找几何中位数、设施位置问题、韦伯问题等有关。

线性规划也是可能的，但可能太慢且过度杀伤。

有人知道好的方法吗？

---

这是边长为 3 的正方形的插图:

1-------2(M/3)-------3------4(M/1)|                              |12(M/2)                        5|                              |11(M/1)                        6|                              |10--------9---------8(X)-------7

如果你把一个力量为 3 的怪物放在 2，一个力量为 1 的怪物为 4，一个力量为 2 的怪物为 12，一个力量为 1 的怪物为 11，英雄(X)为 8。加权距离之和为:3*6 + 1*4 + 1*3 + 2*4 = 33，也是本例中的最大值

Answer 1

我将尝试指出您可以遵循的策略来实现所需的 1 秒响应时间。当然，必须实现它以确保它符合此要求。

解决方案依赖于以下事实:

基本上，给定位置 P 的加权距离 WP 之和，每个怪物将通过增加或减去 1 倍其强度到 WP 来贡献 P 邻居的加权距离总和。如果邻居比 P 更靠近怪物，则增加强度；如果更远，则减去强度。

考虑到这一事实，解决方案在于在初始步骤中计算某个初始位置的加权距离总和，并根据先前为其邻居计算的值计算其他位置的加权距离总和。

除了计算初始位置的值外，我们还必须在初始步骤上定义:

• 我们将遍历位置以计算加权距离总和的方向(例如顺时针)
• 在定义的方向上遍历时，我们将走得更远(添加)的怪物的力量总和(SADD)；
• 在定义的方向上遍历时，我们将接近(减去)的怪物的力量总和(SSUB)；

然后，从初始位置的邻居开始，我们遍历定义方向上的所有位置，并为每个位置更新 SADD 和 SSUB(当我们遍历圆形路径时，一些越来越近的怪物开始得到更远，反之亦然)并将(SADD - SSUB)添加到为前一个邻居计算的值。

因此，我们可以计算所有位置的加权距离总和，而无需为每个位置遍历所有怪物。

我用 Java 实现了该解决方案的初始版本。

下面的类代表一个怪物:

class Monster {
    private long strenght;
    private int position;
    // omitting getters and setters...        
}

下面的类表示正方形的边位置:

class SquareSidePositions {
    private List<Monster>[] positionWithMosters;
    private List<Monster> monstersOnSquareSides = new ArrayList<Monster>();

    @SuppressWarnings("unchecked")
    public SquareSidePositions(int numberOfPositions) {
        positionWithMosters = new LinkedList[numberOfPositions];
    }

    public void add(int position, Monster monster) {
        if (positionWithMosters[position] == null) {
            positionWithMosters[position] = new LinkedList<Monster>();
        }

        positionWithMosters[position].add(monster);
        monster.setPosition(position);
        monstersOnSquareSides.add(monster);
    }

    public int size() {
        return positionWithMosters.length;
    }

    public boolean hasMonsters(int position) {
        return positionWithMosters[position] != null;
    }

    public long getSumOfStrenghtsOfMonstersOnThePosition(int i) {
        long sum = 0;

        for (Monster monster : positionWithMosters[i]) {
            sum += monster.getStrenght();
        }

        return sum;
    }

    public List<Monster> getMonstersOnSquareSides() {
        return monstersOnSquareSides;
    }
}

最后，通过以下方法进行优化:

public static int findBest(SquareSidePositions positions) {
    long tini = System.currentTimeMillis();
    long sumOfGettingNearer = 0;
    long sumOfGettingFarther = 0;
    int currentBestPosition;
    long bestSumOfWeight = 0;
    long currentSumOfWeight;
    final int numberOfPositions = positions.size();
    int halfNumberOfPositions = numberOfPositions/2;
    long strenghtsOnPreviousPosition = 0;
    long strenghtsOnCurrentPosition = 0;
    long strenghtsOnPositionStartingGetNearer = 0;
    int positionStartGetNearer;

    // initial step. Monsters from initial position (0) are skipped because they are at distance 0 
    for (Monster monster : positions.getMonstersOnSquareSides()) {
        // getting nearer
        if (monster.getPosition() < halfNumberOfPositions) {
            bestSumOfWeight += monster.getStrenght()*monster.getPosition();
            sumOfGettingNearer += monster.getStrenght();
        } else {
        // getting farther
            bestSumOfWeight += monster.getStrenght()*(numberOfPositions - monster.getPosition());
            sumOfGettingFarther += monster.getStrenght();
        }
    }

    currentBestPosition = 0;
    currentSumOfWeight = bestSumOfWeight;

    // computing sum of weighted distances for other positions
    for (int i = 1; i < numberOfPositions; ++i) {
        strenghtsOnPreviousPosition = 0;
        strenghtsOnPositionStartingGetNearer = 0;
        strenghtsOnCurrentPosition = 0;
        positionStartGetNearer = (halfNumberOfPositions + i - 1);

        if (positionStartGetNearer >= numberOfPositions) {
            positionStartGetNearer -= numberOfPositions;
        }

        // monsters on previous position start to affect current and next positions, starting to get farther
        if (positions.hasMonsters(i-1)) {
            strenghtsOnPreviousPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i-1);  
            sumOfGettingFarther += strenghtsOnPreviousPosition;
        }

        // monsters on current position will not affect current position and stop to get nearer
        if (positions.hasMonsters(i)) {
            strenghtsOnCurrentPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i);
            currentSumOfWeight -= strenghtsOnCurrentPosition;
            sumOfGettingNearer -= strenghtsOnCurrentPosition;
        }

        // monsters on position next to a half circuit start to get nearer
        if (positions.hasMonsters(positionStartGetNearer)) {
            strenghtsOnPositionStartingGetNearer = positions.getSumOfStrenghtsOfMonstersOnThePosition(positionStartGetNearer);
            sumOfGettingNearer += strenghtsOnPositionStartingGetNearer;
            sumOfGettingFarther -= strenghtsOnPositionStartingGetNearer;
        }

        currentSumOfWeight += sumOfGettingFarther - sumOfGettingNearer;

        // if current is better than previous best solution
        if (currentSumOfWeight > bestSumOfWeight) {
            bestSumOfWeight = currentSumOfWeight;
            currentBestPosition = i;
        }
    }

    final long executionTime = System.currentTimeMillis() - tini;

    System.out.println("Execution time: " + executionTime + " ms");
    System.out.printf("best position: %d with sum of weighted distances: %d\n", currentBestPosition, bestSumOfWeight);

    return currentBestPosition;
}

要设置您用作示例的输入，您可以使用:

SquareSidePositions positions = new SquareSidePositions(12);

positions.add(1, new Monster(3));
positions.add(3, new Monster(1));
positions.add(10, new Monster(1));
positions.add(11, new Monster(2));

在初步测试中，此方法在运行 Windows 7 的英特尔酷睿 i5-2400 上针对 100,000 个怪物和 200,000,000 个可能的位置执行了 771 毫秒。

我使用以下代码生成此输入:

// I used numberOfMosters == 100000 and numberOfPositions == 200000000
public  static SquareSidePositions initializeMonstersOnPositions(int numberOfMonsters, int numberOfPositions) {
    Random rand = new Random();
    SquareSidePositions positions = new SquareSidePositions(numberOfPositions);

    for (int i = 0; i < numberOfMonsters; ++i) {
        Monster monster = new Monster(rand.nextInt(10000)+1);

        positions.add(rand.nextInt(numberOfPositions), monster);
    }

    return positions;
}

希望对你有帮助!