고속행진법

고속행진법은^[1] 제임스 세션(James Sethian)이 에이콘 방정식의 경계값 문제를 해결하기 위해 만든 숫자법이다.

\nabla u(x) =1/f(x){\text{ for }x\in \Oomega

u(x)=0{\text{ for }x\in \partial \Oomega

일반적으로 이러한 문제는 폐쇄 표면의 진화를 속도 $f$ ${\displaystyle$ f $}$ 이(가) 정상 방향으로 전파 $u$ $f$ 표면의 $x$ 지점 $x$ $x$ 에서 시간 $u$ $u$ 의 함수로서 설명한다.속도 함수를 지정하고 등고선이 $점$ x $x$ 을 교차하는 시간을 방정식을 풀어서 구한다 $x$ .또는 $u(x)$ $u(x)$ ( $u(x)$ ) $u(x)$ 을(를) 지점 $x$ ${\displaystyle$ $\partial \Oomega}$ 에서 $\partial\Omega$ $\partial \Omega$ ${\displaystyle$ $x$ 에 도달하는 데 걸리는 최소 시간으로 생각할 수 있다.빠른 행군 방법은 "알려진 정보", 즉 경계 값에서 시작하는 솔루션을 외부에서 구축하기 위해 이 최적의 문제 제어 해석의 이점을 이용한다.

알고리즘은 다이크스트라의 알고리즘과 유사하며 정보가 시드 영역 바깥쪽으로만 흐른다는 사실을 사용한다.이 문제는 레벨셋 방식의 특수한 경우다.더 일반적인 알고리즘이 존재하지만 보통 더 느리다.

비플래트(삼각형) 도메인 해결로의 확장

\nabla _{S}u(x) =1/f(x),

표면 $S$ $S$ 및 $S$ $x\in S$ $x\in S$ S ${\displaystyle x\in S$ 에 대해서는 론 킴멜과 제임스 세션에 의해 소개되었다.

속도 기능으로 미로(Maze) 최단 경로
랜덤 소스 점이 있는 거리 맵 다중 스텐실

알고리즘.

첫째, 도메인이 그물망으로 분해되었다고 가정한다.메쉬포인트를 노드라고 부르겠다.각 노드 $x_{i}$ $U_{i}=U(x_{i})\approx u(x_{i})$ ${\$ 은 $x_{i}$ (는) $U_{i}=U(x_{i})\approx u(x_{i})$ i = $U_{i}=U(x_{i})\approx u(x_{i})$ ( $U_{i}=U(x_{i})\approx u(x_{i})$ ) $U_{i}=U(x_{i})\approx u(x_{i})$ $U_{i}=U(x_{i})\approx u(x_{i})$ ( $U_{i}=U(x_{i})\approx u(x_{i})$ $U_{i}=U(x_{i})\approx u(x_{i})$ ) ${\displaystyle U_{i}=U(x_{i}})\관련 u(x_{i$

알고리즘은 Dijkstra의 알고리즘처럼 작동하지만 노드의 값이 계산되는 방법은 다르다.Dijkstra 알고리즘에서 노드 값은 인접 노드 중 하나의 값을 사용하여 계산한다.단, R $\mathbb {R} ^{n}$ ${\$ ^{ $n$ 의 PDE를 풀 때 인접 노드의 $1$ $n$ $1$ 에서 $1$ $n$ $n$ 사이는 사용된다.

노드는 멀리(아직 방문하지 않음), 고려(방문 및 임시 할당된 값) 및 수락(방문 및 영구 할당된 값)으로 라벨이 지정된다.

Assign every node $x_{i}$ the value of $U_{i}=+\infty$ and label them as far; for all nodes $x_{i}\in \partial \Omega$ set $U_{i}=0$ and label $x_{i}$ as accepted.
만약 U일<>U나는{\displaystyle{\tilde{U}}<>마다 멀리 노드에게)나는},{\displaystyle x_{나는}은 Eikonal}U~{\displaystyle{\tilde{U}을 위한 새로운 가치를 계산하기 위해 공식 업데이트}.;를 사용한다.U_{나는}}i}}해당)나는}{\displaystyle x_{나는}U~{\displaystyle U_{나는}={\tilde{U}원 U을 세웠다. $x_{i}$ 고려에 의하면
${\tilde {x}}$ ~ ${\$ 을(를) $가장$ 작은값 U {\ $displaystyle U}$ 을(를) 가진 노드로 간주하고 ${\tilde {x}}$ $U$ x ${\tilde {x}}$ x ${\tilde {x}}$ ~ {\ $displaystyle {\tilde$ { $x}}$ 을(를) 수락한 것으로 ${\tilde {x}}$ 간주한다.
수락되지 ${\tilde {x}}$ x ~ ${\tilde {x}}$ {\ $displaystyle$ {\ $tilde {x}$ 의 $x_{i}$ 모든 인접 $x_{i}$ $x_{i}$ {\ $displaystyle x_{i}$ 에 대해 임시 ${\tilde {U}}$ U ${\tilde {U}}$ ~ ${\$ 을(를) 계산하십시오 ${\tilde {U}}$
${\tilde {U}}<U_{i}$ ~ ${\tilde {U}}<U_{i}$ < ${\tilde {U}}<U_{i}$ ${\tilde {U}}<U_{i}$ ${\$ ${$ $i}}}}}$ 을 $U_{i}={\tilde {U}}$ 를) 설정한 경우 ${\tilde {U}}<U_{i}$ U i = $x_{i}$ ~ {\ $displaystyle U_{i}={\tilde{U}}}}$ 을(를) 설정하고 $U_{i}={\tilde {U}}$ x $x_{i}$ ${\$ 레이블이 표시된 $x_{i}$ 경우 해당 레이블을 고려하도록 업데이트하십시오.
고려된 노드가 있는 경우 3단계로 돌아가십시오.그렇지 않으면 종료한다.