Tags: algorithm |
Posted by
Admin on
3/13/2012 11:11 AM |
Comments (7)
There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.
Group1: (0, 1), 4
Group2: (1, 3), 3
Group3: (2, 0), 5
. 4 . .
. . . 3
5 . . .
If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))