Snabb marschmetod

Den snabba marschmetoden är en numerisk metod skapad av James Sethian för att lösa problem med gränsvärde i Eikonal-ekvationen :

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

$u(x)=0{\text{ för }}x\in \partial \Omega$

Vanligtvis beskriver ett sådant problem utvecklingen av en stängd yta som en funktion av tiden $u$ med hastigheten $f$ i normal riktning vid en punkt $x$ på fortplantningsytan. Hastighetsfunktionen specificeras, och tiden då konturen korsar en punkt $x$ erhålls genom att lösa ekvationen. Alternativt $u(x)$ ses som den minsta tid det skulle ta att nå $\partial \Omega$ med början från punkten $x$ . Den snabba marschmetoden utnyttjar denna optimala kontrolltolkning av problemet för att bygga en lösning utåt utifrån den "kända informationen", dvs gränsvärdena.

Algoritmen liknar Dijkstras algoritm och använder det faktum att information endast strömmar utåt från såningsområdet. Det här problemet är ett specialfall av nivåbestämda metoder . Mer generella algoritmer finns men är normalt långsammare.

Utvidgningar till icke-platta (triangulerade) domänlösningar

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

för ytan $S$ och ${\displaystyle x\in S} ,$ introducerades av Ron Kimmel och James Sethian .

• 

  Labyrint som hastighetsfunktion kortaste vägen

• 

  Avståndskarta multi-stenciler med slumpmässiga källpunkter

Algoritm

Antag först att domänen har diskretiserats till ett nät. Vi kommer att referera till meshpoints som noder. Varje nod $x_{i}$ har ett motsvarande värde $U_{i}=U(x_{i})\approx u(x_ {i})$ .

Algoritmen fungerar precis som Dijkstras algoritm men skiljer sig i hur nodernas värden beräknas. I Dijkstras algoritm beräknas en nods värde med en enda av de närliggande noderna. Men för att lösa PDE i $\mathbb {R} ^{n}$ används mellan $1$ och $n$ av de närliggande noderna .

Noder är märkta som långt (ännu ej besökta), övervägda (besökta och värde preliminärt tilldelat) och accepterade (besökt och värde permanent tilldelat).

1. Tilldela varje nod $x_{i}$ värdet på $U_{i}=+\infty$ och märk dem så långt ; för alla noder $x_{i}\in \partial \Omega$ sätt $U_{i}=0$ och etikett $x_{i}$ som accepterat .
2. För varje bortre nod $x_{i}$ , använd Eikonals uppdateringsformel för att beräkna ett nytt värde för ${\tilde {U}}$ . Om ${\tilde {U}}<U_{i}$ ställ in $U_{i}={\tilde {U}}$ och etikett ${ \displaystyle x_{i}}$ som ansett .
3. Låt ${\tilde {x}}$ vara den betraktade noden med det minsta värdet $U$ . Märk ${\tilde {x}}$ som accepterat .
4. För varje granne $x_{i}$ av ${\tilde {x}}$ som inte accepteras, beräkna ett preliminärt värde ${\tilde {U}}$ .
5. Om ${\tilde {U}}<U_{i}$ så ställ in $U_{i}={\tilde {U}}$ . Om $x_{i}$ var märkt så långt , uppdatera etiketten till beaktad .
6. Om det finns en övervägd nod, gå tillbaka till steg 3. Avsluta annars.

Se även

• Nivåsättningsmetod
• Snabb sopningsmetod
• Bellman–Ford algoritm

externa länkar

• Dijkstra-liknande metoder för Eikonal-ekvationen JN Tsitsiklis, 1995
• The Fast Marching Method and its Applications av James A. Sethian
• Multi-Stencils Snabba marschmetoder
• Multi-Stencils Fast Marching Matlab-implementering
• Implementeringsdetaljer för snabbmarschmetoderna
• Generalized Fast Marching-metod av Forcadel et al. [2008] för applikationer inom bildsegmentering.
• Python-implementering av Fast Marching-metoden
• Se kapitel 8 i Design och optimering av nano-optiska element genom att koppla tillverkning till optiskt beteende Arkiverad 2013-08-20 på Wayback Machine