Мне задали следующий вопрос: у вас есть N точек, две из которых - «начало» и «выход». Вы хотите начать с «старта», пройти через все остальные узлы и в конечном итоге «выход".Какой кратчайший путь (с использованием евклидова расстояния), если многоугольник, образованный N узлами, является выпуклым?Есть ли лучший алгоритм, чем грубая сила, здесь?
edit1:
Эта проблема была задана в TAP в 2016 году (Аргентинский конкурс программистов) и была упомянута мне сегодня.Я подозреваю, что здесь должен быть алгоритм, превосходящий грубую силу, использующий свойство выпуклости, иначе они не спросят его на соревновании.Кроме того, ограничения для N были N <400, поэтому его нельзя было бы решить с помощью решения O (n!) </p>
edit2:
Вот один интересный случай: Рассмотрим очень длинный иузкий прямоугольник, где точки находятся на длинных сторонах прямоугольника, одна перед другой.Начальная и конечная точки находятся на противоположных концах этого «туннеля», делая поворот по часовой стрелке или против часовой стрелки, и вы в конечном итоге переместитесь на 2 * L, где L - размер длинной стороны прямоугольника.В этом случае оптимальным будет сделать зигзаг от начала до конца, поскольку вам нужно всего лишь пройти L один раз, а затем сделать несколько небольших шагов от одной стороны к другой.