数学特別演習（第9回）

今日からこの授業も3学期です。今日は、まず、前回の「オイラーの定理」を受けて、オイラーの業績の紹介がありました。複素関数論で現われる公式「e^{i π}+1=0」は、オイラーが発見した公式ですが、これは小説「博士の愛した数式」でもモチーフになっていました。それから、ドイツに伝わる一筆書き遊び「サンタクロースの家」というのも紹介されていました。期せずしてちょうどよいタイミングの話題になったと思います。

その次に、ごみ収集車が街中のごみを収集して回る最短経路の問題を考えることになりました。収集車のランニングコストを抑えるためには、収集車の総走行距離をなるべく抑える必要があります。そのためには、なるべく一筆書きに近い形で街中を通り抜けたいわけですが、街路には行き止まりなどもあり、なかなかそううまくはいきません。そこで、この問題をなるべくよい形で解くために「操業橋渡し運行」というのを導入し、操業橋渡し運行が最短になる組み合わせを求める問題として「ペアリング問題」を解くという話になりました。

「ペアリング問題」は、組み合わせの問題の一種なので、これを素朴に解こうとすると、時間計算量が O(n!) になり、組み合わせの爆発が起きるわけですが、これを O(n³) の計算時間で解くアルゴリズムがあるという事実が紹介されました。

次回は、これらを組み合わせて、ごみ収集車の問題を解くということで、ダイクストラのアルゴリズム、プリムのアルゴリズムに続いて、久々に具体的な形のアルゴリズムが授業に登場する予定です。私も予習をしつつ、学生さんの発表を見守りたいと思います。