递归算法的实现

Question

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

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

考虑到这些限制，我认为最好使用暴力:计算到地面的所有可能距离，然后返回最小值。

​

​

我想我要做的是写一个递归函数:首先计算到最近平台的垂直距离，然后向右和向左分支，然后再返回。当所有路径都到达地面时，就会出现中断情况。

    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:这个问题应该在大约两个半小时内解决。

Answer 1

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

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

我将把寻找(x, y)和地面(如果有)之间最近的平台留给您来解决。

那么从球到地面的最短距离就是distanceToGround(ball_x, ball_y) + ball_y。

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

Answer 2

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

要执行此操作，请遍历所有平台，并为其每条边以及另一个平台的边正下方的任何点创建节点。将共享公共平台的所有节点连接在一起。也要进行垂直连接。

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

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

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

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

这可能不会直接回答你的问题(即这不是蛮力)，但我认为这是一个更好的方向。另外，如果你尝试用蛮力把球的所有方向都用力，结果就是O(2^P)，这是一个令人不快的高时间复杂度。