Data Structures, Algorithms, & Applications in C++
Chapter 20, Exercise 3
Define a directed graph with as many vertices as the number
of
balls on Mary's side of the court plus 1.
One of these vertices
represents the location of the basket and each of the remaining vertices
represents the location of a ball.
The digraph is a complete digraph and the length of the edge
(i,j) is the distance between
the locations represented by the vertices i
and j.
The solution to the traveling salesperson problem defined on this digraph
gives us the shortest route Mary can take to pick up the balls on her
side of the court.
For Joe's side of the court, we can define an analogous traveling
salesperson problem. So by solving two traveling salesperson
problems, we can find the order in which Mary and Joe should pick
up balls so that they walk the minimum distance.