3

我有两种对象，Ball和Platform。球有(x,y)坐标，平台有(x_begin, x_end, y)。最多可以有 80 个平台。

我被要求找到任何给定Ball到地面的最短路径（y=0）。请注意，此输出应仅为最小距离。

考虑到我认为最好使用蛮力的约束：计算到地面的所有可能距离，然后返回最小值。

图。1

我想我会写一个递归函数：首先计算到最近平台的垂直距离，然后分支到左右，然后再返回。断开条件是所有路径都到达地面时。

    void calculateDistances(Ball b, vector<Platform> ps, vector<float>* distances)
    {
        //The idea is to have, for every branch
        // distances[i] = vertical distance
        // distances[i+1] = distance to right
        // distances[i+2] = distance to left
        Platform* p = NULL;
        float d_y = verticalDistanceToNearestPlatform(ps, p); // "p" now holds the platform the ball is on
        if (d_y == 0) 
            return; //already on floor
        distances->push_back(d_y);

        d_x_right = distanceToRightEdgeOfPlatform(p);
        distances->push_back(d_x_right);
        d_x_left = distanceToLeftEdgeOfPlatform(p);
        distances->push_back(d_x_left);
    }

这里的问题很明显......我到底如何使这个递归？

非常感谢！

PS：这个问题打算在大约两个半小时内解决。

4

2 回答 2

4

递归解决方案（例如horizontalDistanceToGround(x, y)）将涉及计算从某个任意点(x, y)到地面上最近点的水平距离，如下所示：

  • (x, y)如果与地面之间没有平台，则返回 0。
  • 如果(x, y)与地面之间有任何平台，则找到最近的此类平台（即最大platform_y小于的平台y）。如果该平台位于，则返回和(platform_min_x, platform_max_x, platform_y)的最小值。这基本上计算了从当前 x 位置到平台末端以及从那里到地面所需的最小距离。(x - platform_min_x) + horizontalDistanceToGround(platform_min_x, platform_y)(platform_max_x - x) + horizontalDistanceToGround(platform_max_x, platform_y)

我会留下寻找(x, y)和地面之间最近的平台（如果有的话）让你弄清楚。

球到地面的最短距离为distanceToGround(ball_x, ball_y) + ball_y。

注意：根据@MooingDuck 关于垂直距离与递归无关的有用评论进行了更新。

于 2012-12-13T23:40:48.143 回答
2

您可以将此问题转换为图问题，然后使用任意数量的图搜索算法来解决它。

为此，循环遍历所有平台并为它们的每个边缘以及直接位于另一个平台边缘下方的任何点创建节点。将共享一个公共平台的所有节点连接在一起。也进行垂直连接。

对地面执行相同的操作，但不要为边添加额外的节点，也不要连接地面节点

现在，您可以使用 Dijkstra 算法（一种重构变体）在图形中搜索顶部和底部每个点之间的最短路径。选择具有最低值的结果，您就完成了。Dijkstra 的算法在 O(N^2) 中运行，其中 N 是一个节点，用于幼稚实现和 O(E+N log N)，其中 E 是智能实现的边缘。

您也可以使用 A*，这可能更容易在紧要关头实现。

搜索从边缘掉下的球会击中哪个平台很容易。把地面当作一个平台。按高度对平台进行排序。对于每个平台，从最近的平台开始，线性地穿过它下面的所有平台。查看较高平台的 x 值是否落在较低平台边缘定义的范围内。这需要 O(P^2)。（P 是平台数量。）

这可能无法直接回答您的问题（即这不是蛮力），但我认为这是指向您的更好方向。另外，如果您尝试蛮力，球可以去的所有方向最终会像 O (2^P)，这是一个令人不快的高时间复杂度。

于 2012-12-14T00:02:12.670 回答