4

この問題は、右または下に移動するだけで、ポイントA（常に左上）からポイントB（常に右下）までのNxMグリッド内の最短経路を見つける必要がある場合に発生します。簡単そうですね。ここに問題があります。現在座っているタイルに表示されている数字しか移動できません。説明させてください：

2 5 1 2
9 2 5 3
3 3 1 1
4 8 2 7

この4x4グリッドでは、最短経路は3つのステップをたどり、左上から2ノードから3に、そこから3ノードを右に1に、次に1ノードをゴールまで歩きます。

[2] 5  1  2
 9  2  5  3
[3] 3  1 [1]
 4  8  2 [7]

最短経路でない場合は、次のルートを使用することもできます。

[2] 5 [1][2]
 9  2  5  3
 3  3  1 [1]
 4  8  2 [7]

残念ながら、それはなんと4つのステップを踏むことになり、したがって、私の興味はありません。それは物事を少しクリアする必要があります。次に入力について。

ユーザーは次のようにグリッドを入力します。

5 4      // height and width
2 5 2 2  //
2 2 7 3  // the
3 1 2 2  // grid
4 8 2 7  //
1 1 1 1  //

宿題

私はこれを熟考しましたが、入力されたグリッドを単純化して重み付けされていない（または負の重みの）グラフにし、その上でdijkstraやA *（またはそれらの線に沿ったもの）のようなものを実行するよりも良い解決策を見つけることはできません。さて...これは私が迷子になる部分です。私は最初に何かを実装しました（またはすぐにスラッシュに投げるために何かを実装しました）。dijkstraやA*などとは何の関係もありません。単純な幅優先探索。

コード

#include <iostream>
#include <vector>

struct Point;

typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<Point> vector_point;

struct Point {
    int y, x;
    vector_point Parents;
    Point(int yPos = 0, int xPos = 0) : y(yPos), x(xPos) { }

    void operator << (const Point& point) { this->Parents.push_back(point); }
};

struct grid_t {
    int height, width;
    vector_2D tiles;

    grid_t() // construct the grid
    { 
        std::cin >> height >> width; // input grid height & width

        tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles

        for(int i = 0; i < height; i++)     //
            for(int j = 0; j < width; j++)  // input each tile one at a time
                std::cin >> tiles[i][j];    // by looping through the grid
    }
};

void go_find_it(grid_t &grid)
{
    vector_point openList, closedList;
    Point previous_node; // the point is initialized as (y = 0, x = 0) if not told otherwise
    openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course

    do
    {
        closedList.push_back(openList.back()); // the tile we are at is good and checked. mark it so.
        openList.pop_back(); // we don't need this guy no more

        int y = closedList.back().y; // now we'll actually
        int x = closedList.back().x; // move to the new point

        int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.

        if(y + jump < grid.height) // if we're not going out of bounds
        { 
            openList.push_back(Point(y+jump, x)); // 
            openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
        }
        if(x + jump < grid.width) // if we're not going out of bounds
        { 
            openList.push_back(Point(y, x+jump)); // push in the new promising point
            openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
        }
    }
    while(openList.size() > 0); // when there are no new tiles to check, break out and return
}

int main()
{
    grid_t grid; // initialize grid

    go_find_it(grid); // basically a brute-force get-it-all-algorithm

    return 0;
}

また、実行時間は1秒を超えることはできず、グリッドの最大の高さと幅は1000です。すべてのタイルも1から1000までの数字です。

ありがとう。

編集されたコード

#include <iostream>
#include <vector>

struct Point;

typedef std::vector<int> vector_1D;
typedef std::vector< std::vector<int> > vector_2D;
typedef std::vector<Point> vector_point;

struct Point {
    int y, x, depth;
    vector_point Parents;
    Point(int yPos = 0, int xPos = 0, int dDepth = 0) : y(yPos), x(xPos), depth(dDepth) { }

    void operator << (const Point& point) { this->Parents.push_back(point); }
};

struct grid_t {
    int height, width;
    vector_2D tiles;

    grid_t() // construct the grid
    { 
        std::cin >> height >> width; // input grid height & width

        tiles.resize(height, vector_1D(width, 0)); // initialize grid tiles

        for(int i = 0; i < height; i++)     //
            for(int j = 0; j < width; j++)  // input each tile one at a time
                std::cin >> tiles[i][j];    // by looping through the grid
    }
};

int go_find_it(grid_t &grid)
{
    vector_point openList, closedList;
    Point previous_node(0, 0, 0); // the point is initialized as (y = 0, x = 0, depth = 0) if not told otherwise
    openList.push_back(previous_node); // (0, 0) is the first point we want to consult, of course

    int min_path = 1000000;

    do
    {
        closedList.push_back(openList[0]); // the tile we are at is good and checked. mark it so.
        openList.erase(openList.begin()); // we don't need this guy no more

        int y = closedList.back().y; // now we'll actually move to the new point
        int x = closedList.back().x; //
        int depth = closedList.back().depth; // the new depth

        if(y == grid.height-1 && x == grid.width-1) return depth; // the first path is the shortest one. return it

        int jump = grid.tiles[y][x]; // 'jump' is the number shown on the tile we're standing on.

        if(y + jump < grid.height) // if we're not going out of bounds
        { 
            openList.push_back(Point(y+jump, x, depth+1)); // 
            openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
        }
        if(x + jump < grid.width) // if we're not going out of bounds
        { 
            openList.push_back(Point(y, x+jump, depth+1)); // push in the new promising point
            openList.back() << Point(y, x); // push in the point we're at right now, since it's the parent node
        }
    }
    while(openList.size() > 0); // when there are no new tiles to check, break out and return false

    return 0;
}

