algorithm - 旅行的最短路径

Question

给定相连的线段 A->B->C->D(A->B 是一条线段，然后 B->C 是另一条线段，依此类推)，如何找到从 A->D 给出了以下选项？

1. 您可以沿着线段行驶，费用为 $1/unit_distance
2. 您可以从任何线段上的某个点“跳”到其他线段上的其他点，这会花费您 2 美元/unit_distance 在该“跳转”中覆盖，然后再次在选项 #1 和选项 #2 之间进行选择剩余行程。

线段是二维线。

例如假设您需要从 (0,0)->(2,2)->(2,-2) 旅行。有很多选择可以做到这一点。我在下面列出 3:

1. 如果您完全遵循选项 #1，则成本为 2√2(从 (0,0) 到 (2,2))+ 4(从 (2,2) 到 (2,-2))<
2. 如果您从 (0,0) 跳到 (2,-2)，则覆盖的距离为 2√2，因此成本为 4√2(跳跃 2 美元/单位)。
3. 但是，如果您从 (0,0) 跳到 (2,-1)，然后按照选项 #1 从 (2,-1) 跳到 (2,-2)，这会花费您2√5(跳跃)+ 1(跟随选项 #1)。

线段的数量可能会有所不同。我正在考虑为此制定一些 LPP，但无法进一步进行。有人可以帮我找到此类问题的最小值吗？

Answer 1

我不认为 LPP 可以直接用于解决问题，因为距离是非线性的，即如果您将任何线段上的任何点 P 用作距离度量，那么线段之后的 A 的距离只有，然后“跳跃”距离函数测量通过“跳跃”从距 A 距离 x 的点 P 移动到距 A 距离 x' 的另一个点 P' 的成本，例如 Hop(x, x')，是x 和 x' 都是非线性的，因为欧氏距离度量是非线性的。

但是，我们先假设只有两条路段(即路径是 A-B-C)。跳转的唯一可能模式是从段 A-B 跳到段 B-C，因为在单个段内跳转没有意义。让这三个点位于坐标 A=(ax,ay)、B=(bx,by) 和 C=(cx,cy) 处。然后考虑线段 A-B 上的点 P 和线段 B-C 上的点 P'，使得 P 到 A 的距离为 d，P' 到 B 的距离为 d'。 P到P'通过线段的距离为

d' + AB - d

其中 AB 是从 A 到 B 的(恒定)距离，通过跳跃它是

2 * sqrt((x - x')^2 + (y - y')^2)

在哪里

x =  ax + d  * (bx - ax) / AB
y =  ay + d  * (by - ay) / AB
x' = bx + d' * (cx - bx) / BC
y' = bx + d' * (cy - by) / BC

其中 BC 是 B 到 C 的距离。

那么两个距离的差就是

2 * sqrt((x - x') (x - x') + (y - y') (y - y')) - d' + AB + d

而且我确信它可以通过任何标准技术解决局部最小值问题。最小值表示那些对 (P, P')，在这些对中，跳跃对跟随段的好处无法提高，并且根据问题的几何形状，我真的希望只有有限数量的这种最小值对。

这种相同的方法可以用于路径上的任何两个段对，因为没有使用段连接的事实，因此以这种方式，您可以建立一个具有有限分支的等效网络(如其中一个建议的那样)上面的评论)，然后使用简单的寻路算法计算出最优结果。