Task: Find meeting point

Tags: | 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))

Comments (7) -

Admin United States on 3/13/2012 11:14 AM Firstly, this two dimensional problem can be reduced to two one dimensional problem. In the one dimensional problem, I can prove that the best spot must be one of these groups. In this way, I can give a O(G^2) algorithm.(G is the number of group).

Use iterator's example for illustration:

{(-100,0,100),(100,0,100),(0,1,1)},(x,y,population)

for x, {(-100,100),(100,100),(0,1)}, 0 is the best.

for y, {(0,100),(0,100),(1,1)}, 0 is the best.

So it's (0, 0)

Is there any better solution for this problem.
Chandan Giri India on 3/15/2012 9:20 AM O(M+N) algorithm by iterating x over 0 to M-1 to find x for which sum of distance is minimum and then same for Y.
Todd Smith United States on 3/27/2012 9:58 PM Make a function to calculate total cost of traveling to the meeting point:

cost(x,y) = 5sqrt( (x-2)^2+y^2 ) + 4sqrt( x^2 + (y-1)^2 ) + 3sqrt( (x-1)^2-(y-3)^2 );

then set each partial derivative equal to zero and solve the system (numerically) to get x=0.8793 and y=0.9483.
asdf India on 4/13/2012 8:55 PM It is the weighted average of the X,Y coordinates of the groups.The weights are the number of people
Tony Germany on 4/19/2012 1:11 AM @Admin I dont understand your answer. If the meeting point would be (0,0) then the cost of moving everyone to that would equal 26. (4((0-0)+(1-0))+3((1-0)+(3-0))+5((2-0)+(0-0))=4+12+10=26)
But If the meeting point is (1,1) the cost will be 20.

To find the (1,1) I just thought I would count how much it costs for every group to move to a location. So I counted that the cost for

(0,*)=13; (1,*)=9; (2,*)=11.

Obviously the first digit should be 1. After the same process for the second digit

(*,0)=13; (*,1)=11; (*,2)=17.

As well, here we see that the second digit should be 1 as well.
After combining them, we get the minimum cost in location (1,1) to be 20.
Vasyl Ukraine on 4/24/2012 4:47 PM I came to next solution:
Split to 2 similar tasks ( horisontal and vertical axises)
For each task:
Create additional array
For each group Put coordinate into array for amount of persons in group times
Find median with quicksort split
This is the answer on current axis

Array preparation takes O(n) times where n - amount of people
Median search - O( log n)

With some modifications it can be reduced to O(amount of groups) and even to O(log n) time (in case of using original data)

But it's 2AM now. )
Vasyl Ukraine on 4/24/2012 4:59 PM Mistake Not O( log n) - but O(n) time where n - amount of groups

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading