3

NXM グリッドがあります。グリッドの 1 つの正方形がソースで、1 つが宛先です。ソースと目的地を含むグリッドの各正方形には、いくつかの標高 (値 0 ～ 9 の整数) があります。次の制限を満たすソースから宛先への最小コスト パスを見つける必要があります。

  1. パスは連続している必要があります。つまり、隣接する正方形間のみ (斜めの隣接ではありません) でなければなりません。
  2. 標高の高いところから低いところへしか行けません。

任意の正方形の高さを増減できます。標高の変化量がコストとしてカウントされます。標高が変化しない場合は、ゼロコストと見なされます。したがって、ソースから目的地までのパスの総コストは、パスに含まれる正方形の標高の変化です。さらに、ソースの標高は変更できませんが、目的地の標高は変更できます。

Djikstra や APSP などのアルゴリズムを適用しようとしましたが、解決策に到達できませんでした。この問題で私を助けてください。

4

3 に答える 3

1

実際には、目的地の広場の標高も変更できないと考えるかもしれません。標高を上げる必要がないからです。

さて、古典的な Dijkstra(-like) アルゴリズムでは、グリッドのすべての正方形には、この正方形に到達できる価格があると言えます。つまり、ソース スクエアの価格は0 です。次に、ループ内で次に安いスクエアを取得し、そこから価格が大きいすべての隣接するスクエアに移動しようとします。

あなたの問題には、余分な自由度があります。それは、正方形の標高レベルです。つまり、正方形に移動すると、その高さを変更できます。

最も単純な「ブルートフォース」ソリューションは次のとおりです。

  1. すべてのセルをチェックし、標高レベルのセット (つまり、すべての高さのスペクトル) を作成します。H個の異なる高さがあるとします。
  2. 正方形の状態をその位置と高さとして定義します。ダイクストラ グラフの観点から問題を定義します。
  3. すべての正方形について、実際の標高を表す頂点をグラフに追加します。次に、より大きな標高でそれを表す追加の頂点を追加します (ソースと宛先の四角以外に)。すべての正方形に最大H個の頂点があるようにします。
  4. 実際の位置からの高さとして、すべての頂点の内部価格を定義します。したがって、すべての正方形に対して、内部価格= 0 (実際の高さ) を持つ頂点と、適切な内部価格を持つ高騰したポジションを表す頂点の数があります。
  5. 有向辺によって隣接する正方形を表す接続された頂点。ソース頂点に少なくともターゲット頂点の標高がある場合にのみ、エッジを配置します。

次に、Dijkstra (または A*) アルゴリズムによって最短経路を見つけます。移動のコストは、ターゲット頂点の内部価格と見なされます (エッジには価格がありません)。

簡単に言えば、「階層化された」グラフを作成しました。各層はオプションの高さに対応しています。各位置で、現在のレイヤーで移動するか、下に移動することができます。

問題の複雑さが増すことは言うまでもありません。頂点の数は、 Hの係数 (最大) で増加します。同じことがエッジの数にも当てはまります。

基本的に、パス検索には複雑さがlog(N) * N * Mあり、Nはセル数の 2 乗、Mは接続順序 (接続された最近傍の数) です。インフレーション後、複雑さはH^2倍 (最大) 増加します。

したがって、このアルゴリズムの効率は、異なる高さの数に依存します。高さの数が少ない場合、アルゴリズムは効率的です。ただし、すべての正方形の高さが異なる場合は、おそらく別のアプローチを使用する必要があります。

于 2012-05-19T21:21:47.920 に答える
1

これは、別の次元での単純な最短距離問題の例です。次のように問題を定式化してみてください。cost[n][m][max_height] = {INFINITY};

コスト[srcX][srcY][高さ[srcX][srcY]] = 0;

現在 cost[x+1][y][ht] = min(cost[x+1][y][ht], cost[x][y][q_ht] + (q_ht - ht) ) for q_ht はmax_height から ht. アイデアは、許容される高さ (つまり、高さ >= ht) から最小のコストで (x+1,y,ht) に到達することです。これも、すべての ht(0 から max_height) について計算する必要があります。完全な実装はここにあります:-

#define HIGHVAL 100000000
#define XI (x + a[i])
#define YI (y + b[i])

int n,m;

bool isvalid(int x,int y)
{
    return (x>=0 && y>=0 && x<n && y<m);
}

int main()
{

    int pondX, pondY;
    int farmX, farmY;

    cin>>n>>m>>pondX>>pondY>>farmX>>farmY;
    pondX--, pondY--, farmX--, farmY--;

    int height[n][m];
    string s;

    for(int i=0; i<n; i++)
    {
        cin>>s;
        for(int j=0; j<m; j++)
            height[i][j] = (int)(s[j] - '0');
    }

    int ht = height[pondX][pondY];
    int cost[n][m][ht+1];
    bool visited[n][m];

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            for(int k=0; k<ht+1; k++)
                cost[i][j][k] = HIGHVAL;

    cost[pondX][pondY][ht] = 0;
    int a[4]= {0,0,1,-1};
    int b[4]= {1,-1,0,0};

    int ci = pondX, cj = pondY;
    queue<int> qx;
    queue<int> qy;

    visited[pondX][pondY] = 1;

    memset(visited, 0, sizeof(visited));
    qx.push(pondX);
    qy.push(pondY);

    while(qy.size())
    {
        int x = qx.front();
        int y = qy.front();

        qx.pop();
        qy.pop();

        for(int i=0; i<4; i++)
        {
            int temp = 0;
            if(isvalid(XI, YI))
            {
                if(!visited[XI][YI])
                {
                    qx.push(XI);
                    qy.push(YI);
                    visited[XI][YI] = 1;
                    temp = 1;
                }

                for(int j=ht; j>=0; j--)
                {
                    int q = HIGHVAL;
                    for(int k=ht; k>=j; k--)
                    {
                        q = min(q, cost[x][y][k] + abs(j - height[XI][YI]));
                    }

                    if(cost[XI][YI][j] > q)
                    {
                        cost[XI][YI][j] = q;

                        if(visited[XI][YI] && !temp)
                        {
                            qx.push(XI);
                            qy.push(YI);
                        }
                    }
                }
            }

        }
    }

    int ans=HIGHVAL;
    for(int i=0; i<=ht; i++)
        ans = min(ans, cost[farmX][farmY][i]);

    cout<<ans;
    //cout<<" "<<n<<m;
    return 0;

}
于 2012-05-24T11:45:47.977 に答える
0

「標高の変化」は一見、問題を複雑にしているように見えますが、もう少し注意深く考えてみると、そうではありません。まず、正方形の標高を下げる理由はありません。上げるだけです。そして、検索の現在の「分岐」の「終了」正方形以外に、正方形を持ち上げる理由はありません。と、どのトラバーサルでも、次の正方形に移動できるようにするために必要な量を超えて正方形の高さを上げる理由は決してありません。最適なパスがそれ自体にループバックすることは決してないことを付け加えるかもしれません。そのため、検索の各ステップで、持ち上げる必要がある正方形と、それをどれだけ持ち上げるかは、完全に決定論的です。それを見つけるために検索を使用する必要はありません。したがって、@valdo が提案した「階層化グラフ」は実際には必要ありません。

その洞察があれば、ほぼすべての標準的なパス検索アルゴリズムを簡単な方法で使用できます。

于 2012-05-19T22:46:11.350 に答える