Well take any traveling salesman problem : You are given a graph and required to find the shortest path from A to B that visits at all the nodes in the 'cities' subset at least once. Now create a new graph by adding node C and an edge BC. Now you choose your metric to be the length of each edge, except for BC. The metric for BC is 0 if the route travel included visits to all the cities, and very large (sum of all edges / infinite) otherwise. Now you have Stefan's problem. So finding an efficient solution for the general case looks very unlikely.
On Sun, Sep 21, 2008 at 9:18 PM, Marcus Wolschon <[EMAIL PROTECTED]>wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > Nic Roets schrieb: > > (So why didn't Stefan say that in the first place ...) > > > > The turn restriction problem is easy to solve once you realize that > > OSM nodes need not correspond to graph vertexes. The graph > > vertexes are states (search google for state machine). > > > > Let's say node N1 is part of one simple turn restriction relation > > W1,N1,W2 and one complicated turn restriction relation > > W3,N2,W4,N1,W5. Then we would associate 3 states with N1 : N1a : N1 > > was reached after traveling along W1. N1b : N1 was reached after > > traveling along W3, then N2, then W4. N1c : N1 was reached in some > > other way. > > > > And N2 will have at least 2 states associated with it. > > > Yes, that will work for me. Thanks for the idea! > Expand a node into a small graph with one-way > - -edges that represents the same rule. > > This however is my problem. Stefan has a different > issue. His metric depends on the metric of the path > used to reach the currently evaluated node. > > Marcus > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.4.6 (GNU/Linux) > Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org > > iD8DBQFI1p33f1hPnk3Z0cQRAtfTAJ4p73mDHfTnrfWkwI5cPskf78FVnwCeMYzd > WLWLzSTZAZ15NfBwfvg7qHI= > =B560 > -----END PGP SIGNATURE----- > > > _______________________________________________ > Routing mailing list > [email protected] > http://lists.openstreetmap.org/listinfo/routing >
_______________________________________________ Routing mailing list [email protected] http://lists.openstreetmap.org/listinfo/routing
