Задача евклідівого найкоротшого шляху () — це задача в обчислювальній геометрії: для заданого набору перешкод у вигляді многогранників в евклідівому просторі та двох точок знайти найкоротший шлях між цими точками, який не перетинає жодної з перешкод.

Розмірність 2 Для розмірності 2 задачу можна розв'язати за поліноміальний час в моделі обчислень, яка дозволяє додавати та порівнювати дійсні числа, незважаючи на теоретичну складність, пов'язану з .

Ці алгоритми базуються на двох різних принципах:

Алгоритми пошуку найкоротшого шляху, наприклад, алгоритм Дейкстри на , побудованому на основі перешкод.

Поширення "хвильового фронту'' від однієї з точок, доки він не досягне іншої (підхід, що називається неперервним методом Дейкстри)

Вищі розмірності У розмірностях три (і вище) ця задача є NP-складною в загальному випадку, але існують конструктивні алгоритми апроксимації, які розв'язують задачу за поліноміальний час.

Вони базуються на ідеї знаходження відповідної набору точок на ребрах перешкод і виконання обчислень на графі видимості з використанням цих точок.

Існує багато способів обчислення найкоротших шляхів, які лежать на поверхні многогранника. Нехай задано опуклий многогранник та дві точки і на його поверхні.

Задача полягає в обчисленні найкоротшого шляху, який ніколи не залишає поверхню і з'єднує і . Це є узагальненням задачі з розмірності 2, але вона набагато простіша ніж тривимірна задача.

Модифікації Існують модифікації цієї задачі, де перешкоди є "ваговими'', тобто через перешкоду можна пройти, але це спричиняє додаткові витрати. Класична задача -- це окремий випадок, де перешкоди мають нескінченну вагу. В літературі це задача вагових областей.

Див. також Задача про пошук найкоротшого шляху у графі Найкоротший шлях на дереві

Замітки

J. Canny and J. H. Reif, "New lower bound techniques for robot motion planning problems", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49-60.

Джерела . . . . . . . . . .

Посилання Реалізація алгоритму найкоротшого шляху Евкліда в програмному забезпеченні Digital Geometric Kernel