有人问我以下问题: 你有 N 个点，其中两个是“开始”和“退出” 您希望从“开始”开始，遍历所有其他节点，并在“退出”结束。如果由 N 个节点组成的多边形是凸的，那么最短路径(使用欧氏距离)是多少？这里有比蛮力更好的算法吗？
编辑1:
这是 2016 年 TAP(阿根廷编程竞赛)中提出的问题，今天向我提到了它。我怀疑这里一定有比使用凸性属性的蛮力算法更好的算法，否则他们不会在比赛中要求它。 N 的约束条件也是 N < 400，所以它不能用 O(n!) 解决方案来解决
编辑2:
一个有趣的案例是: 考虑一个非常狭长的矩形，其中点位于矩形的长边上，一个在另一个前面。 起点和导出位于这条“隧道”的两端 顺时针或逆时针转动，您最终会移动 2*L，其中 L 是矩形长边的大小。 在这里从头到尾做一个之字形是最佳的，因为你只需要通过 L 一次，然后从一侧到另一侧的一些小步骤。
最佳答案
这里有比蛮力更好的算法吗？
如果你认为这个问题与动态规划你可以得到一个解决方案 O(n^2) 可以解决约束 n < 400。
这个链接有很好的解释，见问题B:https://caloventorendos.blogspot.com/2016/09/solucionario-tap-2016.html
关于algorithm - 具有起点和终点问题的凸多边形的最短距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53290319/