자기 회피 보행

수학에서 SAW(self-avoiding walk)는 같은 점을 두 번 이상 방문하지 않는 격자(격자 경로) 상의 일련의 움직임입니다.이것은 경로의 그래프 이론 개념의 특별한 경우입니다.자기 회피 폴리곤(SAP)은 격자상의 닫힌 자기 회피 워크입니다.비록 물리학자들은 사실로 믿고 수치 시뮬레이션에 의해 강하게 뒷받침되는 수많은 추측을 제공했지만, 수학적인 관점에서 자기 회피 보행에 대해서는 엄격하게 알려진 것이 거의 없다.

계산물리학에서 자기회피보행은 일정한 수의 노드를 가진 R 또는³ R의 체인² 같은 경로로, 일반적으로 일정한 스텝 길이이며, 자기 자신이나 다른 워크와 교차하지 않는 특성이 있습니다.SAW 시스템은 이른바 제외 볼륨 조건을 충족합니다.고차원에서는 SAW가 일반적인 랜덤 워크와 매우 비슷하게 동작하는 것으로 생각됩니다.

SAW와 SAPs는 단백질과 같은 실과 루프 형태의 분자의 위상 및 매듭 이론 거동의 모델링에 중심적인 역할을 한다.실제로 SAW는 물리 부피가 동일한 공간 지점을 여러 개 점유할 수 없는 용제 및 폴리머와 같은 사슬과 유사한 실체의 실제 거동을 모델링하기 위해 화학자 Paul^{[1][dubious – discuss]} Flory에 의해 처음 도입되었을 수 있다.

SAW는 프랙탈이야예를 들어, d = 2에서 프랙탈 치수는 4/3이고, d = 3의 경우 5/3에 가까운 반면 d ≤ 4의 경우 프랙탈 치수는 2이다.이 치수는 제외된 볼륨이 무시할 수 있는 상위 임계 차원이라고 합니다.제외된 체적 조건을 충족하지 않는 SAW는 ^[2]최근 SAW의 확장에 따른 명시적 표면 형상을 모델링하기 위해 연구되었다.

SAW의 특성은 분석적으로 계산할 수 없으므로 수치 시뮬레이션을 사용합니다.피벗 알고리즘은 n단계 자가 회피 보행에 대한 균일한 측정을 위한 마르코프 연쇄 몬테 카를로 시뮬레이션의 일반적인 방법이다.피벗 알고리즘은 자기 회피 워크를 하고 이 워크의 포인트를 랜덤으로 선택한 다음 n번째 스텝 후에 워크에 대칭 변환(회전 및 반사)을 적용하여 새 워크를 만드는 방식으로 작동합니다.

주어진 격자에서 자기 회피 보행 수를 계산하는 것은 일반적인 계산 문제이다.엄밀한 ^[3][4]근사 방법이 있지만 현재 알려진 공식은 없다.

유니버설리티

일반적으로 자기 회피 보행과 통계 물리학 모델과 관련된 현상 중 하나는 보편성의 개념, 즉 격자 선택과 같은 미시적 세부 사항으로부터의 거시적 관찰 가능성의 독립성이다.보편 법칙에 대한 추측에서 나타나는 한 가지 중요한 양은 다음과 같이 정의된 연결 상수이다.c는_n n단계 자기 회피 보행 횟수를 나타냅니다.모든 (n + m) 스텝의 자기 회피 워크는 n 스텝의 자기 회피 워크와 m 스텝의 자기 회피 워크로 분해할 수 있으므로 c ≤ cc가_nm 된다_n+m.따라서 시퀀스 {log_n c}은(는) 부가적이며 Fekete의 보조항목을 적용하여 다음과 같은 제한이 있음을 나타낼 수 있습니다.

${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}.}$

c는 걷기 위해 선택된 특정 격자에 따라 달라지기 때문에_n μ는 연결 상수라고 불립니다.μ의 정확한 값은 육각형 격자에 대해서만 알려져 있으며, 여기서 ^[5]μ는 다음과 같습니다.

$(\displaystyle {2+{\displayrt {2}})}$

다른 격자의 경우, μ는 수치적으로만 근사되었으며 대수적 숫자도 아닌 것으로 여겨진다.라고 추측되고^[6] 있다

${\displaystyle c_{n}\about \mu^{n}n^{\frac {11}{32}}$

여기서 μ는 격자에 따라 달라지지만, 멱함수 ${\displaystyle {\frac{\mathrm{보정}}{}}^{}}$ n ${\displaystyle {\frac{11}{}}^{}}$ 32$({${11}{$32})$는 그렇지 않다. 즉, 이 법칙은 보편적이라고 여겨진다.

네트워크상

자기 회피 보행은 또한 ^[7]네트워크 이론의 맥락에서 연구되었다.이 문맥에서는 SAW를 동적 프로세스로 취급하는 것이 관례입니다.따라서 타임스텝마다 워커가 네트워크의 인접 노드 사이를 랜덤으로 홉합니다.워커가 막다른 골목 상태에 이르면 워크가 종료되므로 더 이상 새로 방문되지 않은 노드로 진행할 수 없습니다.최근 Erd's-Rényi 네트워크에서는 동적으로 성장한SAW의 패스 길이 분포를 해석적으로 계산할 수 있으며 Gompertz ^[8]분포를 따르는 것으로 나타났습니다.

한계

전체 평면에서 n단계 자가 회피 보행에 대한 균일한 측정을 고려한다.n → θ로 나타나는 균일한 측정의 한계가 무한 전체 평면 보행에 대한 측정을 유도하는지는 현재 알려져 있지 않다.그러나 해리 케스텐은 하프플레인에서 스스로 걷는 것을 피하기 위해 그러한 조치가 존재한다는 것을 보여주었다.자기 회피 보행과 관련된 한 가지 중요한 질문은 스케일링 한계의 존재와 등각적 불변성, 즉 보행의 길이가 무한대로 가고 격자의 메시가 0으로 가는 한계이다.그self-avoiding 걷다의 한계 Schramm–Loewner 진화에 의해 매개 변수 κ).mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output으로 설명되어 질 것으로 추측할 수 있다..sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}8/3.

「 」를 참조해 주세요.

• 임계 현상
• 해밀턴 경로
• 나이트 투어
• 랜덤 워크
• 스네이크 (비디오 게임 장르)
• 범용성(동적 시스템)

레퍼런스

추가 정보

외부 링크

• OEIS 시퀀스 A007764(n X n 그리드의 반대쪽 모서리에 결합하는 교차하지 않는(또는 자기 회피) 루크 경로의 수): N × N 그리드의 반대쪽 모서리에 결합하는 자기 회피 경로의 수(0 ~12).또한 최대 N = 21까지 확장 목록을 포함합니다.
• Weisstein, Eric W. "Self-Avoiding Walk". MathWorld.
• 2D 자동 회피 워크의 Java 애플릿
• SAW와 확장 FiberWalk를 n차원 정사각형 격자에서 시뮬레이션하는 일반적인 파이버 구현입니다.
• 다이아몬드 큐빅에서 SAW를 생성하는 Norris 소프트웨어.