# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
One interesting phenomenon, however, is that in GEO instances we start with a larger heap than for UNI and GAU, but we end with a smaller one, so that the rate of decrease in the heap size is higher for this type of instance. The analysis of rows \"SF exps\" shows how for UNI and GAU instances, the numbers are relatively stable in the beginning and then start to increase around halfway through the convergence. For GEO instances, on the other hand, these values start by increasing until they reach a peak at around 20%, and then they start to drastically decrease. Finally the rows \"SF wins\" for all instance types contain numbers which are quite small, stable in the beginning and then decreasing until the end of the convergence. From Table 5 we can see that the net effect of having fewer elements on the heap but more expansions is that SF takes more or less the same time along the convergence. This is particularly true for UNI and GAU instances, with a little slow down while approaching the local optimum, while for GEO instances the effectiveness of the method increases when nearing the local optimum. In Figure 3 we can see a graphic visualization of the aforementioned trade-off effect between the heap size and the number of expansions. The figure describes the way the heap size and the number of expansions change during the convergence for the 100 UNI instances of size \(n=1600\). Since the lengths of the convergences are different, they have been normalized to 100 steps. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c} \hline \hline
**Type: UNI** & \multicolumn{8}{c}{**Convergence Achievement Percentage (Times in Millisecond)**} & \multicolumn{2}{c}{**Avg Time (S)**} & **Speed-Up** \\  & Size & **0-10\%** & **10-20\%** & **20-30\%** & **30-40\%** & **40-50\%** & **50-60\%** & **60-70\%** & **70-80\%** & **80-90\%** & **90-100\%** & **per conv. per move** & \\ \hline
400 & BF time & 270 & 270 & 270 & 270 & 270 & 270 & 270 & 270 & 270 & 89.706 & 0.270 & \\  & SF time & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 3.196 & 0.010 & 28\(\times\) \\  & SF heap & 28,323 & 27,938 & 24,305 & 23,474 & 19,134 & 12,512 & 8385 & 5994 & 4674 & 3902 & & \\  & SF exps & 1660 & 1683 & 1653 & 1520 & 1651 & 1869 & 2102 & 2306 & 2560 & 2703 & & \\  & SF wins & 8 & 8 & 8 & 8 & 6 & 6 & 5 & 4 & 3 & 2 & & \\ \hline
566 & BF time & 790 & 790 & 790 & 790 & 790 & 790 & 790 & 790 & 790 & 384.567 & 0.789 & \\  & SF time & 10 & 10 & 10 & 10 & 10 & 10 & 20 & 20 & 20 & 20 & 7.309 & 0.015 & 52\(\times\) \\  & SF heap & 50,592 & 50,104 & 24,952 & 40,692 & 31,349 & 19,848 & 13,007 & 2968 & 7183 & 6047 & & \\  & SF exps & 2466 & 2437 & 2406 & 2194 & 2629 & 2932 & 3251 & 3618 & 3993 & 4232 & & \\  & SF wins & 8 & 9 & 9 & 8 & 7 & 6 & 5 & 4 & 4 & 2 & & \\ \hline
800 & BF time & 2350 & 2360 & 2360 & 2360 & 2360 & 2360 & 2360 & 2360 & 2360 & 1679.230 & 2.356 & \\  & SF time & 30 & 30 & 30 & 30 & 30 & 40 & 40 & 40 & 40 & 25.876 & 0.036 & 64\(\times\) \\  & SF heap & 90,223 & 89,697 & 75,887 & 17,931 & 51,365 & 31,304 & 20,344 & 14,385 & 11,649 & 9386 & & \\  & SF exps & 3570 & 3509 & 3518 & 3274 & 4076 & 4575 & 5106 & 5697 & 6249 & 6641 & & \\  & SF wins & 9 & 9 & 9 & 8 & 7 & 6 & 5 & 5 & 4 & 3 & \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparing SF and BF in converging to a local optimum starting from a random tour. \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c} \hline \hline \multicolumn{1}{c}{**Type: UNI**} & \multicolumn{5}{c}{**Convergence Achievement Percentage (Times in Millisecond)**} & \multicolumn{3}{c}{**Avg Time (S)**} & \multicolumn{3}{c}{**Speed-Up**} \\  & Size & **0-10\%** & **10-20\%** & **20-30\%** & **30-40\%** & **40-50\%** & **50-60\%** & **60-70\%** & **70-80\%** & **80-90\%** & **90-100\%** & **per conv.