关于算法的一个小提示

2012-5-1 22:14:36
收藏：0
阅读：91
评论：2

我需要一个算法，从点 a 到点 b，花费给定的 n 像素（或者我可以将面积大于一个像素的方块视为一个像素）。 例如： 如果在笛卡尔平面中，点 a = (0,0) 和点 b = (100,150)，n = 350，我想让算法按如下方式行动： 如果点 a 和点 b 的和等于 n，则直接走向最终点（即 x=100，y=150） 但如果上述条件不成立，则绕着计划走，直到上述条件成立，然后直接走向该点。

我在思考上述算法的一些内容。我的问题是，算法不能花费比 n 更多或更少的像素，它必须恰好是 n。

我目前正在使用 Lua，但这并不重要，因为我想在这里改进我的想法，而不是准备另一种想法。

原文链接 https://stackoverflow.com/questions/10404999

点赞
stackoverflow用户1286272
stackoverflow用户1286272

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

假设点A是(0,0)，点B是(0,p)，现在找到点C(x,0)满足路径A->C->B的长度为n。很容易得到x = sqrt(n^2 - p^2)。如果n==p，c=0，这意味着直接走直线。

2012-05-01 23:35:58
stackoverflow用户786351
stackoverflow用户786351

我不确定你使用的距离度量是什么。如果你从（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 +（n-m)）。生成0到1之间的随机数，如果小于p，则向目标前进，否则远离目标。

def nextmove(m，n):
    p = 3.0*m/(3*m + (n-m) )
    if random.random() <=p:
        return m-1，n-1，'向目标前进'
    else:
        return m+1，n-1，'远离目标'
2012-05-01 23:36:59

作者:

stackoverflow用户1282910

stackoverflow用户1282910
推荐文章