Быстрый метод походный [1] является численным методом , созданным Джеймсом Sethian для решения краевых задач на уравнениях Eikonal :
Обычно такая задача описывает эволюцию замкнутой поверхности как функцию времени. со скоростью в нормальном направлении в точке на распространяющейся поверхности. Указана функция скорости и время, в которое контур пересекает точку.получается путем решения уравнения. В качестве альтернативы, можно рассматривать как минимальное время, необходимое для достижения начиная с точки . Метод быстрого перехода использует преимущества этой оптимальной управленческой интерпретации проблемы, чтобы построить решение, исходя из «известной информации», то есть граничных значений.
Алгоритм аналогичен алгоритму Дейкстры и использует тот факт, что информация течет только наружу из области засева. Эта проблема - частный случай методов установки уровня . Существуют более общие алгоритмы, но обычно они работают медленнее.
Расширения на неплоские (триангулированные) области решения
для поверхности а также , были представлены Роном Киммелом и Джеймсом Сетхианом .
Лабиринт как кратчайший путь функции скорости
Мульти-трафареты карты расстояний со случайными исходными точками
Алгоритм
Во-первых, предположим, что область была дискретизирована в сетку. Мы будем называть точки сетки узлами. Каждый узел имеет соответствующее значение .
Алгоритм работает так же, как алгоритм Дейкстры, но отличается тем, как вычисляются значения узлов. В алгоритме Дейкстры значение узла вычисляется с использованием одного из соседних узлов. Однако при решении PDE в, между а также из соседних узлов используются .
Узлы помечаются как дальние (еще не посещенные), рассматриваемые (посещенные и предварительно присвоенное значение) и принятые (посещенные и присвоенное значение постоянно).
- Назначьте каждый узел значение и пометьте их как можно дальше ; для всех узлов набор и этикетка как принято .
- Для каждого удаленного узла , используйте формулу обновления Эйконала, чтобы вычислить новое значение для. Если затем установите и этикетка как считается .
- Позволять быть рассматриваемым узлом с наименьшим значением . Этикеткакак принято .
- Для каждого соседа из что не принято, рассчитайте ориентировочное значение .
- Если затем установите . Еслибыл обозначен как далеко , обновить метку считается .
- Если существует рассматриваемый узел, вернитесь к шагу 3. В противном случае завершите работу.
Смотрите также
Внешние ссылки
- Методы Дейкстры для уравнения Эйконала Ю. Н. Цициклис, 1995
- Метод быстрого марша и его приложения Джеймс А. Сетиан
- Методы быстрого марша с несколькими трафаретами
- Мульти-трафареты. Быстрая реализация Matlab.
- Детали реализации методов быстрого перехода
- Обобщенный метод Fast Marching Forcadel et al. [2008] для приложений сегментации изображений.
- Реализация в Python метода Fast Marching
- См. Главу 8 в разделе « Проектирование и оптимизация нанооптических элементов путем связывания изготовления с оптическими характеристиками».