Studies on probabilistic analysis of λ-opt for traveling salesperson problems 巡回セールスパーソン問題に対するλ-optの確率的解析に関する研究
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
Studies on probabilistic analysis of λ-opt for traveling salesperson problems
- タイトル別名
-
巡回セールスパーソン問題に対するλ-optの確率的解析に関する研究
- 著者名
-
岡田, 正浩
- 著者別名
-
オカダ, マサヒロ
- 学位授与大学
-
奈良先端科学技術大学院大学
- 取得学位
-
博士(工学)
- 学位授与番号
-
甲第48号
- 学位授与年月日
-
1999-03-24
注記・抄録
博士論文
目次
- 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)