pathfinding, special case...

blazer
Unregistered
 
Post: #1
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 start-node and ends at the end-node (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...
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
It's NP-complete, just like the traveling salesman problem. That means that, for large numbers of nodes, it's probably too expensive to find an absolute-best 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.
Quote this message in a reply
blazer
Unregistered
 
Post: #3
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?
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #4
Yes its got somthing to do with triangles..... Wacko
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!
Quote this message in a reply
Member
Posts: 208
Joined: 2005.04
Post: #5
Check out Dijkstra's algorithm and some of the other famous shortest path algorithms.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #6
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.
Quote this message in a reply
Moderator
Posts: 522
Joined: 2002.04
Post: #7
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
Quote this message in a reply
Moderator
Posts: 522
Joined: 2002.04
Post: #8
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
Quote this message in a reply
Member
Posts: 104
Joined: 2002.04
Post: #9
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.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  pathfinding for skating game in VC tenpenny 1 4,323 Sep 2, 2011 09:31 PM
Last Post: PoseMotion
  Maps Pathfinding Nodes jigzat 10 4,749 Jun 17, 2008 02:58 PM
Last Post: jigzat
  pathfinding crashes Iceman 5 4,306 Jul 28, 2005 05:48 PM
Last Post: unknown
  Pathfinding stevejohnson 6 3,684 Oct 28, 2004 01:20 PM
Last Post: igame3d
  Pathfinding? Blake 3 3,191 Jan 13, 2004 09:34 PM
Last Post: Blake