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
>
>
>
------------------------------------------------------------------------------
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
