数学特別演習（第16回）

今日は水曜日ですが、11日の金曜日が建国記念の日で休みになるため、金曜日の振替授業となりました。

今日は、長さ最短の巡回路に近い巡回路を計算するヒューリスティックの一つ「クリストファイズのアルゴリズム」を扱いました。このアルゴリズムで計算する巡回路の長さは、最短の巡回路に比べて、たかだか1.5倍に抑えられることが理論的にわかっています。

今日の授業では、最初の発表者に、クリストファイズのアルゴリズムの概要を説明してもらい、次の発表者に、クリストファイズのアルゴリズムで計算される巡回路の長さが、最短の巡回路に比べて1.5倍に近づくという、理論上最悪の例題の1つを説明してもらいました。

このうち、後半の、理論上最悪の例題では、ある規則的な形で、ノード数がどんどん増えていくグラフを扱いました。このノード数が大きくなると、クリストファイズのアルゴリズムで計算される巡回路の長さの、最短の巡回路の長さに対する比が1.5に収束するというものです。テキストでは、クリストファイズのアルゴリズムで計算される巡回の長さを「だいたい」の長さで計算しており、発表者の人も、それに従って発表していました。

しかし、数学を専門に学ぶ学生としては、「だいたい」の部分を「はっきり」させて確認する必要があると考え、その場で、巡回路の長さの見積りを厳密に計算してもらいました。そして、厳密に計算した長さの比も、3/2に近づくことを確かめてもらいました。

今回の授業を通して、本で読んだり人から聞いたりしたようなことでも、自分で確かめることが大切なこと、自分で確かめる作業は、数学では頭を使えばできる作業もあること、こういう作業によって、物事の道理を確かめることの大切さを学ぶことも、数学を学ぶ意義の一つであること、を知る機会になったと思います。

発表者の人は大変だったと思いますが、引き続き、完全グラフの巡回路を、樹形図で表す部分について説明してもらいました。よく頑張ったと思います。

次回はいよいよ最終回です。巡回路を探索する際の「分枝限定法」などを扱います。どこまで進めるかわかりませんが、なるべくゴールを目指して進みたいと思います。