Thread: algorithms??

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    8

    algorithms??

    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
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Given your problem description, there is no "the path". For any given set of points, there are many possible paths through them.

    If your goal is to minimise the travel distance, then you are almost certainly talking about some variation of the travelling salesman problem, which is about finding the shortest path through all the points, and returning to the starting point.

    If there are some sets of points with no direct path between them, then you will probably need to identify subsets of points, solve the travelling salesman problem for each subset, and then string the paths together.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    Quote Originally Posted by grumpy View Post
    Given your problem description, there is no "the path". For any given set of points, there are many possible paths through them.

    If your goal is to minimise the travel distance, then you are almost certainly talking about some variation of the travelling salesman problem, which is about finding the shortest path through all the points, and returning to the starting point.

    If there are some sets of points with no direct path between them, then you will probably need to identify subsets of points, solve the travelling salesman problem for each subset, and then string the paths together.
    Firstly thanks for the reply. Yes my goal is to minimise the travel distance through all the points but there is no strict requirement for returning to the same point. I just want to travel through all the given points with minimum cost but i do have a condition of ending with the predefined end point. That is end point is fixed initially.
    If there are some sets of points with no direct path between them, then you will probably need to identify subsets of points, solve the travelling salesman problem for each subset, and then string the paths together.
    ...please do explain me about it in a bit easier way. I dint get what you meant by that.

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by en411 View Post
    ...please do explain me about it in a bit easier way. I dint get what you meant by that.
    It's probably a moot point since you are talking about a variant of the travelling salesman problem. I was just suggesting, given your statement that you have some points with no paths between them, that you might be able to break your problem into pieces.

    Unless you have some criteria that allows you to eliminate particular paths (i.e. heuristics) you probably have to do a brute-force search anyway.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Is it this, or could it be based on this?
    Hamiltonian path - Wikipedia, the free encyclopedia
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    A hamiltonian path problem is related to the hamiltonian cycle problem, which is a special case of the travelling salesman problem.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  7. #7
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    Is it necessary that in every network there exist a hamiltonian path?

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    No. The Hamiltonian path problem is about detecting if there is a hamiltonian path - or finding such a path - in a specified network (or, more accurately, and undirected graph).
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  9. #9
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    If there is no any hamiltonian path in the network it means that the network doesn't consist of any path that goes through all the points or is there a need of some other path finding algorithms in such case??

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    I don't know.

    I think you need to do quite a lot of reading on graph theory in general before coming to any particular conclusion.
    Once you know what kind of graph you have, and the kinds of path you need to obtain, then you should be able to identify some theorem which would underpin your implementation.

    We can help you with the code when you know what your primary references are (and have some code).
    But a lot of the primary research you will have to do yourself.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by en411 View Post
    If there is no any hamiltonian path in the network it means that the network doesn't consist of any path that goes through all the points or is there a need of some other path finding algorithms in such case??
    How carefully did you read the link Salem provided on Hamiltonian paths? The very first sentence of that article states (emphasis mine):
    Quote Originally Posted by Wikipedia - Hamiltonian path
    In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected graph that visits each vertex exactly once.
    I agree with Salem though, you need to better define your problem and do a little more reading.

  12. #12
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Can you please clarify this bit here:

    >> 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

    I'm a bit confused with the last part. You mean to say you must travel through each point only once?
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #13
    Registered User
    Join Date
    Sep 2012
    Posts
    8
    Quote Originally Posted by Mario F. View Post
    Can you please clarify this bit here:

    >> 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

    I'm a bit confused with the last part. You mean to say you must travel through each point only once?
    I was trying to explain in it that all the points may not have a connection to all other points in the network. I have sets of nodes and their connection nodes are fixed. I just need to find a path that travels through all the nodes without missing any of them. If its possible to find such path without node repetition then it would be great but it may not always be possible like in the case of dead end nodes. In such cases of dead end nodes there is surely a repetition of nodes. I just want to track a path that goes through all the nodes.

  14. #14
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by en411 View Post
    In such cases of dead end nodes there is surely a repetition of nodes.
    Okay, so each node must be visited at least once. Note that most algorithms assume the rule to be "each node is visited exactly once", which does impact the results.

    How many nodes and edges are we talking about? Roughly? What is the minimum and maximum number of edges connected to a single node? Is the graph clustered, or relatively uniform?

    Do you require the optimum (shortest) path, regardless of computation time (usually requiring a distributed algorithm, so you can run it in reasonable time on e.g. a cluster), or are you looking for an algorithm that will yield just a very good path?

  15. #15
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    @en411:
    It would help if you used proper terminology. Try this: Glossary of graph theory - Wikipedia, the free encyclopedia.

    Is it weighted? Is it directed or undirected? Is it guaranteed to be fully connected, or might it have disconnected components? What else you can tell us about the graph to help you figure out a good algorithm?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Algorithms
    By samtay in forum C++ Programming
    Replies: 2
    Last Post: 03-08-2004, 01:14 PM
  2. STL algorithms
    By PJYelton in forum C++ Programming
    Replies: 7
    Last Post: 11-12-2002, 03:27 PM
  3. any more algorithms ?
    By black in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 07-31-2002, 01:00 AM
  4. C Algorithms
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 09-28-2001, 02:59 AM