Finding the best path through at set of locations

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Apr 18, 2013 at 12:58

Hey all.

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

Cheers,
Kenneth

5 Replies

Please log in or register to post a reply.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Apr 19, 2013 at 08:46

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 examples.
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 the path.
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 those points.
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.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Apr 19, 2013 at 16:54

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 NP-complete.

88dc730f0f71e55be39de0ad103bd9ff
0
Alienizer 109 Apr 19, 2013 at 22:21

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.

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Apr 20, 2013 at 09:11

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.

88dc730f0f71e55be39de0ad103bd9ff
0
Alienizer 109 Apr 20, 2013 at 15:13

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.