método de marcha rápida

El método de marcha rápida ^{[ 1 ]} es un método numérico creado por James Sethian para resolver problemas de valores en la frontera de la ecuación de Eikonal :

${\displaystyle |\nabla u(x)|=1/f(x){\text{ para }}x\in \Omega }$

${\displaystyle u(x)=0{\text{ para }}x\in \partial \Omega }$

Normalmente, este tipo de problema describe la evolución de una superficie cerrada en función del tiempo.${\displaystyle u}$con velocidad${\displaystyle f}$en la dirección normal en un punto${\displaystyle x}$en la superficie de propagación. Se especifica la función de velocidad y el tiempo en el que el contorno cruza un punto.${\displaystyle x}$se obtiene resolviendo la ecuación. Alternativamente,${\displaystyle u(x)}$puede considerarse como la cantidad mínima de tiempo que se necesitaría para alcanzar${\displaystyle \partial \Omega }$comenzando desde el punto${\displaystyle x}$El método de marcha rápida aprovecha esta interpretación de control óptimo del problema para construir una solución desde el exterior, partiendo de la "información conocida", es decir, los valores límite.

El algoritmo es similar al de Dijkstra y se basa en el hecho de que la información solo fluye hacia afuera desde el área de siembra. Este problema es un caso especial de los métodos de conjuntos de nivel . Existen algoritmos más generales , pero suelen ser más lentos.

Extensiones a dominios no planos (triangulados) que resuelven

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

para la superficie${\displaystyle S}$y${\displaystyle x\in S}$, fueron presentados por Ron Kimmel y James Sethian .

• 
  Laberinto como función de velocidad de camino más corto
• 
  Mapa de distancias con múltiples plantillas y puntos de origen aleatorios

Primero, supongamos que el dominio se ha discretizado en una malla. Nos referiremos a los puntos de la malla como nodos. Cada nodo${\displaystyle x_{i}}$tiene un valor correspondiente${\displaystyle U_{i}=U(x_{i})\approx u(x_{i})}$.

El algoritmo funciona igual que el algoritmo de Dijkstra, pero difiere en cómo se calculan los valores de los nodos. En el algoritmo de Dijkstra, el valor de un nodo se calcula utilizando uno solo de los nodos vecinos. Sin embargo, al resolver la EDP en${\displaystyle \mathbb {R} ^{n}}$, entre${\displaystyle 1}$y${\displaystyle n}$de los nodos vecinos se utilizan .

Los nodos se clasifican como lejanos (aún no visitados), considerados (visitados y con un valor asignado provisionalmente) y aceptados (visitados y con un valor asignado permanentemente).

1. Asignar cada nodo${\displaystyle x_{i}}$el valor de${\displaystyle U_{i}=+\infty }$y etiquetarlos como lejos ; para todos los nodos${\displaystyle x_{i}\in \partial \Omega }$colocar${\displaystyle U_{i}=0}$y etiqueta${\displaystyle x_{i}}$como se aceptó .
2. Para cada nodo lejano${\displaystyle x_{i}}$, utilice la fórmula de actualización de Eikonal para calcular un nuevo valor para${\displaystyle {\tilde {U}}}$. Si${\displaystyle {\tilde {U}}<U_{i}}$luego establecer${\displaystyle U_{i}={\tilde {U}}}$y etiqueta${\displaystyle x_{i}}$como se considera .
3. Dejar${\displaystyle {\tilde {x}}}$sea ​​el nodo considerado con el valor más pequeño${\displaystyle U}$. Etiqueta${\displaystyle {\tilde {x}}}$como se aceptó .
4. Por cada vecino${\displaystyle x_{i}}$de${\displaystyle {\tilde {x}}}$Eso no se acepta, calcule un valor tentativo.${\displaystyle {\tilde {U}}}$.
5. Si${\displaystyle {\tilde {U}}<U_{i}}$luego establecer${\displaystyle U_{i}={\tilde {U}}}$. Si${\displaystyle x_{i}}$fue etiquetado como hasta ahora , actualice la etiqueta a considerado .
6. Si existe un nodo considerado , vuelva al paso 3. De lo contrario, finalice.

• Método de conjunto de niveles
• Método de barrido rápido
• Algoritmo de Bellman-Ford

• Métodos tipo Dijkstra para la ecuación de Eikonal, JN Tsitsiklis, 1995
• El método de marcha rápida y sus aplicaciones por James A. Sethian
• Métodos de marcha rápida con múltiples plantillas
• Implementación en Matlab de marcha rápida con múltiples plantillas
• Detalles de implementación de los métodos de marcha rápida
• Método de Marcha Rápida Generalizada de Forcadel et al. [2008] para aplicaciones en segmentación de imágenes.
• Implementación en Python del método de marcha rápida
• Consulte el capítulo 8 de «Diseño y optimización de elementos nanoópticos mediante el acoplamiento de la fabricación al comportamiento óptico», archivado el 20 de agosto de 2013 en Wayback Machine.