int main()
{
    grid_t grid; // initialize grid

    int min_path = go_find_it(grid); // basically a brute-force get-it-all-algorithm

    std::cout << min_path << std::endl;
    //system("pause");
    return 0;
}

プログラムは正解を出力します。次に、最適化する必要があります（実行時間は長すぎます）。これに関するヒントはありますか？最適化は私が嫌うことの1つです。

答え

結局、ソリューションは小さなコードで構成されているように見えました。私が好きなように、少ないほど良いです。美しいソリューションを提供してくれたDejanJovanovićに感謝します

#include <iostream>
#include <vector>
#include <algorithm>

struct grid_t {
    int height, width;
    std::vector< std::vector<int> > tiles;
    std::vector< std::vector<int> > distance;

    grid_t() // construct the grid
    { 
        std::cin >> height >> width; // input grid height & width

        tiles.resize(height, std::vector<int>(width, 0)); // initialize grid tiles
        distance.resize(height, std::vector<int>(width, 1000000)); // initialize grid tiles

        for(int i = 0; i < height; i++)     //
            for(int j = 0; j < width; j++)  // input each tile one at a time
                std::cin >> tiles[i][j];    // by looping through the grid
    }
};

int main()
{
    grid_t grid; // initialize grid

    grid.distance[0][0] = 0;
    for(int i = 0; i < grid.height; i++) {
        for(int j = 0; j < grid.width; j++) {
            if(grid.distance[i][j] < 1000000) {
                int d = grid.tiles[i][j];
                if (i + d < grid.height) {
                    grid.distance[i+d][j] = std::min(grid.distance[i][j] + 1, grid.distance[i+d][j]);
                }
                if (j + d < grid.width) {
                    grid.distance[i][j+d] = std::min(grid.distance[i][j] + 1, grid.distance[i][j+d]);
                }
            }
        }
    }
    if(grid.distance[grid.height-1][grid.width-1] == 1000000) grid.distance[grid.height-1][grid.width-1] = 0;
    std::cout << grid.distance[grid.height-1][grid.width-1] << std::endl;
    //system("pause");
    return 0;
}
4

4 に答える 4

3

難しく考えすぎだよ。:)幅優先探索を実行します。ソリューションスペースは、各ノードが「右」または「下」に分岐する二分木です。現在のポイントから、ダウンポイントとライトポイントを生成し、それらの座標をキューに詰め込み、終了するまで繰り返します。

チェックせずに、次のようなもの：

queue = [{ x: 0, y: 0, path: [] }] # seed queue with starting point
p = nil
do
  raise NoSolutionException if p.empty? # solution space exhausted
  p = queue.pop # get next state from the back of the queue
  break if p.x == MAX_X - 1 && p.y == MAX_Y - 1 # we found final state
  l = grid[p.x][p.y] # leap length

  # add right state to the front of the queue
  queue.unshift({x: p.x + l, y: p.y, path: p.path + [p] }) if p.x + l <= MAX_X

  # add down state to the front of the queue
  queue.unshift({x: p.x, y: p.y + l, path: p.path + [p] }) if p.y + l <= MAX_Y
end
puts p.path

読者のための演習として残されたC++への醜い：p

于 2013-01-04T13:45:32.793 に答える
3

グラフを作成する必要があります。これは、マトリックス上で1回のスキャンを使用する動的計画法で簡単に解決できます。

距離行列D[i、j]を開始時に+ infに設定でき、D [0,0] = 0です。行列をトラバースしている間は、次のようにします。

if (D[i,j] < +inf) {
  int d = a[i, j];
  if (i + d < M) {
    D[i + d, j] = min(D[i,j] + 1, D[i + d, j]);
  }
  if (j + d < N) {
    D[i, j + d] = min(D[i,j] + 1, D[i, j + d]);
  }
}

最終的な最小距離はD[M-1、N-1]です。パスを再構築したい場合は、最短パスがどこから来たかを示す別のマトリックスを保持できます。

于 2013-01-04T17:15:14.933 に答える
2

重み付けされていない有向グラフを作成します。

  1. NxM個の頂点があります。以下では、頂点vはグリッドの正方形に対応しvます。
  2. 1回の移動でグリッドの正方形から正方形にジャンプできる場合は、頂点uから正方形への円弧があります。vuv

次に、右上の頂点から左下の頂点への最短経路アルゴリズムを適用します。

最後に、実際にグラフを作成する必要はないことに注意してください。元のグリッドに関して、最短経路アルゴリズムを簡単に実装できます。

于 2013-01-04T13:53:46.473 に答える
0

それを機能させるために力ずくのアプローチから始めて、そこから最適化します。総当たり攻撃は単純明快です。再帰的に実行します。2つの動きを取り、それらを繰り返します。有効な回答をすべて収集し、最小限に抑えます。実行時間が長すぎる場合は、さまざまな方法で最適化できます。たとえば、一部の移動は無効である可能性があり（グリッドの寸法を超えているため）、削除することができます。最悪の場合の入力が目的の速度で実行されるまで、最適化を続けます。

そうは言っても、パフォーマンス要件は、同じシステムと入力を使用している場合にのみ意味があり、それでもいくつかの注意点があります。Big O表記は、パフォーマンスを分析するためのはるかに優れた方法です。さらに、アルゴリズムを示し、プロファイリングの必要性を排除することができます。

于 2013-01-04T13:50:22.707 に答える