Self-avoiding walk とは

数学では、自己回避歩行(self-avoiding walk:SAW)は、同じ点を2回以上訪問しない格子(格子経路)上の一連の移動である。これは、パスのグラフ理論的概念の特殊なケースです。自己回避ポリゴン(self-avoiding polygon:SAP)は、格子上に閉じた自己回避歩行です。 SAWは、物理的体積が同じ空間的点の複数の占有を禁止する溶媒やポリマーなどの鎖状物質の実際の挙動をモデル化するために化学者Paul Floryによって最初に導入されました。物理学者は、数値シミュレーションによって真実であり、強力に支持されている数々の推測を提供したが、数学的観点からは自己回避歩行について厳密にはほとんど知られていない。
計算物理学では、自己回避歩行は、一定数のノード、典型的には固定されたステップ長を有するR2またはR3における鎖状経路であり、それ自体または他の歩行を交差させないという不可欠の特性を有する。自己回避歩行のシステムは、いわゆる排除容積状態を満たす。より高い次元では、自己回避歩行は、通常のランダム歩行のように振る舞うと考えられている。 SAWおよびSAPは、タンパク質などの糸状およびループ状の分子の位相および結節理論的挙動のモデル化において中心的な役割を果たす。 SAWはフラクタルです。例えば、d = 2ではフラクタル次元は4/3であり、d = 3の場合は5/3に近く、d≧4の場合はフラクタル次元が2である。この次元は上方の限界寸法と呼ばれ、除外された体積は無視できる。除外された体積条件を満たさないSAWは、最近、SAWの拡張に起因する明示的な表面形状をモデル化するために研究された。
SAWの特性は解析的に計算することができないため、数値シミュレーションを使用します。ピボットアルゴリズムは、nステップの自己回避歩行の一様な測定のためのマルコフ連鎖モンテカルロシミュレーションの一般的な方法です。ピボットアルゴリズムは自己回避歩行を行い、この歩行のポイントをランダムに選択し、n歩後の歩行に対称操作(回転と反射)を適用して新しい歩行を作成します。与えられた格子内の自己回避歩行の数を計算することは、一般的な計算上の問題である。現在、自己回避歩行の数を決定するための公式は知られていませんが、それらを近似する厳密な方法があります。そのような経路の数を見つけることは、NP困難な問題であると考えられる。対角線の一方の端から他方の端への自己回避歩行の場合、正の方向への移動だけで、正確に
( m + n m , n ) {\displaystyle {m+n \choose m,n}}
m×nの長方形格子のための経路。