Given are a number of ordered nodes in a bidirectional graph with known only positive cost for each edge.
I need to find the shortest path through the given nodes in the particular order that are given while never using any edge twice.
So in contrast to Travelling Salesman problems, I know the order of traversal.
However, the last requirement is key here. Due to not being able to use any edge twice, the locally optimal path between node 1 and 2 could create a suboptimal path between 2 and 3 and so on or even make a complete path impossible.
Right now, I am using A-Star in succession to build the total path, but it is clear that this is not optimal.
So, is there a way to find the global optimum over all given nodes (if it exists at all) by looking at all of them at the same time to find the optimal path?
Best Answer
Even finding out whether there is a solution at all is NP-complete. I will show this by reducing from 3SAT.
Given a 3SAT instance, create a copy of the following 18-node network for each 3-literal clause:
The edges $Y_1\leftrightarrow Z_1$, $Y_2\leftrightarrow Z_2$, and $Y_3\leftrightarrow Z_3$ represent the literal; the connections to the $Y_i$ and $Z_i$ nodes will be made later.
The nodes $A, B, C, D, E, F$ must be visited in that order. The edge going to the right from $F$ connects to the $A$ of the next clause.
The part of the path that visits $ABCDEF$ must use at least one of the $Y_i\leftrightarrow Z_i$ edges. Because $C$ must be visited, at least two of $X_1 X_2 X_3$ must be visited by this part of the path; this prevents any part of the path outside $ABCDEF$ from entering the $BCX_1X_2X_3$ network. (The rules imply that a node of degree $\le 3$ can be used at most once). Similarly on the other side of the fragment, no part of the path outside $ABCDEF$ can enter the $W_1W_2W_3DE$ network.
In addition to these clause networks, for each variable $x_n$ in the 3SAT problem have nodes $P_n, Q_n$ that must be visited in this order. Add a path from $P_n$ to $Q_n$ that passes through all the $Y_iZ_i$ edges for $x_i$ literals (connecting each $Z_i$ to the $Y_i$ of the next instance of $x_i$), and another path from $P_n$ to $Q_n$ that passes through all of the $\neg x_i$ literals. Because the $X_i$ and $Y_i$ nodes are not available outside the $ABCDEF$ segments, these two full paths will be the only ways to get from $P_n$ to $Q_n$.
Finally add connecting edges from each $Q_n$ to $P_{n+1}$, from the last $F$ to $P_1$, etc.
Now a path that passes through everything in order and does not reuse edges will correspond to a satisfying truth assignment, with each variable's truth variable determined by the path from $P_n$ to $Q_n$ we don't take. And in each clause there must be at least one of the literals that have the right truth value.