빠른 행진 방법 문서 원본 보기

{{위키데이터 속성 추적}}
'''빠른 행진 방법'''(빠른行进方法, {{llang|en|fast marching method}})<ref name="sethian_fmm">J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591--1595, 1996. [https://math.berkeley.edu/~sethian/2006/Papers/sethian.fastmarching.pdf]</ref>은 [[제임스 세티안]]이 만든 방법으로, 다음의 [[아이코날 방정식]]의 [[경계값 문제]]를 해결하는 수치적 방법이다:

: <math>|\nabla u(x)|=1/f(x) \text{ for } x \in \Omega</math>
: <math>u(x) = 0 \text{ for } x \in \partial\Omega</math>

특히, 이런 문제는 닫힌 표면의 진화를 점 <math>x</math>에서 전파 표면으로 가는 법 방향의 속도 <math>f</math>와 시간 <math>u</math>에 관한 함수로 설명한다. 속도 함수는 결정되어 있고, 파면이 점 <math>x</math>을 통과하는 시간은 방정식을 풀어서 얻을 수 있다. 대신에, <math>u(x)</math>는 점 <math>x</math>에서 시작해서 <math>\partial\Omega</math>에 도달하는 최소 시간으로 생각할 수 있다. 빠른 행진 방법은 "아는 정보"에서 시작해서 해법을 만들어 나가는 문제(즉, 경계값 문제)의 [[최적 제어]] 해석의 이점을 이용한다.

알고리즘은 [[데이크스트라 알고리즘]]과 유사하고 정보가 시작 영역에서 바깥으로 뻗어나간다는 점을 이용한다. 이 문제는 [[레벨 셋 방법]]의 특수한 경우이다. [[아이코날 방정식#계산 알고리즘|더 일반적인 알고리즘]]이 있지만 일반적으로 더 느리다.

평면이 아닌(삼각화된) 영역으로의 확장은 다음을 표면 <math>S</math>와 <math>x\in S</math>에 대해서 해결하는 것으로, [[론 킴멜]]과 [[제임스 세티안]]이 고안해냈다:

::<math>|\nabla_S u(x)|=1 / f(x),
</math>

<gallery>
파일:Fast_marching_maze.png|속도 함수로써의 미로와 최단 경로
파일:Fast_marching_multi_stencil_2nd_order.png|무작위 소스 점에서의 거리 맵의 멀티 스탠실
</gallery>

==알고리즘==

처음에는, 영역이 메쉬로 이산화되었다고 가정한다. 이 메쉬의 점을 꼭짓점으로 부를 것이다. 각각의 꼭짓점 <math>x_i</math>은 대응하는 값인 <math>U_i = U(x_i) \approx u(x_i)</math>을 가진다.

이 알고리즘은 [[데이크스트라 알고리즘]]과 거의 비슷하지만 꼭짓점의 값을 계산하는 방법은 다르다. 데이크스트라 알고리즘에서 꼭짓점의 값은 인접한 하나의 꼭짓점만 의존해서 계산하지만, <math>\mathbb{R}^n</math>에서 PDE를 풀 때는 <math>1</math>에서 <math>n</math>개의 인접한 꼭짓점을 [[아이코날 방정식#수치 근사|사용한다]].

꼭짓점은 각각 ''멂(far)'' (방문하지 않음), ''고려 중(considered)'' (방문했으며 시험적인 값을 부여함), 그리고 ''완료 됨(accepted)'' (방문했으며 영구적인 값을 부여함)의 라벨이 붙는다.

# 모든 꼭짓점 <math>x_i</math>에 <math>U_i=+\infty</math>의 값을 부여하고 ''멂'' 라벨을 붙이고, <math>x_i \in \partial\Omega</math>인 모든 꼭짓점에 대해서 <math>U_i = 0</math>로 설정하고 <math>x_i</math>의 라벨을 ''완료 됨''으로 설정한다.
# 모든 먼 꼭짓점 <math>x_i</math>에 대해서, <math>\tilde{U}</math>의 새 값을 계산하기 위해 [[아이코날 방정식#수치 근사|아이코날 업데이트 공식]]을 사용한다. <math>\tilde{U} < U_i</math>이면, <math>U_i = \tilde{U}</math>으로 <math>x_i</math>의 라벨을 ''고려 중''으로 설정한다.
# <math>\tilde{x}</math>가 고려 중인 꼭짓점 중 가장 작은 <math>U</math>의 값을 가지는 꼭짓점이라면 <math>\tilde{x}</math>에는 ''완료 됨''의 라벨을 붙인다.
# <math>\tilde{x}</math>의 모든 완료되지 않은 인접한 꼭짓점 <math>x_i</math>에 대해서, 시험적 값 <math>\tilde{U}</math>을 계산한다.
# <math>\tilde{U} < U_i </math>이라면 <math>U_i = \tilde{U}</math>로 설정한다. If <math>x_i</math>의 라벨이 ''멂''이였다면, 라벨을 ''고려 중''으로 갱신한다.
# 만약 ''고려 중''인 꼭짓점이 있다면, 3단계로 되돌아간다. 그렇지 않으면 종료한다.

== 같이 보기 ==
* [[레벨집합 방법]]
* [[빠른 스위핑 방법]]
* [[벨먼-포드 알고리즘]]

== 외부 링크 ==
* [http://www.mit.edu/~jnt/dijkstra.html Dijkstra-like Methods for the Eikonal Equation J.N. Tsitsiklis, 1995]
* [http://math.berkeley.edu/~sethian/ The Fast Marching Method and its Applications by James A. Sethian]
* [https://web.archive.org/web/20110719232108/http://mecca.louisville.edu/~msabry/projects/msfm.htm Multi-Stencils Fast Marching Methods]
* [http://www.mathworks.com/matlabcentral/fileexchange/24531 Multi-Stencils Fast Marching Matlab Implementation]
* [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/841/pdf/imm841.pdf Implementation Details of the Fast Marching Methods]
* [https://rd.springer.com/article/10.1007/s11075-008-9183-x Generalized Fast Marching method] by Forcadel et al. [2008] for applications in image segmentation.
* [https://github.com/scikit-fmm/scikit-fmm Python Implementation of the Fast Marching Method]
*See Chapter 8 in [http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf Design and Optimization of Nano-Optical Elements by Coupling Fabrication to Optical Behavior] {{웹아카이브|url=https://web.archive.org/web/20130820063106/http://etd.fcla.edu/CF/CFE0001159/Rumpf_Raymond_C_200608_PhD.pdf}}

== 각주 ==
{{각주}}

[[분류:수치미분방정식]]