Hi You can solve this by dynamic programming/memoization. Start off from the left and maintain two lists of points, one for forward traversal and one for reverse traversal. Each point would be in any one of the lists. When you encounter a point try putting it in each of the lists turn by turn and call the function recursively. You just need to maintain the heads of each of the lists. Once you memoize, the complexity would be O(n^3). The signature of the function would be:
int least_path( int current_position, int head_of_list1, int head_of_list2) -Dhyanesh On 3/30/07, Mahdi <[EMAIL PROTECTED]> wrote: > > Hello everyone! > We have n points in a chart that none of them have the same length(I > mean their 'x' parameter). We want to find a cycle with MINIMUM length > with these assumptions : > We start from the point with minimum length, meeting all of the points > and finally return to the starting point. We are allowed to change our > direction of moving only one time. I mean we go through more positive > points seeing some of them, and when we arrive to the rightest point, > we change our direction to the left, and seeing reminding points, > return to the starting point. > Let me give an example: > We have 3 points a,b,c : > a : x=2 y=0 > b: x=10 y=8 > c: x=17 y=0 > one possible cycle is : a-->b-->c-->a > another : a-->c-->b-->a > One of them is shorter than the another. > > thanks. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
