Studies on probabilistic analysis of λ-opt for traveling salesperson problems 巡回セールスパーソン問題に対するλ-optの確率的解析に関する研究

Access this Article

Title: Studies on probabilistic analysis of λ-opt for traveling salesperson problems

博士論文

Studies on Probabilistic Analysis of λ-opt for Traveling Salesperson Problems / p1 (0003.jp2)
Contents / p9 (0007.jp2)
1 Introduction / p1 (0011.jp2)
1.1 Historical background of the TSP / p1 (0011.jp2)
1.2 Research objective and outline of the thesis / p3 (0012.jp2)
2 Problem Definition and Some Solution Methods / p5 (0013.jp2)
2.1 Problem definition and related problems of the TSP / p5 (0013.jp2)
2.2 Complexity and approximation algorithms of the TSP / p7 (0014.jp2)
2.3 Constructive methods / p7 (0014.jp2)
2.4 Local search methods / p11 (0016.jp2)
2.5 λ-opt / p12 (0017.jp2)
3 Probabilistic Analysis of 2-Opt for Traveling Salesperson Problems / p15 (0018.jp2)
3.1 Introduction / p15 (0018.jp2)
3.2 Preliminary / p16 (0019.jp2)
3.3 Probabilistic model / p17 (0019.jp2)
3.4 Experimental results / p32 (0027.jp2)
3.5 Discussions on the function νκ(t) / p37 (0029.jp2)
3.6 Conclusion and future issues / p43 (0032.jp2)
3.A Derivation of equation(3.12) / p45 (0033.jp2)
4 Probabilistic Polynomial Behavior of λ-opt for Traveling Salesperson Prob-lems / p47 (0034.jp2)
4.1 Introduction / p47 (0034.jp2)
4.2 Number of iterations of λ-opt / p47 (0034.jp2)
4.3 Probabilistic polynomial behavior of λ-opt / p51 (0036.jp2)
4.4 Random Euclidean TSP / p56 (0039.jp2)
4.5 Conclusion / p69 (0045.jp2)
4.A Proof of Lemmas 4.4.1 and 4.4.2 / p69 (0045.jp2)
5 Conclusion / p77 (0049.jp2)
Appendix / p79 (0050.jp2)
A.1 Graph theory / p79 (0050.jp2)
A.2 Complexity theory / p80 (0051.jp2)

9access