Metoda rychlého pochodu - Fast marching method

The metoda rychlého pochodu^[1] je numerická metoda vytvořená pomocí James Sethian k řešení problémy s hraniční hodnotou z Eikonální rovnice:

{ displaystyle | nabla u (x) | = 1 / f (x) { text {pro}} x v Omega}

{ displaystyle u (x) = 0 { text {pro}} x v částečné Omega}

Typicky takový problém popisuje vývoj uzavřeného povrchu jako funkci času ${ displaystyle u}$ s rychlostí ${ displaystyle f}$ v bodě v normálním směru ${ displaystyle x}$ na množícím se povrchu. Je určena funkce rychlosti a čas, kdy kontura protne bod ${ displaystyle x}$ se získá řešením rovnice. Alternativně, ${ displaystyle u (x)}$ lze považovat za minimální čas potřebný k dosažení ${ displaystyle částečné Omega}$ počínaje od bodu ${ displaystyle x}$ . Metoda rychlého pochodu to využívá optimální ovládání interpretace problému za účelem vytvoření řešení směrem ven počínaje „známou informací“, tj. hraničními hodnotami.

Algoritmus je podobný Dijkstrův algoritmus a využívá skutečnosti, že informace teče pouze ven z oblasti setí. Tento problém je zvláštním případem metody nastavení úrovní. Obecnější algoritmy existují ale obvykle jsou pomalejší.

Řešení rozšíření do plochých (trojúhelníkových) domén

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

pro povrch ${ displaystyle S}$ a ${ displaystyle x v S}$ , byly představeny Ron Kimmel a James Sethian.

Bludiště jako rychlostní funkce nejkratší cesta
Distanční mapa s více vzorci s náhodnými zdrojovými body

Algoritmus

Nejprve předpokládejme, že doména byla diskretizována do sítě. Mřížkové body budeme označovat jako uzly. Každý uzel ${ displaystyle x_ {i}}$ má odpovídající hodnotu ${ displaystyle U_ {i} = U (x_ {i}) přibližně u (x_ {i})}$ .

Algoritmus funguje stejně jako Dijkstrův algoritmus, ale liší se ve způsobu výpočtu hodnot uzlů. V Dijkstraově algoritmu se hodnota uzlu vypočítává pomocí jediného ze sousedních uzlů. Při řešení PDE v ${ displaystyle mathbb {R} ^ {n}}$ mezi ${ displaystyle 1}$ a ${ displaystyle n}$ sousedních uzlů Jsou používány.

Uzly jsou označeny jako daleko (dosud nenavštíveno), považováno (navštívená a předběžně přidělená hodnota) a přijato (navštíveno a hodnota trvale přiřazena).

Přiřaďte každý uzel ${ displaystyle x_ {i}}$ hodnota ${ displaystyle U_ {i} = + infty}$ a označit je jako daleko; pro všechny uzly ${ displaystyle x_ {i} v částečné Omega}$ soubor ${ displaystyle U_ {i} = 0}$ a označit ${ displaystyle x_ {i}}$ tak jako přijato.
Pro každý vzdálený uzel ${ displaystyle x_ {i}}$ , použijte Eikonal aktualizační vzorec pro výpočet nové hodnoty pro ${ displaystyle { tilde {U}}}$ . Li ${ displaystyle { tilde {U}}$ pak nastavit ${ displaystyle U_ {i} = { tilda {U}}}$ a označit ${ displaystyle x_ {i}}$ tak jako považováno.
Nechat ${ displaystyle { tilde {x}}}$ být považován za uzel s nejmenší hodnotou ${ displaystyle U}$ . Označení ${ displaystyle { tilde {x}}}$ tak jako přijato.
Pro každého souseda ${ displaystyle x_ {i}}$ z ${ displaystyle { tilde {x}}}$ to není přijato, vypočítejte předběžnou hodnotu ${ displaystyle { tilde {U}}}$ .
Li ${ displaystyle { tilde {U}}$ pak nastavit ${ displaystyle U_ {i} = { tilda {U}}}$ . Li ${ displaystyle x_ {i}}$ byl označen jako daleko, aktualizovat štítek na považováno.
Pokud existuje a považováno uzel, vraťte se ke kroku 3. V opačném případě ukončete.