I'm doing AI for a simple puzzled game and need to solve the following problem efficiently (less than 1 sec for the range specified since I need to do many iterations in a game).
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
I have tried several approaches but none are fast or accurate enough.
The possibly complementary of this problem (minimizing the sum of distances to set of points at furthest distance from each corresponding monsters in the original set) seems to related to finding the geometric median, facility location problem, Weber problem etc.
Linear programming is also possible but might be too slow and overkilled.
Does anyone have any idea for a good approach?
Here is an illustration on a square of sides of length 3:
1-------2(M/3)-------3------4(M/1) | | 12(M/2) 5 | | 11(M/1) 6 | | 10--------9---------8(X)-------7
if you put a monster of strength 3 at 2, one with strenth 1 at 4, one with strength 2 at 12 and one with strength 1 at 11 and the hero(X) at 8. the sum of weighted distane is: 3*6 + 1*4 + 1*3 + 2*4 = 33, which is also the maximum in this case
I will try to point out a strategy that you can follow to achieve the required 1 second response time. Of course, it must be implemented to ensure it fits this requirement.
The solution relies on the following fact:
Basically, given the sum of weighted distance WP for a position P, each monster will contribute to the sum of weighted distances of a P neighbor by adding or subtracting 1 time it strength to WP. The strength is added if the neighbor is nearer to the monster than P or subtracted if it is farther.
With this fact in mind, the solution resides in compute sum of weighted distance for some initial position on a initial step, and compute the sum of weighted distance for the other positions based on the value previously computed for its neighbor.
Besides compute the value for the initial position, we must define on the initial step:
Then, starting on the neighbor of the initial position, we traverse all position on the defined direction, and for each one, we update SADD and SSUB (when we traverse the circular path, some monster that were getting nearer starts to get farther and vice versa) and add (SADD - SSUB) to the value computed for the previous neighbor.
Thus, we can compute the sum of weighted distances for all positions without having to iterate over all monsters for each position.
I implemented an initial version of the solution in Java.
The following class represents a monster:
class Monster {
private long strenght;
private int position;
// omitting getters and setters...
}
And the following class represents the square side positions:
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;
}
}
And finally, the optimization is performed in the following method:
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;
}
To setup the input you used as example, you can use:
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));
On a preliminary test, this method took 771 ms to execute, for 100,000 monsters and 200,000,000 possible positions, on a Intel Core i5-2400 running Windows 7.
I employed the following code to generate this input:
// 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;
}
I hope it helps you!