# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
Our goal in using more than one type of random distribution was to assess if our method is sensible, and if so, to what extent, to variation in the type of edge costs involved. The results will show that the GEO instances are slightly harder to tackle, while UNI and GAU are more or less equivalent. ### Experiment 1: Best Move from a Random Tour

#### 5.2.1 Random Instances

In a first set of experiments we compared our method to the brute force (BF) approach on random instances of the type described before. In particular, for each type of random graph we generated instances of sizes \(n_{1},\ldots,n_{9}\) where we set \(n_{1}=400\) and \(n_{i+1}=\lceil\sqrt{2}\times n_{i}\rceil\) for \(i=1,\ldots,8\). This geometric increase is chosen so that we should see a doubling of the running times in going from \(n_{i}\) to \(n_{i+1}\) with a quadratic method, while the ratio should be about \(2\sqrt{2}\simeq 2.83\) with the cubic BF approach. For each given size \(n_{i}\) we generated 1000 random instances. Finally, for each random instance, we generated a random initial tour and found the best 3-OPT move with both smart force (SF) and BF. In Table 3 we report the results of the experiment. The table is divided vertically into three parts. The first part reports the average running time of the two approaches (columns BFavg and SFavg) and the speed-up achieved by smart force over brute force. We can see that in our instances smart force is at least 70 times faster and as much as 500 times faster than brute force. Similar results are reported in the second vertical part, in which we focus on the number of triples evaluated by the two methods. Clearly, the average for the BF method is indeed a constant, since all triples must be evaluated. SF, on the other hand, evaluates a much smaller number of triples, going from a minimum of 200 times less up to 7000 times less triples than BF. Notice how the saving in the running time is actually smaller than the saving in the number of triples evaluated. This is due to the overhead needed for building and updating the heap. The standard deviations for the SF times (not reported in the table for space reasons) were in the range 10-25% of the mean value, while for the number of evaluated triples the standard deviations were between 30% and 40%. In the final vertical section, we focus on the empirical estimate of a complexity function for the running time and the number of evaluated triples of the smart force approach. In particular, the column SFtime reports the ratio between the average time of SF on instances of size \(n_{k}\) and \(n_{k-1}\). Given the way that we defined the \(n_{k}\)'s, a value \(\simeq 2\) on this column would be indicative of a quadratic algorithm, while a value \(\simeq 2\sqrt{2}\simeq 2.83\) would be indicative of a cubic algorithm. The average ratios for the running time of the SF algorithm were 2.37, 2.31 and 2.47 for the UNI, GAU and GEO instances respectively. These values are indicative of an algorithm whose empirical average complexity is definitely sub-cubic, but not quite quadratic. A reasonably good fit with an experimental upper bound to the time complexity is \(O(n^{2.5})\) (see Figure 2). The column labeled SFeval reports the same type of ratios but this time relatively to the number of triples evaluated by SF. We can see that for UNI and GAU graphs the number of triples grows almost exactly as a quadratic function of \(n\). Notice that evaluating less than a quadratic number of triples would be impossible, since each edge must be looked at, and there is a quadratic number of edges. Again, the class of graphs GEO seems to be slightly harder than UNI and GAU. For completeness, in columns BFtime and BFeval we report the same type of values for the BF method. The main message from the table is that while finding the best 3-OPT move for a tour of about 6000 nodes with the classical BF approach can take more than half an hour, with our approach it can be done in 5 s or so.