# algorithms??

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-01-2012
en411
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.
• 12-01-2012
grumpy
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.
• 12-01-2012
en411
Quote:

Originally Posted by grumpy
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.
Quote:

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.
• 12-01-2012
grumpy
Quote:

Originally Posted by en411
...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.
• 12-02-2012
Salem
Is it this, or could it be based on this?
Hamiltonian path - Wikipedia, the free encyclopedia
• 12-02-2012
grumpy
A hamiltonian path problem is related to the hamiltonian cycle problem, which is a special case of the travelling salesman problem.
• 12-02-2012
en411
Is it necessary that in every network there exist a hamiltonian path?
• 12-03-2012
grumpy
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).
• 12-04-2012
en411
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??
• 12-04-2012
Salem
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.
• 12-04-2012
anduril462
Quote:

Originally Posted by en411
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-05-2012
Mario F.
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?
• 12-06-2012
en411
Quote:

Originally Posted by Mario F.
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.
• 12-06-2012
Nominal Animal
Quote:

Originally Posted by en411
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?
• 12-06-2012
anduril462
@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?
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last