Metoda de mers rapid - Fast marching method

Metoda marsaluind rapidă este o metodă numerică creată de James Sethian pentru rezolvarea problemelor de valoare limită ale ecuației Eikonal :

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

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

De obicei, o astfel de problemă descrie evoluția unei suprafețe închise în funcție de timp cu viteza în direcția normală într-un punct de pe suprafața de propagare. Funcția de viteză este specificată, iar timpul la care conturul traversează un punct este obținut prin rezolvarea ecuației. Alternativ, poate fi considerat ca timpul minim necesar pentru a ajunge, începând de la punctul respectiv . Metoda de marșare rapidă profită de această interpretare optimă de control a problemei pentru a construi o soluție spre exterior pornind de la „informațiile cunoscute”, adică valorile la graniță. ${\ displaystyle u}$ ${\ displaystyle f}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle u (x)}$ ${\ displaystyle \ partial \ Omega}$ ${\ displaystyle x}$

Algoritmul este similar algoritmului lui Dijkstra și folosește faptul că informațiile curg doar în afară din zona de însămânțare. Această problemă este un caz special al metodelor de nivelare . Există algoritmi mai generali, dar în mod normal sunt mai încet.

Extensii la rezolvarea domeniilor non-plate (triunghiulate)

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

pentru suprafață și , au fost introduse de Ron Kimmel și James Sethian . ${\ displaystyle S}$ ${\ displaystyle x \ în S}$

Labirint ca funcție de viteză cea mai scurtă cale
Harta de distanță multi-șabloane cu puncte sursă aleatorii

Algoritm

În primul rând, presupuneți că domeniul a fost discretizat într-o rețea. Ne vom referi la punctele de rețea ca noduri. Fiecare nod are o valoare corespunzătoare . ${\ displaystyle x_ {i}}$ ${\ displaystyle U_ {i} = U (x_ {i}) \ approx u (x_ {i})}$

Algoritmul funcționează la fel ca algoritmul lui Dijkstra, dar diferă în modul în care sunt calculate valorile nodurilor. În algoritmul lui Dijkstra, valoarea unui nod este calculată folosind unul dintre nodurile vecine. Cu toate acestea, în rezolvarea PDE în , între și dintre nodurile vecine sunt utilizate . ${\ displaystyle \ mathbb {R} ^ {n}}$ ${\ displaystyle 1}$ ${\ displaystyle n}$

Nodurile sunt etichetate până acum (nu au fost încă vizitate), sunt considerate (vizitate și valoare atribuită provizoriu) și acceptate (vizitate și valoare atribuită permanent).

Alocați fiecărui nod valoarea și etichetați-le până acum ; pentru toate nodurile setate și etichetate ca acceptate . ${\ displaystyle x_ {i}}$ ${\ displaystyle U_ {i} = + \ infty}$ ${\ displaystyle x_ {i} \ in \ partial \ Omega}$ ${\ displaystyle U_ {i} = 0}$ ${\ displaystyle x_ {i}}$
Pentru fiecare nod îndepărtat , utilizați formula de actualizare Eikonal pentru a calcula o nouă valoare pentru . Dacă apoi setați și etichetați în considerare . ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ tilde {U}}}$ ${\ displaystyle {\ tilde {U}} <U_ {i}}$ ${\ displaystyle U_ {i} = {\ tilde {U}}}$ ${\ displaystyle x_ {i}}$
Fie nodul considerat cu cea mai mică valoare . Eticheta este acceptată . ${\ displaystyle {\ tilde {x}}}$ ${\ displaystyle U}$ ${\ displaystyle {\ tilde {x}}}$
Pentru fiecare vecin de care nu este acceptat, se calculează o valoare tentativă . ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ tilde {x}}}$ ${\ displaystyle {\ tilde {U}}}$
Dacă apoi setați . Dacă a fost etichetat până acum , actualizați eticheta la considerat . ${\ displaystyle {\ tilde {U}} <U_ {i}}$ ${\ displaystyle U_ {i} = {\ tilde {U}}}$ ${\ displaystyle x_ {i}}$
Dacă există un nod considerat , reveniți la pasul 3. În caz contrar, terminați.