グラフ理論は頂点と辺の集合で表されるグラフを用いて、そのグラフについて様々な問題を解く。そして、日常の様々な問題をグラフ化し、その手法を応用して解いていく。
巡回セールスマン問題はグラフ理論の問題の一つである。グラフの辺にはそれぞれ重み(コスト)が存在している。そのグラフの全ての頂点を1回ずつ通る経路のうち、その経路に含まれる辺の重みが最小となるものを求めるのが巡回セールスマン問題である。
私はこの問題を解く手法を用いて、ポケモンスタンプラリーの最適なルートを求めたいと思っている。
アルゴリズムイントロダクション 第3版 第1巻、第2巻
(T.コルメン、R.リベスト、C.シュタイン、C.ライザーソン共著)
組合せ最適化
(B.コルテ、J.フィーゲン共著)
アート・オブ・Rプログラミング
(Norman Matloff著)
・春学期の卒業研究では、組合せ最適化の本を用いて最短パスについて学習しました。ゼミBではなかった個人ゼミもこのタイミングで始まりましたが、初めのうちは定理や命題の証明を十分理解していない状態で臨んでしまい、細かい箇所の説明を求められた時に何も話せないことが多くありました。しかし、この個人ゼミを通して証明の手法や、問題を解くこと(問題を解く意味、問題を解くための手法)について学ぶことができたと感じています。また、春学期の最後には研究室の生徒同士で自分が何を学んできたのかの発表会がありました。まだ発表には慣れておらず、上手く話すことはできませんでしたが、他の人はこれまで何をやってきたのかという話を聞くことができ、良い刺激になりました。
・秋学期の卒業研究では、まずは本格的に卒業研究を進めるためにテーマを決めるところから始まりました。私は、なんとなく興味があった巡回セールスマン問題を選択し、それから巡回セールスマン問題を解く手法を用いる問題としてポケモンスタンプラリーの最適ルートを解くというテーマにたどり着きました。限られた時間でこの問題を解くために、私は現在P・NP、巡回セールスマン問題(近似アルゴリズム)、Rのプログラミング(iGraph)を学んでいます。最終的には問題で求めたい最適ルートを実際に近似アルゴリズムを用いて出力したいと思っています。