On 04/06/2014 19:55, Henry Baker wrote:
BTW, I've never seen a mathematical characterization of what I call the "bicycle touring problem": the problem of riding for N miles on the most pleasant roads possible without repeats (or without significant repeats). The focus is on _links_, not _nodes_, and we want to maximize the pleasantness of the total trip, or perhaps minimize the maximum unpleasantness of the worst link.
The BTP may be closer to the Euler problem than the TSP.
This http://cstheory.stackexchange.com/questions/20682/is-the-longest-trail-probl... suggests that this problem is NP-complete despite its Eulerian-looking character. (I haven't read it carefully enough to be sure either that it's correct or that it really addresses your problem rather than another vaguely similar-looking one.) -- g