文字サイズ

    楽して計算するには 「効率的な方法探る視点を」 数理解析研究所 牧野和久准教授

     「楽をする」というと、怠ける、手を抜くといったマイナスの印象が強いが、無駄を省く、効率的といったプラス面もある。計算では特に後者の視点が重要だ。

    • 数理解析研究所 牧野和久准教授
      数理解析研究所 牧野和久准教授

     「ハミルトン閉路」という数学のテーマがある。これは、複数の頂点とそれらを結ぶ辺で構成される図形(グラフ)で、出発点からそれ以外の頂点を1回だけ通り、最後に出発点にもう一度戻ってくることのできるルートが一つでもあれば「閉路あり」、一つもなければ「閉路なし」と定義される。

     図1を見てほしい。例えば頂点Aを出発し、矢印のルートを進めば、各頂点を1回だけ通るので、図1は「閉路あり」となる。

     図2はどうか。図1に比べて「閉路あり」のルートを見つけるのは時間がかかる。

     そこで、今回のテーマに沿って「楽して」、閉路の有無を見つけたい。図2の一辺の両端の頂点が必ず別の色になるよう、白と赤の2色で色分けした図3を作ってみた。

     仮に「閉路あり」だとすると、必ず「白→赤→白→赤……」というように交互に頂点を通り、出発点に戻ってくることになる。そして、出発点に戻る一つ前の頂点の色は、出発点と別の色でなければならない。ということは、白と赤は同数になるはずだ。

     しかし、数えてみると白7、赤8だ。交互に進んでも、「赤→赤」と続く頂点が必ず出てきてしまうことになり、「閉路あり」の条件と矛盾する。つまり図2は「閉路なし」となる。複雑な計算をせず、「楽して」結論が出せる一例だ。

     社会の発展には、瞬時に膨大な計算ができるスーパーコンピューターなど、ハード面の整備が重要なのは確かだ。でも、効率的な計算法というソフト面の充実がより重要だと思う。

     □まきの・かずひさ□ 1997年、京都大工学研究科博士課程(数理工学専攻)修了。大阪大基礎工学研究科助教授、東京大情報理工学系研究科助教授などを経て、2013年から現職。専門は離散数学、最適化、アルゴリズム論。

    2015年11月30日 Copyright © The Yomiuri Shimbun
    大阪本社社会部から
    リンク