Евклидов кратчайший путь
-
Задача о кратчайшем евклидовом пути
- Задача нахождения кратчайшего пути между двумя точками, не пересекающего препятствия в евклидовом пространстве.
-
Двумерные алгоритмы
- Решение задачи возможно за полиномиальное время с использованием модели вычислений, позволяющей работать с действительными числами.
- Алгоритмы основаны на кратчайшем пути Дейкстры или непрерывном методе Дейкстры.
-
Трехмерные и более высокие размеры
- В трех и более измерениях задача NP-сложна, но существуют эффективные алгоритмы аппроксимации.
- Алгоритмы используют выборку точек на краях препятствий для построения графика видимости.
-
Вариации задачи
- Существуют задачи с взвешенными препятствиями, где преодоление препятствия имеет дополнительную плату.
- Стандартная задача — это частный случай с бесконечным весом препятствий.
-
Ссылки и примечания
- Статья содержит внешние ссылки и примечания о помощи в расширении Википедии.