Метод быстрого марша

Метод быстрого марша — численный метод , созданный Джеймсом Сетианом для решения краевых задач Эйконала уравнения :

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

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

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

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

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

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

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

• 
  Лабиринт как кратчайший путь функции скорости
• 
  Мультитрафареты карты расстояний со случайными исходными точками

Алгоритм

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

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

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

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

См. также

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

Внешние ссылки

• Методы Дейкстры для уравнения Эйконала Дж. Н. Цициклис, 1995 г.
• Метод быстрого марша и его применение Джеймс А. Сетиан
• Методы быстрого марша с использованием нескольких трафаретов
• Реализация Multi-Stencils Fast Marching Matlab
• Детали реализации методов быстрого марша
• Обобщенный метод быстрого марша Forcadel et al. [2008] за применение в сегментации изображений.
• Реализация метода быстрого марша на Python
• См. главу 8 в разделе «Проектирование и оптимизация нанооптических элементов путем сопоставления изготовления с оптическим поведением». Архивировано 20 августа 2013 г. на Wayback Machine.