5

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:

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?

Improve this question
4
  • this isn't homework, I promise. A friend of mine had a scavenger hunt with this as a riddle and the answer got us the next clue. That's why I already know the answer - but I'm still curious about an algorithm Commented Feb 26, 2013 at 15:12
  • 3
    Look up the Chinese Postman Problem, if I remember the problem name correctly. Commented Feb 26, 2013 at 15:29
  • An optimal path, if such exists is Eulerian path, which is easily found (unlike hamiltonian path, which is in the family of TSP) - so the problem probably has a polynomial time solution. Commented Feb 26, 2013 at 16:15
  • According to this paper, "Necessary and sufficient conditions for the existence of such a tour, an Euler tour, are simple: each node must be incident to an even number of edges." Since there are vertices with an odd number of edges incident, there is no Eulerian path and it is an instance of the Chinese Postman Problem, as Jan suggested. Commented Feb 26, 2013 at 20:37

2 Answers 2

Reset to default
3

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.
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

this is a good beginning but ultimately a wrong answer. What if there are four vertices with odd degrees but there are no edges between any two of them?
In this case, the algorithm can work. For more complicate case as Ali mentioned , it need to be improved to 'find out two vertices are with odd degree', if there is no direct edge between them. But I don't think there will be 'no edges' between them if they are in save graph.
I improved the algorithm according Ali's comments.
1

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 enter image description here 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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.