Innovative Tech

あなたは解けるか？　“ものすごく難しい迷路”　物理学者が作成　準結晶構造や数学的手法を活用（1/2 ページ）

　英カーディフ大学、スイスのジュネーヴ大学、英ブリストル大学に所属する研究者らが発表した論文「Hamiltonian Cycles on Ammann-Beenker Tilings」は、複雑な迷路を作成できるアルゴリズムを提案した研究報告である。

　研究で使用したのは「Ammann-Beenker（AB）タイリング」と呼ばれる準結晶の一種である。準結晶とは、原子が規則的な構造を持ちながらも、周期的な繰り返しパターンを持たない固体を指す。ABタイリングは、正方形と菱形の2種類のタイルから構成され、これを用いることで非周期的な2次元構造を作り出せる。この特性を利用し、研究者らは非常に複雑で解決が難しい迷路を作り上げた。

　この迷路の作成には「ハミルトン閉路」と呼ばれる数学的手法が用いられた。ハミルトン閉路とは、グラフ上の全ての頂点を一度だけ通り、出発点に戻ってくる経路のことであり、これを見つける問題はNP完全問題の一つとして知られている。

　研究者らは、ABタイリングの特性を利用し、このハミルトン閉路を構築するアルゴリズムを開発。ABタイリングの構造を利用してグラフを生成し、このアルゴリズムを用いてハミルトン閉路を見つけ出すことで、これらの経路が迷路のような複雑な構造を形成する。

　この迷路の難しさは、その非周期的な構造に起因する。通常の周期的な迷路では、一定のパターンが繰り返されるため、解決の手掛かりとなるが、ABタイルを用いた迷路ではそのようなパターンが存在せず、極めて難解である。

　開発したアルゴリズムの効率性と準結晶の特殊な構造を生かした応用として、次の3つが挙げられている。

1. 走査型トンネル顕微鏡の性能向上：準結晶という特殊な物質の表面を観察する際、顕微鏡の針先が動く最適な経路を見つけられる。これにより、より速く正確に物質の表面を調べることができるようになる。
2. 物質表面への分子の吸着の研究：ABタイリングを持つ準結晶の表面に、長い分子や柔軟な分子がどのように吸着するかを予測する。この予測は、新しい触媒や材料の開発に役立つ。
3. タンパク質の形作りの理解：タンパク質が折りたたまれて特定の形になる過程を、より正確にモデル化可能。

Innovative Tech

2019年にスタートした本連載「Innovative Tech」は、世界中の幅広い分野から最先端の研究論文を独自視点で厳選、解説している。執筆は研究論文メディア「Seamless」（シームレス）を主宰し、日課として数多くの論文に目を通す山下氏が担当。イラストや漫画は、同メディア所属のアーティスト・おね氏が手掛けている。

この連載の記事をもっと見る

この記事の著者

関連記事

• 

  “どの次元”でも車輪のように転がる“球以外の図形”　カナダの数学者らが発見　体積は常に球より小さい形状

• 

  周期性のない図形「ペンローズ・タイル」が量子コンピュータのエラーを訂正？　カナダの研究者らが発表

• 

  数学の未解決問題「アインシュタイン問題」を“完全解決”する新図形発見　「The hat」を改良

• 

  寝不足で失われた「記憶」、後で十分寝ても手遅れ？　繰り返し高速再生する機能は戻らず　米研究者らが検証

• 

  「素数」はランダムではない　出現周期に現れる“偏り”とは？　2016年発表の論文を紹介