Suppose you live in a city with with various shops and boutiques, each belonging to a category $C_{i}$, where $i=0..n$, containing $N_{i}$ shops each. A shop is noted $s_{ij}$, the $j^{th}$ shop, in the $i^{th}$ category, and is geographically randomly distributed. For convenience, $S = \{C_{i}, i=0..n - 1 \} $

You're planning a category-based Sunday shopping. In other words, all categories ought to be visited only once, through one shop only. Any shop-pair $(s_{kj},s_{k'j'})$ can be connected with a straight line.

$V = (a,b,....) \in \mathbb N^{n}$ is a plausible path for your Sunday walk, i.e. $a^{th}$ shop in the first category, $b^{th}$ shop in the second category, etc..., and d(V), the length of that path.

Finding the minimum distance $$d(S) = min \sum_{}^S d(V)$$

Is it reducible to TSP? I have the gut feeling that yes, since the categories are in effect the network nodes. At the same time, the set of nodes realising the minimum distance is, by definition, unknown.

Note that the order in which categories are visited is part of the minimisation problem, otherwise the problem would be somewhat easier.

  • $\begingroup$ If you want $n$ categories, you need $i=0,\ldots,n-1$ or $i=1,\ldots,n$. (Good question though.) $\endgroup$ – TonyK Jan 31 '17 at 12:38
  • $\begingroup$ Yes, you have a point :) $\endgroup$ – Alex Jan 31 '17 at 14:16

This can be solved in polynomial time $O(nm^2)$ using dynamic programming (where $m$ is the maximum number of shops in a single category):

for each category i = 2,...,n
  for each shop s(i,j) in category i
    find the minimum-length partial path that ends at s(i,j),
    using the lengths already calculated for category i-1

Now just pick the minimum-length path over all s(n,j).

You only need to store the minimum partial-path lengths for two consecutive categories, which requires $\le 2m$ storage elements.

  • $\begingroup$ That works if you don't have to return home, it fits the description though. Weird, looks like the missing ingredient to make it TSP'esque is a closed loop. Thanks, I count it as the correct answer! $\endgroup$ – Alex Jan 31 '17 at 14:24
  • $\begingroup$ Actually, there is a dependence on the category order, so it's a minimum given the list C0, C1, .... Cn-1. Weirdly, as soon as one chooses the first category to visit, the algorithm leads to a global minimum, regardless of the permutations C1...Cn-1. $\endgroup$ – Alex Jan 31 '17 at 14:37
  • $\begingroup$ I don't get your "weirdly" comment. The algorithm can only find the minimum path for a given ordering of the categories. $\endgroup$ – TonyK Jan 31 '17 at 14:57
  • $\begingroup$ And if you want to return home, just add a final category containing your house. $\endgroup$ – TonyK Jan 31 '17 at 14:59
  • $\begingroup$ I doubt that, the last segment home isn't necessarily a minimum for d(S). Plus, you'd have a polynomial solution to the traveling salesman problem. Am I missing something ? $\endgroup$ – Alex Jan 31 '17 at 16:00

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.