# Finding the Best 3-OPT Move in Subcubic Time
## 3 Speeding-Up the Search: The Basic Idea  
The goal of our work is to provide an alternative, much faster, way for finding the best move to the classical \"nested-for\" approach over all reinsertion schemes and indices, which is something like  
```
for(\(r=r_{1},r_{2},r_{3},r_{4}\)) for(\(i_{1}=0\);\(i_{1}\leq\bar{n}-4\);\(i_{1}\)++) for(\(i_{2}=i_{1}+2\);\(i_{2}\leq\bar{n}-2-\mathcal{P}(i_{1}=0)\);\(i_{2}\)++) for(\(i_{3}=i_{2}+2\);\(i_{3}\leq\bar{n}-\mathcal{P}(i_{1}=0)\);\(i_{3}\)++) evaluateMove(\((i_{1},i_{2},i_{3}),r\)); [' check if move is improving. possibly update best *]
```  
and takes time \(\Theta(n^{3})\). (The expression \(\mathcal{P}(A)\), given a predicate \(A\) returns \(1\) if \(A\) is true and \(0\) otherwise). As opposed to the brute force approach, we will call our algorithm the smart force procedure. Our idea for speeding-up the search is based on this consideration. Suppose there is a magic box that knows all the best moves. We can inquire the box, which answers in time \(O(1)\) by giving us a _partial move_. A partial move is the best move, but one of the selection indices has been deleted (and the partial move specifies which one). For example, we might get the answer \(((4,-,9),r_{2})\), and then we would know that there is some \(x\) such that the selection \((4,x,9)\), with reinsertion scheme \(r_{2}\), is an optimal move. How many times should we inquire about the box to quickly retrieve an optimal move? Suppose there are many optimal moves (e.g., the arc \(\{0,1\}\) costs \(1000\) and all other arcs cost \(1\), so that the move \(((0,x,y),r)\) is optimal for every \((x,y)\) and \(r\)). Then we could call the box \(O(n^{2})\) times \begin{table}
\begin{tabular}{c c c} \hline \hline
**n** & **2-OPT** & **3-OPT** \\ \hline
50 & 1175 & 69,000 \\ \hline
100 & 4850 & 608,000 \\ \hline
200 & 19,700 & 5,096,000 \\ \hline
500 & 124,250 & 81,840,000 \\ \hline
1000 & 498,500 & 660,680,000 \\ \hline
2000 & 1,997,000 & 5,309,360,000 \\ \hline
5000 & 12,492,500 & 83,183,400,000 \\ \hline
10,000 & 49,985,000 & 666,066,800,000 \\ \hline \end{tabular}
\end{table} 
Table 1: The number of true \(2\)-OPT and \(3\)-OPT moves for some \(n\). and get the reply \(((-,x,y),r)\) for all possible \(x,y,r\) without ever getting the value of the first index of an optimal selection. However, it is clear that with just one call to the box, it is possible to compute an optimal 3-OPT move in time \(O(n)\). In fact, after the box has told us the reinsertion scheme to use and the values of two indices out of three, we can enumerate the values for the missing index (i.e., expand the two indices into a triple) to determine the best completion possible. The bulk of our work has then been to simulate, heuristically, a similar magic box, i.e., a data structure that can be queried and should return a partial move much in a similar way as described above. In our heuristic version, the box, rather than returning a partial which could certainly be completed into a best move, returns a partial move which could likely be completed into a best move. As we will see, this can already greatly reduce the number of possible candidates to be best moves. In order to assess the likelihood with which a partial move could be completed into a best solution, we will use suitable functions described in the next sections. Since there is no guarantee that a partial move suggested by our box can be indeed completed into an optimal move, we will have to iterate over many suggestions, looking for the best one. If there are \(O(n)\) iterations, given that each iteration costs us \(O(n)\) we end up with an \(O(n^{2})\) algorithm. Some expansions will be _winning_, in that they produce a selection better than any one seen so far, while others will be losing, i.e., we enumerate \(O(n)\) completions for the partial move but none of them beats the best move seen so far. Clearly, to have an effective algorithm we must keep the number of losing iterations small.