@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 <vikrantsing...@gmail.com>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 <sachin_mi...@yahoo.co.in> 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 <vikrantsing...@gmail.com> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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: ankur.1...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
