2
$\begingroup$

Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice.

For example, consider the following:

example

I have attempted to solve this by first performing a breadth-first search to find the shortest path from A to B, then from B to C, and so on, taking care to exclude any paths already found at each iteration.

This greedy solution works for most inputs, but in some case it will fail to find a solution, as the shortest path between two target nodes may end up blocking the complete path.

Aside from a brute-force approach, is it possible to find the shortest path that visits all of the target nodes, and is guaranteed to find such a path if one exists? Any suggestions on how to proceed?

$\endgroup$
  • $\begingroup$ In addition to what @D.W. said, I would suggest Lin-Kernighan heuristic $\endgroup$ – Sandro Lovnički Sep 1 '18 at 8:08
  • 1
    $\begingroup$ The solution you suggest isn't optimal. A shorter solution is to make the A-B path go north of D, like this. This gives cost 22, whereas your solution has cost 24. $\endgroup$ – David Richerby Sep 2 '18 at 7:58
  • $\begingroup$ @D.W. I'm not sure TSP algorithms will be much use: in this situation, the order of the cities is fixed and the difficulty is that we might need to pick a suboptimal route between one pair of cities to save space later on. $\endgroup$ – David Richerby Sep 2 '18 at 8:00
  • 1
    $\begingroup$ So a path is going from grid point to grid point, and the same grid point must not be used twice? $\endgroup$ – gnasher729 Jan 1 at 10:37
  • $\begingroup$ gnasher729's question is important. Knowing the points lie on a grid and the edges are the grid neighborhood relation allows more efficient solutions. $\endgroup$ – reinierpost Jan 31 at 16:48
0
$\begingroup$

I answered a more general problem a couple days ago. You simply want the destination pairs to be (a, b), (b, c), (c,d ),etc.

The gist is to translate the problem into a minimum-cost integer multi-commodity flow problem with a maximum capacity of $1$ per node, and one commodity between each pair of destinations.

$\endgroup$
  • $\begingroup$ You reduce this problem to minimum-cost integer multi-commodity flow problem, which is not sufficient to show this problem is NP-complete. $\endgroup$ – xskxzr Jan 1 at 4:45
  • $\begingroup$ @xskxzr Right. I removed that claim. $\endgroup$ – orlp Jan 1 at 11:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.