Предположим, нам дано несколько непересекающихся простых многоугольников на плоскости и две точки и t вне каждого многоугольника. Задача евклидова кратчайшего пути состоит в том, чтобы вычислить евклидов кратчайший путь от s до t , который не пересекает внутреннюю часть любого многоугольника. Для конкретности предположим, что координаты s и t и координаты каждой вершины многоугольника являются целыми числами.
Можно ли решить эту проблему за полиномиальное время?
Конечно, большинство вычислительных геометров сразу скажут «да»: Джон Хершбергер и Субхаш Сури описали алгоритм, который вычисляет евклидовы кратчайшие пути за время , и эта временная граница является оптимальной в алгебраической модели вычислительного дерева. К сожалению, алгоритм Хершбергера и Сури (и почти все связанные алгоритмы до и с тех пор), кажется, требуют точной реальной арифметики в следующем сильном смысле.
Назовите полигональный путь действительным, если все его внутренние вершины являются вершинами препятствий; каждый евклидов кратчайший путь действителен. Длина любого допустимого пути является суммой квадратных корней целых чисел. Таким образом, сравнение длин двух допустимых путей требует сравнения двух сумм квадратных корней, что мы не знаем, как сделать за полиномиальное время .
Более того, кажется вполне правдоподобным, что произвольный случай проблемы суммы квадратных корней может быть сведен к эквивалентной евклидовой задаче кратчайшего пути.
Итак: существует ли алгоритм полиномиального времени для вычисления евклидовых кратчайших путей? Или проблема NP-сложная? Или сумма квадратных корней трудно ? Или что-то другое?
Несколько заметок:
Кратчайшие пути внутри (или снаружи) одного многоугольника могут быть вычислены за раз без каких-либо странных численных проблем с использованием стандартного алгоритма воронки, по крайней мере, если дана триангуляция многоугольника.
На практике арифметика с плавающей запятой достаточна для вычисления путей, кратчайших до точности с плавающей запятой. Меня интересует только сложность точной проблемы.
Джон Кэнни и Джон Рейф доказали, что соответствующая задача в 3-пространстве NP-трудна (морально, потому что может быть экспоненциальное число кратчайших путей). Joonsoo Choi, Jürgen Sellen и Chee-Keng Yap описали схему аппроксимации за полиномиальное время.
Саймон Кахан и Джек Сноейнк рассмотрели аналогичные вопросы для связанной проблемы путей минимальной связи в простом многоугольнике.
Ответы:
Может быть, я что-то упускаю, но если мы рассмотрим «легкий» случай, когда все препятствия являются точками, то у нас возникает проблема вычисления кратчайшего пути между двумя вершинами в плоском графе, который, если я не ошибаюсь, известен как суммы квадратных корней трудно.
PS. Я хотел добавить комментарий, а не ответ, но не могу найти как. Я прошу прощения за то. Могут ли админы помочь мне с этим.
источник