3

私は 2 種類のオブジェクトを持ってい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: この問題は、約 2 時間半で解決される予定です。

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 のアルゴリズムは、単純な実装では O(N^2) (N はノード) で実行され、E はスマートな実装ではエッジである O(E+N log N) で実行されます。

ピンチで実装する方が簡単な場合がある A* を使用することもできます。

エッジから落ちたボールがどのプラットフォームに当たるかを検索するのは簡単です。地面をプラットフォームとして扱います。プラットフォームを高さで並べ替えます。プラットフォームごとに、その下にあるすべてのプラットフォームを直線的に進みます。最も近いものから始めます。高いプラットフォームの x 値が、低いプラットフォームのエッジによって定義された範囲内にあるかどうかを確認します。これには O(P^2) かかります。(P はプラットフォームの数です。)

これはあなたの質問に直接答えないかもしれません (つまり、これは総当りではありません) が、あなたを指し示す方が良い方向だと思います。 (2^P)、これは不快なほど高い時間の複雑さです。

于 2012-12-14T00:02:12.670 に答える