数学特別演習（第14回）

今日は「巡回セールスマン問題」(Traveling Salesman Problem, TSP) が取り上げられました。TSP は、これまでの授業で扱った「ハミルトン閉路」と関連して、グラフで最短のハミルトン閉路を求める問題で、グラフ理論の中でも最も有名な問題の一つとして知られています。

私は、これまで、TSP を輸送計画問題としてしか知りませんでしたが、テキストに載っていた TSP の応用例として、電子機器の基板にロボットがドリルがついた腕を移動させながら穴を開ける際、ドリルの移動距離が最短になるような穴を開けるための順番を TSP として解くという問題が紹介されており、予想していなかった応用例があることに驚きました。それから、以前の授業で「プロッタがペンで図形を描く際のペンの最短経路を求める問題」が、中国の郵便配達員問題に帰着されることをやりましたが、図形が連結していないと、こちらも TSP となり、NP 困難な問題になるという事実も紹介され、与えられた問題がちょっと変わるだけで、計算の難しさが大きく変わることにも驚きました。

授業の後半では、TSP のなるべくよい解を求めるための「ヒューリスティック」の紹介がありました。次回は、これらのヒューリスティックが、どれだけよい解を与えているかの目安を知ることを一つの目的として「緩和法」について議論する予定です。

テキストも終盤に入ったところで、なかなか骨のある話題が続きますが、次の担当者の人達にも頑張って予習してもらいたいと思います。