10228 - Star not a Tree?

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

10228 - Star not a Tree?

Post by Shahab »

Any idea to solve such a problem, plz?

I have the idea of derivation of the sum of the distances, but it is really hard and unamusing to code.

Thanks in advance

User avatar
Trickster
New poster
Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

10228 - A star not a tree?

Post by Trickster »

Hi everyone,

i
"There's a difference between knowing the path, and walking the path."

zac.friggstad
New poster
Posts: 5
Joined: Tue Jun 14, 2005 7:12 pm

Post by zac.friggstad »

Hi,

I know this is an old post, but maybe this will still be helpful. Your method is incorrect. Using the centroid will not give the minimum value for the sum of all the distances. (It might be for the sum of the squares of the distances... I would have to think about it more).

How is your multivariate calculus? Think of how you can form a system of 2 equations over two unknowns f(x,y)=0 and g(x,y)=0 where (x,y) represents the location of the hub. Then look up some methods on solving these systems numerically (i.e. not necessarily an exact solution, but close enough for what the problem asks for). The centroid is a good initial approximation for a numerical method, but not the solution. I had my solution accepted on the first try.

Good Luck!

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

:lol:

iggy
New poster
Posts: 3
Joined: Mon May 05, 2008 10:44 am

Re: 10228 - A Star not A Tree

Post by iggy »

Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?

Post Reply

Return to “Volume 102 (10200-10299)”