1
$\begingroup$

Consider the following problem:

There are $n$ points in the plane. Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way that minimizes the cost of the total path.

The weight of each edge changes depending on the path followed. For example imagine $n=3$: $A$, $B$, $C$ and we start at $A$. The weight of the edge $xy$ is $Sd_{xy}$, where $d_{xy}$ is the distance between the points $x$ and $y$ and $S$ is a given constant) If I pick the edge $A\to B$, the weight of the edge $B\to A$ is now $(S-s_B)d_{AB}$ because $B$ changes $S$ by a constant amount $s_B$. Similarly if I pick the edge $A\to C$, the weight of the edge $B\to C$ is now $(S-s_C)d_{AC}$ because visiting $C$ changes $S$ by a constant amount $s_C$.

Developing the $n=3$ case, imagine S=11, $d_{AB}=5,d_{AC}=3,d_{BC}=4$ and $s_{A}=2,s_{B}=5,s_{C}=4$. Then there are 4 possible paths:

A->B->C->A with cost $11*5+(11-5)*4+(11-5-4)*3$

(we stop once we reach A because 11-5-4-2=0)

A->B->A->C with cost $11*5+(11-5)*5+(11-4-2)*3$

A->C->B->A with cost $11*3+(11-4)*4+(11-4-5)*5$

A->C->A->B with cost $11*3+(11-4)*3+(11-4-2)*5$

For $n=4$ there will be 3*3!=18 possible paths and so on.

I know that $s_A+s_B+s_C=S$. This generalizes for $n$ points. What is an efficient algorithm for finding the minimum cost path?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Shouldn't Euclidean TSP reduce to this pretty straightforwardly? $\endgroup$ – G. Bach Oct 24 '13 at 2:07
  • $\begingroup$ Please give a more precise definition of the problem. Definition by example ends up being vague, especially when you give two identical examples of everything. Does using edge $xy$ change the weight of every edge in the graph according to the value of $s_y$? Does it change the weight only of the edges that aren't in the path built so far? Or does it only change the weight of the edge $y\to x$, as suggested by your examples? (The last would have no effect, since the edge $y\to x$ can't be used, since $x$ and $y$ have both already been visited.) $\endgroup$ – David Richerby Oct 24 '13 at 9:26
  • 1
    $\begingroup$ The edit, by a different user, has introduced paths that visit a vertex more than once. Is this supposed to be allowed? $\endgroup$ – David Richerby Oct 24 '13 at 15:20
  • $\begingroup$ Yes we have to visit the starting node A twice so that we make S−$\sum_{i}s_{i}=0$. (so yes $\sum_{i}s_{i}=S$). $\endgroup$ – deb Oct 25 '13 at 2:54
  • $\begingroup$ @deb "There are n points in the plane. Starting from one of them I want to visit each of them once but in a way that minimizes the cost of the total path." This says nothing about visiting the start node twice. And it certainly doesn't suggest that a path $A\to B\to A\to C$, as introduced in the edit, is allowed. $\endgroup$ – David Richerby Oct 25 '13 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.