Algorithm for shortest path through all edges

Question

Here's an interesting problem/riddle a friend asked me recently:

You are painting the lines of a tennis court. You have a machine to paint straight lines, but once it is turned on, you can't stop it until the job is done. Clearly you will need to go over some lines twice. What is the smallest amount of extra paint you have to use, in feet?

The dimensions of a court:

The sum of all lines is 480ft. I happen to know that the answer is 63ft extra (543ft total), but I can't help but wonder what the best algorithm is to solve this.

It seems similar to the traveling salesman problem, where each line on the court is represented by a vertex in a graph and junctions of court-lines translate to edges. (Otherwise, if lines were edges and corners were vertices, it would require a path that goes through all edges, and I don't know of any algorithms for that). Maybe you need to be more clever about how junctions of lines are represented and I have some ideas about that, but nothing has really worked yet.

I think the problem is small enough, though, that it can be brute-force-checked with all paths through the line graph. How would you code that?

Answer 1

An undirected graph has an Eulerian trail if and only if at most two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component. （ Found from http://en.wikipedia.org/wiki/Eulerian_path ）

When we get a non-Eulerian graph, we can change it to an Eulerian by adding edges to the odd degree vertices. So, this problem is turned to: find the lowest cost to turn the graph to a Eulerian.

The algorithm should be:

1. list all vertices with odd degree , suggest it is a list_vodd[];
2. find the shortest edge between the vertices in list_vodd[], get two vertices of the edge: pa, pb;
3. add an edge between pa,pb ( which means this edge should be paint twice );
4. delete pa,pb from list_vodd[];
5. goto 2 until there are only two vertices in list_vodd[].
6. use any existing algorithm to find out a Eulerian router in the new graph with the added edges.

Answer 2

I'm a little late to the game here, but I came across this when I was trying to find an algorithm to determine the shortest path to hike every trail in a state park. Here's a sketch that explains why the answer is 63 As Richard mentioned, this is a Chinese Postman problem. Since the problem didn't specify that we have to start and end in the same location we can use a semi-eulerian graph, which is why all the nodes have an even number, except the start and end points which share a common edge.

Here is a very nice video that explains how to graph and solve this type of problem. https://www.youtube.com/watch?v=spaUY8PlyYA