3
$\begingroup$

I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I believe). Maybe I am over thinking this though? I'm not looking for the fastest solution, but I fear a brute-force algorithm may take an extremely long time to perform this on a undirected graph with say 30 nodes. I'm personally trying to figure out on a video game the fastest way to traverse through every spawn point of a monster on a given zone (with a start point of course) so I can find him faster. I've already constructed a graph and figured out the distances assuming a complete graph. I guess on my part, one way to reduce the run time of such an algorithm is to remove realistically what edges wouldn't and probably wouldn't be included in a optimal path. I assume adding lots of constraints could help too. Might anyone know if there's a specific name for this problem, or if there is a simpler approach aside from just the standard brute-force? Thank you!

$\endgroup$
  • $\begingroup$ Can you clarify whether the path should go back to the start vertex? Are you interested in approximation algorithm? $\endgroup$ – John L. Dec 15 '18 at 12:14
  • $\begingroup$ From your description it is not clear why this is not a TSP problem. $\endgroup$ – Vincenzo Dec 15 '18 at 16:59
  • $\begingroup$ Sorry I should've said it explicitly. We don't want to go back to the start vertex, we just want to touch everything once! $\endgroup$ – Stawbewwy Dec 15 '18 at 19:07
4
$\begingroup$

Your problem is just a TSP in disguise.

1. Dealing with "visit each node at least once"

First, compute a modified distance matrix $D(i,j)$, $i,j=1,...,n$ using an all-pairs shortest path algorithm, such as the Floyd-Warshall algorithm. That is, you want $D(i,j)$ to be the shortest path length from node $i$ to node $j$. Using Floyd-Warshall you also compute a matrix $S(i,j)$ that gives the successor of $i$ on the shortest path from $i$ to $j$.

Now apply a TSP algorithm to the distance matrix $D$. This will give you a tour $T$ that goes through each node exactly once. You now expand each step of $T$ into a shortest path (you can do this using the matrix $S$). That is, if some step of $T$ goes from $i$ to $j$, you expand it into the shortest path from $i$ to $j$. Concatenating all these paths gives a tour $T'$ that visits each node at least once, with possible repeats. If $T$ is optimal for $D$, then $T'$ must be optimal for the original graph.

2. Dealing with "the tour does not need to return to the starting node"

Preprocess your graph as follows. Add a dummy node, node 0, such that the distance from 0 to the starting node $s$ is 0 and the distance from node 0 to any other node is $M := n \cdot \max_{i,j} D(i,j)$.

Now find a TSP tour on the modified graph using your TSP algorithm of choice. Because the value of $M$ is so large, any optimal TSP tour will be of the form $$ 0, s, \pi(1), ..., \pi(n-1), 0$$ where $\pi$ is some permutation of the nodes excluding the start node and node 0. Then the sequence $s, \pi(1), \ldots, \pi(n-1)$ represents your solution.

3. Exact vs heuristic

You can use any algorithm for the symmetric TSP problem. If $n$ is about 30, you will probably not be able to apply an exact (= optimal) TSP algorithm such as the Held-Karp dynamic programming algorithm. A very simple yet reasonable heuristic you might want to try is 2-OPT, which is straightforward to program. A branch-and-bound approach might also work well in practice.

$\endgroup$
  • $\begingroup$ I guess a question then to ask is, what's the last step to not return to the start node? $\endgroup$ – Stawbewwy Dec 15 '18 at 19:13
  • $\begingroup$ Thank you for the amazing details :) I wish I could upvote your answer, but I don't have enough reputation! $\endgroup$ – Stawbewwy Dec 16 '18 at 7:39

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.