Minimizing distance to a weighted grid
- by Andrew Tomazos - Fathomling
Lets suppose you have a 1000x1000 grid of positive integer weights W.
We want to find the cell that minimizes the average weighted distance.to each cell.
The brute force way to do this would be to loop over each candidate cell and calculate the distance:
int best_x, best_y, best_dist;
for x0 = 1:1000,
for y0 = 1:1000,
int total_dist = 0;
for x1 = 1:1000,
for y1 = 1:1000,
total_dist += W[x1,y1] * sqrt((x0-x1)^2 + (y0-y1)^2);
if (total_dist < best_dist)
best_x = x0;
best_y = y0;
best_dist = total_dist;
This takes ~10^12 operations, which is too long.
Is there a way to do this in or near ~10^8 or so operations?
