When we measure complexity or effectivenes of various k-opt optimizations, then 2-opt has weight of two, since by definition it exchanges two pairs of links, 3-opt exchanges three pairs of links, 4-opt exchanges four pairs, 5-opt exchanges five pairs and so on. But quite different image appears when we focus on number of pair exchanges, that is the number of basic transformations of tour required to make given type of k-opt move.
| move | pairs exchanged | exchanges made |
|---|---|---|
| 2-opt | 2 | 1 |
| 3-opt | 3 | 2 or 3 |
| 4-opt | 4 | 3 |
| 5-opt | 5 | 4 or 5 |
As we can see from this table 3-opt should be much better than 2-opt since it makes two or even three pair exchanges instead of only one. Then we expect that 4-opt would be somewhat better than 3-opt, but much less than 3-opt is better than 2-opt. The reason is that 3-opt already includes three possible exchanges and 4-opt adds no more exchanges, even though it provides more various cases. In contrast to this 5-opt involves four or even five exchanges, then more then 4-opt. This should make 5-optimization much better than 4-optimization, more than 4-optimization is better than 3-optimization. In fact this is seen in practice, therefore hardly any implementation uses 4-opt as its best method. Almost all implementations use either 3-opt or 5-opt.
No comments:
Post a Comment