研究のお話

[ English / Japanese ]

 堀山研究室では、情報処理技術の基礎としての 「アルゴリズム」の研究、 もう少し踏み込んで言うと「組合せ最適化」のための アルゴリズムの研究を行っています。 計算の本質的な複雑さとは何かを考え、 アルゴリズムの設計と解析に関して理論的なアプローチをしようと取り組んでいます。

 研究テーマとその簡単な説明は、 「堀山研究室の紹介」をご覧ください。 以下では、研究成果の一部をお見せします。 また、研究に関連して、一般の方向けにやさしく講演する機会がありましたので、 講演タイトルを挙げておきます。

研究テーマ

列挙アルゴリズム

タイリングの列挙

 基本図形に並進 (平行移動) や回転などの操作を繰り返し適用することで 平面を埋めつくすことを、タイリングといいます。 操作には、並進、鏡映、すべり鏡映、回転があり、 これらの組み合わせにより 17種類の埋めつくし方があることが知られています。 (より詳しくは、 wallpaper group についての解説 を参照してください。)

 こうした平面の埋めつくしは、 さまざまなデザインに活かされています。 たとえば、エッシャー は、 アルハンブラ宮殿 (スペイン) の壁面装飾に感銘を受け、 正則分割と呼ばれる技法による多様な絵画を残しています。 (エッシャーの公式ウェブサイトpicture gallery が あり、 symmetry の項目に正則分割による絵画が集められています。 また、それ以外の項目にも、これを発展させたエッシャー独自の絵画が見られます。 たとえば、 "Day and Night" (「昼と夜」) が有名です。) また、正倉院に伝わる正倉院裂 (きれ) のデザインにも見ることができます。 工業製品でも、 衣類 ( 千鳥格子 などが有名です) や カーテン、壁紙のデザインなど、身近に利用されています。

 さて、p4 タイリングは、 上記の 17種類の平面の埋めつくし方の一つです。 「p4 タイリングの パラパラ アニメ」 (PDFファイル) を 見ていただくと分かりますが、p4 タイリングでは、 2つの回転中心 (図の ● と ○) のまわりで 90°回転を繰り返すことで 平面を埋めつくすことができます。

 p4 タイリングができる基本図形は無限に多く考えられるのですが、 ここでは、正方形をつなぎ合わせた図形に限定して考えます。 (Polyomino と呼ばれています。) 回転中心の座標を指定すると、何個の正方形をつなぎ合わせれば良いかを 求めることができます。 ただし、たとえば5個の正方形をつなぎ合わせれば良いと分かっても、 5個を適当につなぎ合わせただけで、 いつでも p4 タイリングができる訳ではありません。 回転による埋めつくしで、重なりや隙間ができないようにする必要があります。 こうした条件を満たす、p4 タイリング可能な polyomino を コンピュータに生成させてみました。 「タイリングを生成してみる」では、 こうして生成された基本図形をもとに、 90°回転を繰り返すことで平面を埋めつくした絵を表示しています。

講演タイトル一覧

展開図の列挙

 展開図というと、 小学校の算数の時間に、立方体や直方体の箱を チョキチョキと楽しく切り開いたのを思い出される方が多いと思います。 私たちの身の周りでは、様々な場面で展開図のお世話になっています。 ケーキやお菓子の箱などは、その一例です。 また、携帯電話は箱に付属品と一緒に詰めてありますが、 その間仕切りをバラしてみると、ボール紙を器用に折り畳んであることが分かります。 板金加工で機械部品を作るのも、展開図から立体を作る作業といえます。 楽しいところでは、1枚の紙から複雑な立体を作る折り紙や、 紙の部品を組み合わせて作るペーパークラフトもあります。

 展開図についての最大の未解決問題は、 「任意の凸多面体は、必ず1つは 重なりの無い展開図を持つのだろうか?」 という問いです。 たとえば、サッカーボールは、五角形と六角形の面でできていますが、 下の図 (左側) の太線に沿って切り開くと、 図 (右側) のように展開図に重なりができてしまいます。 (太線の向こう側にも面はあるのですが、その部分をどのように切り開いても、 図 (右側) に面が追加されるだけで、重なりは解消されません。) 展開図を1枚の紙からチョキチョキと切り出して、 それを折り曲げて多面体を組み立てる工程を考えると、 展開図に重なりがあるのは問題です。 どんな凸多面体にも、重なりの無い展開図がちゃんとあるのかな? というシンプルな問いが未解決なのです。 ちなみに、サッカーボールには、先程のとは別に、うまい切り開き方があって、 重なりのない展開図がちゃんとありますので、ご安心を。

    

 さて、この未解決問題は、yes だと信じられていますが、 まだよく分かっていません。 そこで、重なる/重ならないについて詳しく知るために、 形の整った立体から検討してみることにしました。

 形が最も整った立体は、正多面体です。 1種類の面からなる凸多面体で、どの頂点の周りにも同じ形で面が配置されています。 正多面体は、正四面体、立方体、正八面体、正十二面体、正二十面体の 5種類あります。 正四面体の展開図は 2種類、立方体と正八面体の展開図は 11種類ですので、 全部を描いてみて、重なりがあるかどうか調べるのは簡単です。

 正十二面体、正二十面体の展開図は、43,380種類です。 これをすべて求めて、重なりがないか確認してみましょう。 まず、どの辺をどのように切れば展開図になるでしょうか? 実は、展開図になる切り開き方は、5,184,000通りあります。 次に、別の辺を切り開いていたのに、展開図が同じになる場合もあります。 同型性判定をしながら、本質的に異なる展開図 43,380種類を取り出す必要があります。 こうしてできた展開図カタログをもとに、 「正多面体のどの展開図にも重なりがない」ことが分かりました。

講演タイトル一覧

その他

オンライン問題

講演タイトル一覧

メカニズム デザイン

講演タイトル一覧

離散最適化

講演タイトル一覧


[ 戻る ]
horiyama [ @ ] al.ics.saitama-u.ac.jp