3

我们有 NXM 网格。网格的一个正方形是源，一个是目标。包括源和目标的每个网格正方形都有一些高度（值 0-9 的整数）。我们必须找到一条满足以下限制的从源到目的地的最低成本路径：

  1. 路径必须是连续的，即仅在相邻方格之间（不是对角邻接）。
  2. 一个人只能从高海拔到低海拔。

任何正方形的标高都可以增加或减少。海拔变化量计为成本。如果海拔没有变化，则视为零成本。因此，从源到目的地的路径总成本是路径中方格高度的变化。此外，源的海拔不能改变，但目的地的海拔可以。

我尝试应用一些算法，如 Djikstra 和 APSP，但无法找到任何解决方案。请帮我解决这个问题。

4

3 回答 3

1

实际上你可能会认为目标方格的标高也不能改变，因为不需要抬高它。

现在，在经典的 Dijkstra(-like) 算法中，您会说网格的每个方格都有一个价格，您可以达到这个方格。也就是说，您的源方格的价格=0，然后在一个循环中，您选择下一个最便宜的方格并尝试从它移动到价格更大的所有相邻方格。

在你的问题中，你有一个额外的自由度：你的广场的海拔高度。也就是说，当你移动到一个正方形时，你可以改变它的高度。

最直接的“蛮力”解决方案如下：

  1. 检查所有单元格，建立一组它们的海拔高度（即所有高度的频谱）。假设你有H个不同的高度。
  2. 将正方形的状态定义为其位置和高度。根据 Dijkstra 图定义您的问题。
  3. 对于每个正方形，在图形中添加一个表示其实际高程的顶点。然后添加额外的顶点，以更大的高度表示它（除了源和目标方块）。这样每个正方形最多有H个顶点。
  4. 将每个顶点的内部价格定义为高于其实际位置的高度。因此，对于每个正方形，您都有一个内部价格=0（实际高程）的顶点，加上代表具有适当内部价格的高架位置的顶点数。
  5. 通过有向边表示相邻正方形的连接顶点。仅当源顶点具有至少目标顶点的高程时才放置边。

然后通过 Dijkstra（或 A*）算法找到最短路径。移动的成本被认为是目标顶点的内部价格（我们的边不携带价格）。

简单来说，我们构建了一个“分层”图，每一层对应一个可选的高度。在每个位置，您都可以在当前层移动或降低。

不用说，问题的复杂性增加了。顶点数增加（最多）H倍，边数也是如此。

基本上，路径搜索具有复杂性，log(N) * N * M其中N是单元格计数的平方，M - 是连接顺序（连接的最近邻居的数量）。在您的通货膨胀之后，复杂性会增加（最多）H^2的因子。

因此，该算法的效率取决于不同高度的数量。如果您的高度数量很少 - 该算法应该是有效的。但是，如果您所有的正方形都有不同的高度 - 也许应该使用另一种方法。

于 2012-05-19T21:21:47.920 回答
1

这是另一个维度的简单最短距离问题的示例，尝试像这样制定问题，cost[n][m][max_height] = {INFINITY};

成本[srcX][srcY][高度[srcX][srcY]] = 0;

现在 q_ht 的 cost[x+1][y][ht] = min(cost[x+1][y][ht], cost[x][y][q_ht] + (q_ht - 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 回答