pathfinding, special case...
this pathfinding problem is a little different to others that are described on the net.
similar to travelling salesman  except for the fact that it starts at the startnode and ends at the endnode (different to start node).
the traveller has to start at the first node, go thru all nodes before ending at the final node  this must be done in the most efficient (shortest) manner possible.
how do i do this?
thanks all...
similar to travelling salesman  except for the fact that it starts at the startnode and ends at the endnode (different to start node).
the traveller has to start at the first node, go thru all nodes before ending at the final node  this must be done in the most efficient (shortest) manner possible.
how do i do this?
thanks all...
It's NPcomplete, just like the traveling salesman problem. That means that, for large numbers of nodes, it's probably too expensive to find an absolutebest solution. Depending on how general your network is, you may be able to find easy optimizations to make.
In terms of a basic algorithm, just try all possible paths and keep the shortest.
In terms of a basic algorithm, just try all possible paths and keep the shortest.
onesadcookie  nz huh, me in aus. anyway ... ummm isnt there a better way of doing it other than looking at all paths? a friend of mine said its got something to do with triangles ... do you know much about this bro?
Yes its got somthing to do with triangles.....
Just do it osc's way, It will work much faster than you expect unless you have hundreds of nodes then you should try and develop some heuristic.
Just do it osc's way, It will work much faster than you expect unless you have hundreds of nodes then you should try and develop some heuristic.
Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Check out Dijkstra's algorithm and some of the other famous shortest path algorithms.
those don't take into account the constraint that you must pass through every node.
the simple algorithm I suggested originally is about as good as it gets, without using some constraint on the problem to simplify the possibilities that need to be checked.
the simple algorithm I suggested originally is about as good as it gets, without using some constraint on the problem to simplify the possibilities that need to be checked.
An approach is to use A* to search for the best path of TSP while using the minimum spanning tree as the heuristic.
Wikipedia has info if you need.
Jon
Wikipedia has info if you need.
Jon
OneSadCookie Wrote:those don't take into account the constraint that you must pass through every node.
the simple algorithm I suggested originally is about as good as it gets, without using some constraint on the problem to simplify the possibilities that need to be checked.
If "as good as it gets" is equivalent to "brute force" ;)
Jon
There is no algorithm that can find the best path for all cases that will be faster than the brute force method. If you happen to discover one that works in all cases, I'll personally nominate you for the Truing award for this year.
This is a problem that computer scientists have been working on for many years. If your sample set is large enough to make checking every possibility untenable, then there are some heuristics you can use to approximate the shortest path. I guess the first thing I'd try is a modified A* type of thing that looks ahead a certain number of nodes to find the shortest paths in a greedy way. Really, what you have is a very difficult problem and not one that will be easily solved by a complete algorithm, other than the one OSC offered.
This is a problem that computer scientists have been working on for many years. If your sample set is large enough to make checking every possibility untenable, then there are some heuristics you can use to approximate the shortest path. I guess the first thing I'd try is a modified A* type of thing that looks ahead a certain number of nodes to find the shortest paths in a greedy way. Really, what you have is a very difficult problem and not one that will be easily solved by a complete algorithm, other than the one OSC offered.
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
pathfinding for skating game in VC  tenpenny  1  4,468 
Sep 2, 2011 09:31 PM Last Post: PoseMotion 

Maps Pathfinding Nodes  jigzat  10  4,947 
Jun 17, 2008 02:58 PM Last Post: jigzat 

pathfinding crashes  Iceman  5  4,474 
Jul 28, 2005 05:48 PM Last Post: unknown 

Pathfinding  stevejohnson  6  3,844 
Oct 28, 2004 01:20 PM Last Post: igame3d 

Pathfinding?  Blake  3  3,322 
Jan 13, 2004 09:34 PM Last Post: Blake 