Inaccurate results for trivial problems about chinese-postman HOT 4 CLOSED

Actually that second route is the same as the first, just starting at a different point, going backwards and not returning to the start point. Not returning to the start point is what saves 1000.

from chinese-postman.

Thanks. What you say is true, but in the first (more expensive) case, the algorithm has to go back to the starting point in order to cover all lines. By doing that, it covers line [0,1] twice. In the second case, it doesn't have to return. So, it isn't/shouldn't be a requirement for the algorithm to return, but only to cover all lines in the shortest distance. Also, shouldn't the algorithm be able to find the best starting point automatically?

from chinese-postman.

I see what you mean, but I think you are defining a new problem then, because according to the Wikipedia-article on the Route inspection problem the path has to be closed:

[T]he Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph.

Still, interesting question you pose: What is the shortest route if closing the path is optional? I guess that you could just first find the closed path and then cut out the longest edge. That immediately defines the two starting/end points then.

from chinese-postman.

I understand -- I wasn't aware of that. Yes, that's how I implemented it. Thanks for your assistance!

from chinese-postman.