Innovative Tech

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

公開 2024年07月09日 08時01分

著者

山下裕毅

[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つが挙げられている。

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

次ページへ迷路の答えはこちら

印刷する

SpecialPR

Innovative Tech

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

連載新着通知を受け取る

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