Быстрый походный метод - Fast marching method

В метод быстрого марша^[1] численный метод, созданный Джеймс Сетиан для решения краевые задачи из Уравнение эйконала:

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

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

Обычно такая задача описывает эволюцию замкнутой поверхности как функцию времени. ${\displaystyle u}$ со скоростью ${\displaystyle f}$ в нормальном направлении в точке ${\displaystyle x}$ на распространяющейся поверхности. Указана функция скорости и время, в которое контур пересекает точку. ${\displaystyle x}$ получается путем решения уравнения. В качестве альтернативы, ${\displaystyle u(x)}$ можно рассматривать как минимальное время, необходимое для достижения ${\displaystyle \partial \Omega }$ начиная с точки ${\displaystyle x}$. Метод быстрого марша использует это преимущество. оптимальный контроль интерпретация проблемы с целью построения решения извне, исходя из «известной информации», то есть граничных значений.

Алгоритм похож на Алгоритм Дейкстры и использует тот факт, что информация течет только наружу из области засева. Эта проблема - частный случай методы установки уровня. Существуют более общие алгоритмы но обычно медленнее.

Расширения на неплоские (триангулированные) области решения

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

для поверхности ${\displaystyle S}$ и ${\displaystyle x\in S}$, были представлены Рон Киммел и Джеймс Сетиан.

• 

  Лабиринт как кратчайший путь функции скорости

• 

  Мульти-трафареты карты расстояний со случайными исходными точками

Алгоритм

Сначала предположим, что область была дискретизирована в сетку. Мы будем называть точки сети узлами. Каждый узел ${\displaystyle x_{i}}$ имеет соответствующее значение ${\displaystyle U_{i}=U(x_{i})\approx u(x_{i})}$.

Алгоритм работает так же, как алгоритм Дейкстры, но отличается тем, как вычисляются значения узлов. В алгоритме Дейкстры значение узла вычисляется с использованием одного из соседних узлов. Однако при решении PDE в ${\displaystyle \mathbb {R} ^{n}}$, между ${\displaystyle 1}$ и ${\displaystyle n}$ соседних узлов используются.

Узлы помечены как далеко (еще не посещал), считается (посещено и предварительно присвоено значение), и принято (посещены и присвоено значение постоянно).

1. Назначьте каждый узел ${\displaystyle x_{i}}$ значение ${\displaystyle U_{i}=+\infty }$ и обозначьте их как далеко; для всех узлов ${\displaystyle x_{i}\in \partial \Omega }$ набор ${\displaystyle U_{i}=0}$ и этикетка ${\displaystyle x_{i}}$ в качестве принято.
2. Для каждого удаленного узла ${\displaystyle x_{i}}$, использовать Формула обновления эйконала рассчитать новое значение для ${\displaystyle {\tilde {U}}}$. Если ${\displaystyle {\tilde {U}}<U_{i}}$ затем установите ${\displaystyle U_{i}={\tilde {U}}}$ и этикетка ${\displaystyle x_{i}}$ в качестве считается.
3. Позволять ${\displaystyle {\tilde {x}}}$ быть рассматриваемым узлом с наименьшим значением ${\displaystyle U}$. Этикетка ${\displaystyle {\tilde {x}}}$ в качестве принято.
4. Для каждого соседа ${\displaystyle x_{i}}$ из ${\displaystyle {\tilde {x}}}$ то, что не принято, рассчитайте ориентировочное значение ${\displaystyle {\tilde {U}}}$.
5. Если ${\displaystyle {\tilde {U}}<U_{i}}$ затем установите ${\displaystyle U_{i}={\tilde {U}}}$. Если ${\displaystyle x_{i}}$ был помечен как далеко, измените метку на считается.
6. Если существует считается node, вернитесь к шагу 3. В противном случае завершите работу.

Смотрите также

• Метод установки уровня
• Метод быстрого подметания
• Алгоритм Беллмана – Форда

внешняя ссылка

• Методы Дейкстры для уравнения Эйконала J.N. Цициклис, 1995 г.
• Метод быстрого марша и его приложения Джеймс А. Сетиан
• Методы быстрого нанесения мульти-трафаретов
• Мульти-трафареты. Быстрая реализация Matlab.
• Детали реализации методов быстрого перехода
• Обобщенный метод быстрого марша Автор: Forcadel et al. [2008] для приложений сегментации изображений.
• Реализация в Python метода Fast Marching
• См. Главу 8 в Дизайн и оптимизация нанооптических элементов путем связывания изготовления с оптическим поведением

Примечания

1. J.A. Сетиан. Метод установки быстрого маршевого уровня для монотонно продвигающихся фронтов, Proc. Natl. Акад. Наук, 93, 4, с. 1591--1595, 1996. [1]