I’m working a little phone app for myself, and I’m hoping to get some
input on a problem I’m having.
This thing I’m working on is simply put a route planner, of sorts. I
give the app a start- and finish destination, the app then uses the
Nokia Places API to find specific
places in the area between these two points. What I then need to do, is
create a route from start to finish, that will also go through some of
these places (not all, like maybe 5-15 or so). This route should of
course be a ‘natural’ route, so that I don’t go to a place, and then
have go backwards to get to another place, etc.
I am not quite sure how to pick these places, but the idea I am
currently working with, is to get a plain route only from start to
finish, and then pick the places closest to sample points positioned at
(total_distance / num_stops) along the route. This would make the
route fairly predictable and boring, though.
Any ideas/suggestions for this? Is there some graph theory that can be
applied to this
Please log in or register to post a reply.
This is a shortest path problem, the solution is very well documented ,
and its regularly applied in games , the most famous algorithm is the
A* ( a star ) , google for pathfinding and you will get a lot of
The other thing that worries me most is the fact that these algorithm
uses a regular grid subdivision or a kind of data structure to compute
If you have access to data , at least postions of various locations,
you could use the A* with a set of points constructing a graph from
In the case this is not available , you should get the bitmap , detect
free logic pixels and use the A* to compute the path trhough the non
blocked logic pixels.
It’s not just pathfinding, as he needs to pick which places to visit and
what order to visit them in, not just how to get from given point A to
point B. It’s more like the traveling salesman problem. I’m not sure
what sort of algorithms people are using these days for that one, but
IIRC there are some efficient ones that will get you within a factor of
2 or so of the optimal solution, although finding the optimal one is
Why not simply use the genetic algorithm for the traveling salesman
problem? It’s very, very simple, and fast, and use little memory, and it
will give the optimal solution in no time and every time.
I was under the impression that tsp was used to visit all the locations,
and then returning to the start location, which is not quite what I want
right now (but might be, later).
I just want to go from A to B, through n points. I was looking at
geographic routing (http://en.wikipedia.org/wiki/Geographic_routing),
wihch is used in wireless networking, and seems promising.
TSP does not have to be a loop going from a to z then back to a. You
define the rule in the Fitness function as to how it goes.