CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: algorithms??

  1. #1
    Join Date
    Sep 2012
    Posts
    10

    algorithms??

    i need to a coding in C++.I am trying to do problem in which i have numbers of points. Now i need to find the path that goes through all the points. This is not actually TSP because as per my knowledge in TSP it is possible to travel from all points to every other points. But in my case the path network is fixed and i just need to find the path that goes through all the points provided that all points may not have connection to every other point..so what algorithm am i supposed to follow.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: algorithms??

    Quote Originally Posted by en061 View Post
    ..so what algorithm am i supposed to follow.
    The problem is to find a Hamiltonian Circuit in a graph, that is a path which visits every point (vertice) once. This is an NP-hard problem just like the TSP.

    I'm not sure whether there are polynominal time algorithms available for restricted problems. But if not all points are connected this at least should reduce the running time in practice.

    The most straightforward approach is recursion I think. You start at any point and from it you visit every available point one by one. This is then repeated recursively for each point you reach. You must keep track of the current path because you need to know which points you've already visited. If you cannot go anywhere from a point the recursion backtracks (rewinds to the previously visited point and continues there). When all points are in the current path and you can reach the starting point from where you are, you've found a Hamiltonian path.
    Last edited by nuzzle; December 2nd, 2012 at 05:12 AM.

  3. #3
    Join Date
    Sep 2012
    Posts
    10

    Re: algorithms??

    Quote Originally Posted by nuzzle View Post
    The problem is to find a Hamiltonian Circuit in a graph, that is a path which visits every point (vertice) once. This is an NP-hard problem just like the TSP.

    I'm not sure whether there are polynominal time algorithms available for restricted problems. But if not all points are connected this at least should reduce the running time in practice.

    The most straightforward approach is recursion I think. You start at any point and from it you visit every available point one by one. This is then repeated recursively for each point you reach. You must keep track of the current path because you need to know which points you've already visited. If you cannot go anywhere from a point the recursion backtracks (rewinds to the previously visited point and continues there). When all points are in the current path and you can reach the starting point from where you are, you've found a Hamiltonian path.
    Thanks for the reply...
    If you cannot go anywhere from a point the recursion backtracks (rewinds to the previously visited point and continues there)
    so when such situation arrives then how to proceed further again?? Will it be able to give a solution if we proceed in the way that you mentioned or is it going to be trapped somewhere?? You have any idea about that??

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: algorithms??

    Quote Originally Posted by en061 View Post
    Thanks for the reply... so when such situation arrives then how to proceed further again?? Will it be able to give a solution if we proceed in the way that you mentioned or is it going to be trapped somewhere?? You have any idea about that??
    It won't get trapped. It systematically explores the graph generating all possible point combinations (path sequences) and thus finds all Hamilonian paths (if there are any and if you let it continue until it finishes). The same approach can be used for similar problems such as The Eight Queen Puzzle, The Towers of Hanoi and even Sudoku. When the full combinatorial search is reduced through restrictions it's often called a branch-and-bound algorithm.

    If you search the internet you should be able to locate implementation code. This problem is quite common as an exercise in algorithms courses.
    Last edited by nuzzle; December 3rd, 2012 at 10:33 AM.

  5. #5
    Join Date
    Sep 2012
    Posts
    10

    Re: algorithms??

    So which is better....to find the Hamiltonian path for the network or to use the branch and bound algorithms to find the path?? Which one guarantees of finding a proper path that visits every vertex of the network?? Any idea?

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: algorithms??

    Quote Originally Posted by en061 View Post
    So which is better....to find the Hamiltonian path for the network or to use the branch and bound algorithms to find the path?? Which one guarantees of finding a proper path that visits every vertex of the network?? Any idea?
    There seems to be a misunderstanding here. The Hamiltonian path is what you're looking for. The recursive branch-and-bound algorithm is what I suggest you use to find it.

    There may be more efficient algorithms available but the one I suggested will work. It's simple and straightforward to implement and I'm sure you can find code for it if you just search the internet.

  7. #7
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: algorithms??

    Quote Originally Posted by en061 View Post
    i need to a coding in C++.I am trying to do problem in which i have numbers of points. Now i need to find the path that goes through all the points. This is not actually TSP because as per my knowledge in TSP it is possible to travel from all points to every other points. But in my case the path network is fixed and i just need to find the path that goes through all the points provided that all points may not have connection to every other point..so what algorithm am i supposed to follow.
    I assume this is the same problem as posted here: http://cboard.cprogramming.com/tech-...lgorithms.html
    However, there you (assuming that's you) say you want to minimize the distance, but that you only need a path and not a cycle. If that's the case, you can model it as a TSP by introducing another node that is connected to all the existing nodes with costless arcs (i.e. distance = 0). In the cycle that you find, the special node will be connected to the begin and end point of your path with minimum distance. If you need specific begin and end points, then you can connect the special node to these nodes only.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  8. #8
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: algorithms??

    If you have a restriction that no single node or no single path can be visited again, then it is not guaranteed there even are solutions.

    If the network has more than 2 'dead ends' you can immediately state a solution is not possible under those terms.
    if it has 2 'dead ends' then you can equally state that any solution would be required to start in one dead end and end in the other.
    if it has 1 'dead end' it needs to be either the start or the end of a solution.

    ---
    Whether paths or nodes can be reused doesn't really change the problem domain.

    ---
    Pure TSP can be mapped (this has been proven) onto a the hamiltonian circuit. If you can proove there is a linear time solution for either, you can proove there is a linear time solution for the other.

    ---
    If nodes/paths CAN be revisited, this too can be mapped onto TSP. So solving either in linear time solves the other as well.


    ---
    There are to date no linear time algorithms for TSP.
    There are several algorithms that find 'reasonably optimal' paths very fast or 'near optimal' paths in reasonable amounts of time. None of these algoritms are trivial.
    You can however (dis)proove a specific path is optimal in linear time. To date no algorithm can generate all possible paths in linear time.

  9. #9
    Join Date
    May 2009
    Posts
    2,413

    Re: algorithms??

    Quote Originally Posted by OReubens View Post
    There are to date no linear time algorithms for TSP.
    There isn't even a polynominal algorithm available. If there were then all NP-hard problems could be solved in P and that would mark the beginning of a new era for mankind. The P vs. NP problem is the first of the Millennium Prize Problems,

    http://en.wikipedia.org/wiki/Millennium_Prize_Problems

  10. #10
    Join Date
    Sep 2012
    Posts
    10

    Re: algorithms??

    There are several algorithms that find 'reasonably optimal' paths very fast or 'near optimal' paths in reasonable amounts of time. None of these algoritms are trivial.
    ...can you name some?? some algorithms that would travel through all the given points and also optimise the cost of travel ?

  11. #11
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: algorithms??

    All these algorithms are a tradeoff between CPU time, memory, and accuracy. For a general discussion about it, look up TSP on wikipedia, it references several generalized solutions.


    for small sets, you can have a reasonably fast optimal "brute force" or "semi brute force" approach. I have used this in the past to solve sets of 50-60 vertices (on a sparse network) within a few minutes at most.

    If you have a network with dead ends, you can reduce the problem by pruning all the dead ends, solving the problem for the pruned network (visiting the entry points towards the dead end), and then solving an optimal path going in and leaving for each dead end individually. then merging the subsolutions.
    This approach is what made the above 50-60 possible, since there were typically about 30% vertices that were part of a dead end or a dead end pocket. If you can't prune anything, you will find that 50-60 will likely already take many days to solve with a brute force approach.


    TSP-like problems have been "solved" adequately with many different approaches. Most revolve around picking a random path then incrementally improving it. by either swapping pairs, or even swapping entire subpaths. ANd even in those approaches there are many different ways to do things.
    you have to make a choice between how close to optimal is acceptable to you, and how much running time you want to allow to reach that, and how much memory can you devote to it. Many approaches also give early "close" solutions and allow the user to either pick that or continue running for a maybe better solution.

  12. #12
    Join Date
    May 2009
    Posts
    2,413

    Re: algorithms??

    Quote Originally Posted by en061 View Post
    ...can you name some??
    There are two common major approaches: Approximation algorithms and Genetic algorithms.

    Approximation algorithms try to reformulate the original NP-hard problem to a problem that can be solved in polynominal time. A gurantee is given to how far from optimum of the original problem they will be in the worst case but in practice it's usually much better than that.

    Genetic algorithms attack the original NP-hard problem probabilistically in the hope that chance will evolve towards optimum. There are no performance guarantees but in practice they usually get very close very fast.

    There are plenty of textbooks on this, often with information on where to find code libraries.

  13. #13
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: algorithms??

    For example, the eight-queens problem (or, more generally N-queen's problem) can be heuristically solved by conflict minimization (see article) with extreme efficiency.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  14. #14
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: algorithms??

    If you have some interest in this, I strongly recommend Russell and Norvig's excellent book on AI (title is Artificial Intelligence: A Modern Approach) which explore some methods of efficiently searching for solutions.
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured