algorithm - 具有起点和终点问题的凸多边形的最短距离

Question

有人问我以下问题:你有 N 个点，其中两个是“开始”和“退出”您希望从“开始”开始，遍历所有其他节点，并在“退出”结束。如果由 N 个节点组成的多边形是凸的，那么最短路径(使用欧氏距离)是多少？这里有比蛮力更好的算法吗？

编辑1:

这是 2016 年 TAP(阿根廷编程竞赛)中提出的问题，今天向我提到了它。我怀疑这里一定有比使用凸性属性的蛮力算法更好的算法，否则他们不会在比赛中要求它。 N 的约束条件也是 N < 400，所以它不能用 O(n!) 解决方案来解决

编辑2:

一个有趣的案例是:考虑一个非常狭长的矩形，其中点位于矩形的长边上，一个在另一个前面。起点和导出位于这条“隧道”的两端顺时针或逆时针转动，您最终会移动 2*L，其中 L 是矩形长边的大小。在这里从头到尾做一个之字形是最佳的，因为你只需要通过 L 一次，然后从一侧到另一侧的一些小步骤。

Answer 1

这里有比蛮力更好的算法吗？

如果你认为这个问题与动态规划你可以得到一个解决方案 O(n^2) 可以解决约束 n < 400。

这个链接有很好的解释，见问题B:https://caloventorendos.blogspot.com/2016/09/solucionario-tap-2016.html