快速行进算法

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

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

的一种数值方法.

通常, 此问题描述了闭曲线在法向速度 ${\displaystyle F(x)}$ 下的演化. 其中速度函数仅依赖于位置, 那么求解方程即可得到曲线到达某点${\displaystyle 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 （页面存档备份，存于互联网档案馆）