patternMinor
Shortest path with a start vertex that touches all nodes at least once with repeats allowed
Viewed 0 times
oncepathnodesallowedshortestvertexwithallrepeatsthat
Problem
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!
Solution
Your problem is just a TSP in disguise.
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.
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.
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.
- 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.
- 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.
- 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.
Context
StackExchange Computer Science Q#101566, answer score: 5
Revisions (0)
No revisions yet.