数学特別演習（第17回）

今回が、この授業の最終回となりました。

今回は、まず、巡回路を探索する際に、効率よく選択対象を絞るための「分枝限定法」すなわち「枝刈り」を取り上げました。枝刈りは、基本的には、巡回路の開始ノードからあるノードまでの経路を固定した最小1-木を計算し、その長さを、経路を固定しない場合の最小1-木の長さと比較して、長さが等しいかより短い経路のみを選択肢として残していくやり方です。

本書では、枝刈りのための経路を固定する方法として、以下の2つを取り上げました。まず、開始ノードから次の経路を順番に選択した場合、そして、経路を固定しない場合の最小1-木に、次数が3以上のノードが現われた場合に、そのノードを中心に、次数が2を越えないような経路を選択した場合です。特に後者の方法については、私も予習していて理解に苦しんだ部分でしたが、発表者の人はよく予習していて、おかげで私もよく理解することができました。

次に、後半の、最後の発表では「多面体的組み合わせ論」を扱いました。これは、ノードの個数がn個のグラフについて、すべてのグラフを1つ1つ格子点に対応させて考えます。辺がある場合は、それぞれの座標を1、ない場合は0とします。すると、巡回路全体の集合は、格子点のなす空間内で、多面体を構成します。巡回路の探索にあたって、この多面体をなるべく精度よく近似することで、効率的な巡回路の探索につなげようというものです。

この話題の中では、多面体の頂点と辺の個数の関係を取り上げました。まず、多面体の頂点と辺の個数の関係は、多面体に依存していろいろ異なった状況が存在します。頂点の個数に比べて辺の個数がずっと多い多面体もあれば、逆の場合もあります。次に、仮に頂点の個数が多い多面体でも、辺の個数が比較的少ない場合は、もとの空間から多面体を「切り取る」回数を小さく抑えられる可能性が指摘されました。この話題は、チーズを例に取り上げ、醸造したもとの形のチーズから、立方体のチーズのかたまりを切り取るという例が紹介されました。

最後の話題は、巡回路に対応する頂点から構成される多面体の話になりました。巡回路に対応する頂点から構成される多面体は、頂点の個数に比べて面の個数が大幅に増加します。しかし、それらの面をすべて正確に近似する必要はなく、最適な頂点の近くで、多面体をそこそこ（うまく）近似し、かつ面の個数がなるべく少ない多面体で（お気楽に）近似できれば十分で、現在の研究の最先端は、そのような「うまい」多面体の近似をいかに効率的に見つけるかが焦点の一つであるという説明で終わりました。

これで、結局、テキストの最後の1章を残して授業が終わりました。最後の1章は、巡回セールスマン問題の研究の歴史が紹介されています。

以上がこの授業とテキストの内容ですが、まず、テキストについての感想を述べますと、非常におもしろい本だったと思います。テーマが実社会の問題と密接に関連しており、興味がわくこと、その問題を解くための理論は数学に基づいていること、かつ、「存在証明」などの定性的な要素と、アルゴリズムなど、構成的な要素の両輪を用いて問題にアタックすること、等、私自身も興味をもって読みましたし、学生さん達にとっても、数学に対する認識を新たにする内容だったようです。

翻訳も、読み物的な本を、数学的な正しさを損なわずにわかりやすく訳すのは苦労があったと思いますが、おおむね、よく訳されていて読みやすかったと思います。ただ、数か所、訳文の数学的意味が読み取りづらい部分や、術語の記述が不正確な部分が見受けられたので、さらなる翻訳の向上に期待します。

授業に関しては、学生さん達は、皆積極的によく頑張って予習、発表していたと思います。授業の最初の頃は、皆さん苦労しているようでしたが、回数を重ねるにつれて、発表や板書の質やわかりやすさが徐々に向上していることが見てとれました。学生さん同士でやると、このように刺激になってよいものですね。

先日開かれた学類のクラス連絡会で、授業評価アンケートの結果が報告された際、微積分や線形代数の予習時間の少なさが指摘されていました。大学の授業に対する認識の結果だと思いますが、私がこの授業で学生さん達を見てきた限り、その気になれば予習に取り組む能力は十分に備わっていると確信したので、こうした力を他の授業でも発揮されることを望みます。

長いようで短い半年間でしたが、一緒に授業をつくってきた学生さん達に感謝します。この本は、これから本格的に数学を勉強しようとする学生さん方、数学を教える先生方、そして数学に興味を持つ多くの方々に、おすすめ度は「星3つです！」です。数学的な内容は割とちゃんと書いており、さらっとした会話の中にも重要事項が頻発ますので、1文1文を納得するまでじっくり読まれることをおすすめします。

さあ、学生さん達の最後の感想文に目を通すことにしましょう。ついでに、来年度もこの授業を受け持つ予定です。次はどんな本を読もうかしら・・・