@all i think all the above approaches are greedy.. we need dynamic solution to this problem..
On Sat, Feb 13, 2010 at 11:42 AM, vikrant singh <[email protected]>wrote: > @sachin : the problem is bit more complex , consider N be 2 , and > coordinates be (-2,0) (0,0) (1,0) (3,0). your solution( min value=1+5=6) > wont give the right answer(2+2=4). > > > On Sat, Feb 13, 2010 at 6:07 PM, sachin <[email protected]> wrote: > >> We can make a spanning tree for these 2N points and then find the >> minimum spanning tree >> keeping in mind that a node can only be considered in one edge and not >> more than once. >> This will give you the minimum total sum of all the pairs. >> You can use kruskal's min spanning tree algorithm to find the minimum >> spanning tree because >> kruskal's method works by finding the least cost edges & then >> proceeding towards the max cost edges. >> I hope it solves your problem. >> >> Regards, >> Sachin >> >> >> On Feb 12, 9:20 am, GentLeBoY <[email protected]> wrote: >> > given 2N points in a plane. Pair up to obtain N distinct pairs such >> > that total sum of paired distances is minimum. >> > N can be atmost 50. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Vikrant Singh > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Ankur Aggarwal Research internee Optical Zeitgeist Laboratory Institut National de la Recherche Scientifique (INRS) - ÉMT 800, de la Gauchetière Ouest, bureau 6900 Montréal, QC, H5A 1K6 CANADA E-mail: [email protected] Web: www.zeitgeistlab.ca -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
