-3

我们在平面上给出以下 7 个点 P1, P2, ..., P7，其 x 和 y 坐标如下：

点 P1 P2 P3 P4 P5 P6 P7

x 值 10 12 19 11 12 14 18

y 值 25 23 17 6 20 23 25

我们希望找到连接所有 7 个点的最短封闭路线，条件是路线从最左边开始，严格向右到最右边，然后严格向左返回起点。
任何人都可以提出一个动态的方法（算法）来解决这个问题吗？

4

2 回答 2

2

如前所述，从左到右和从右到左有 2^5 (32) 条可能的路径。只需评估其中的每一个并选择最短的。

您可以在向左或向右时选择每个中间点。因此有 2^5 种可能性。

于 2013-10-01T12:10:32.540 回答
0

这是非常简单的 squareroot((x2-x1)^2+(y2-y1)^2) x2 是 p2 的 x 并且 x1 是 p1 的点然后取所有距离并得到最小的结果

或者您也可以查看 dijekstra 算法

于 2013-10-01T12:06:36.757 回答