Hi Brett and Elena, I’d have to learn a little more about the problem to say something more precise, but this isn’t TSP. It sounds much more like a graph reachability / transitive closure / shortest path problem. There are O(n^3) or better solutions to all of those; really O(n^2) for the kinds of graphs I would expect to come from real streets. You can probable do better, depending on where you’re trying to route from or to.
Just ball-park guessing, I would expect an efficient implementation to take on the order of seconds for a 70,000 node graph. If you need millisecond response times, I expect you’ll need to have done some significant computation ahead of time. -Eric On Sep 3, 2014, at 5:23 AM, Elena Pop <elena0...@gmail.com> wrote: > Hi Brett, > > Hmm, it might not be a TSP problem as much as a data issue. The problem lays > in the graph that is created based on a shapefile that contains some not at > all useful information. That is why i am trying to work around of a faulty > input data. > > > > On Wed, Sep 3, 2014 at 3:44 AM, Brett Walker <brett.wal...@geometryit.com> > wrote: > HI Elena, > > > > A routing problem; it sounds like the classical travelling salesman problem > (TSP). (This assumption could be wrong) > > > > The TSP is O(c^n), c > 1 [exponential] using dynamic programming or O(n!) > [factorial] using brute force. Unless you have some sort of domain specific > metric to cut through the complexity of the TSP, in your case, an O(n*n) sort > is manageable. > > > > If you are getting results in milliseconds with ‘clean’ data then it sound > like you do have a domain specific metric to solve the TSP quickly. And the > O(n*n) sort is a problem. > > > > But then again the TSP assumption could be wrong and what I have said is a > bunch of tripe! > > > > Brett > > > > From: Frank van der Hulst [mailto:drifter.fr...@gmail.com] > Sent: Wednesday, 3 September 2014 4:31 AM > To: Elena Pop > Cc: geotools geotools-gt2-users@lists. sourceforge. net > Subject: Re: [Geotools-gt2-users] Remove the isolated arcs from a graph > > > > Hi Elena, > > I ran into this in my project too. > > My solution was to measure the distance from my tree to each of the candidate > LineStrings. Only if the distance is less than a specified threshold would > the new LineString be added. Depending on the quality of the source data, a > threshold of between 20m and 150m worked for me. You need that distance > anyway, because you need to find the nearest point of the tree to the new > LineString, so it will be added in the right place. You could even do a first > run through the data, deleting any LineString which doesn't connect to any > other LineString. But that will be another O(n*n) process. > > > > One thing I did to improve speed (although I am only looking at a few hundred > LineStrings at most) was to sort the list so that (usually) the best > candidate would be found early. Criteria for the sort were things like the > length of the candidate, the distance in the right direction, the distance > from the nearest point on the tree to the destination. > > Frank > > > > On Tue, Sep 2, 2014 at 8:58 PM, Elena Pop <elena0...@gmail.com> wrote: > > I am using a shapefile downloaded from OpenStreetMap in order to calculate a > route between two points. The graph created contains some isolated arcs that > are messing up my routing like these ones http://screencast.com/t/4jnQFx57 > > Is there any way i can remove them in a fast way, before or after the graph > creation? > > The way i am implementing the project is creating a List of linestrings read > from the shapefile and then iterating through the list and adding each > linestring to the graph. I did find a solution but it is not an optimal one > since it takes more than 1 hour to get results. > > My solution looks to count the number of occurrences of the first and he last > point of a linestring in the other linestrings and if one of the nOccurrences > is >1 the linestring will get added to the graph. > > Basically i will have to iterate twice through the list, but since the list > has more than 70000 linestrings it will do a O(n*n) program which will take > forever and i need to get results in ms not in hours. > > Is there other way that i can do this? > > > > > ------------------------------------------------------------------------------ > Slashdot TV. > Video for Nerds. Stuff that matters. > http://tv.slashdot.org/ > _______________________________________________ > GeoTools-GT2-Users mailing list > GeoTools-GT2-Users@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users > >
signature.asc
Description: Message signed with OpenPGP using GPGMail
------------------------------------------------------------------------------ Slashdot TV. Video for Nerds. Stuff that matters. http://tv.slashdot.org/
_______________________________________________ GeoTools-GT2-Users mailing list GeoTools-GT2-Users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
