0

我需要一种算法，从 point_a 到 point_b 花费给定的 n 个像素（或者我可以将正方形 [面积大于像素] 视为一个像素）。例如：如果在笛卡尔计划中，point_a = (0,0) 和 point_b = (100, 150)，并且 n = 350，我希望算法以这种方式运行：如果 point_a + point_b 等于 n，那么它会执行直奔终点（即 x = 100, y = 150），但如果上述条件为假，它会继续围绕计划走，直到上述条件变为真，当它满足时，它就直奔主题。

我正在考虑我上面引用的算法。我的问题是该算法的花费不能多于或少于 n，它必须是精确的 n。

我目前正在使用 Lua，但这没关系，因为我在这里想要的实际上是改进我的想法，而不是让另一个准备好。

4

2 回答 2

1

关于路径应该是什么样子的任何偏好？让算法先走直线，然后在最后一个方格来回走，直到所有步骤都用完，怎么样？或者稍微好看一点的算法看起来像这样：

假设 pointA 是 (0,0)，pointB 是 (0,p)，现在找到 pointC (x,0) 使得路径 A->C->B 的长度为 n。你可以很容易地得到 x = sqrt(n^2 - p^2)。如果 n==p, c=0 这意味着走直线。

于 2012-05-01T23:35:58.767 回答
1

我不确定您使用的是什么距离测量值。如果从 (0,0) 开始，想走到 (3,4)，那么是 5 步（欧几里得距离）还是 7 步（曼哈顿距离）？如果您使用欧几里得距离，您如何处理无理距离？

我假设您使用的是曼哈顿距离，并且我提出了一个概率解决方案。

让我们假设您距离目的地有 m 步，并且您需要在 n 步中执行此操作（n>=m）。让我们将当前状态定义为 (m,n)。如果您向目标迈出一步，问题状态为 (m-1,n-1)，离目的地更远，则状态为 (m+1,n-1)。

在每个点使用当前状态 p = 3*m/(3*m + (nm) )计算前往目的地的概率。生成一个介于 0 和 1 之间的随机数，如果它低于 p 则前往目的地，否则远离目的地。

def nextmove(m,n):
    p = 3.0*m/(3*m + (n-m) )
    if random.random() <=p:
        return m-1,n-1,'towards'
    else:
        return m+1,n-1,'farther'
于 2012-05-01T23:36:59.937 回答