快速行進算法

賽斯詹姆斯引入的快速行進算法(fast marching method) 是求解程函方程:

$F(x)|\nabla T(x)|=1.$

的一種數值方法.

通常, 此問題描述了閉曲線在法向速度 $F(x)$ 下的演化. 其中速度函數僅依賴於位置, 那麼求解方程即可得到曲線到達某點$x$ 的時間.

該算法基於這樣的事實, 信息的從較小的時間T向外傳播. 該算法與圖搜索中的迪科斯徹算法(Dijkstra's algorithm)相似.

該問題是水平集方法的特殊情況. 對於該問題有更通用的算法, 但是通用算法通常會比快速行進算法慢.

• 
  Maze as speed function shortest path
• 
  Distance map multi-stencils with random source points

參閱

• 水平集方法
• 迪科斯徹算法

外部連結

• The Fast Marching Method and its Applications by James A. Sethian （頁面存檔備份，存於互聯網檔案館）
• Fast Marching on surfaces at Ron Kimmel's homepage （頁面存檔備份，存於互聯網檔案館）
• Multi-Stencils Fast Marching Methods
• Multi-Stencils Fast Marching Matlab Implementation （頁面存檔備份，存於互聯網檔案館）
• Tutorial on the Fast Marching Methods （頁面存檔備份，存於互聯網檔案館）
• Implementation Details of the Fast Marching Methods （頁面存檔備份，存於互聯網檔案館）