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

[山下裕毅，ITmedia]

Innovative Tech：

このコーナーでは、2014年から先端テクノロジーの研究を論文単位で記事にしているWebメディア「Seamless」（シームレス）を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。

X： ＠shiropen2

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

構築した迷路　中央の赤いところから、経路をたどって迷路の外側に脱出する　答えは次ページ

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

ABタイリングのパターンの一部

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

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

形成した迷路

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

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

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