2

我一直在尝试解决这个最短路径问题，我意识到我尝试解决它的方式几乎完全错误，而且我不知道要完成它。

该问题要求您在给定输入文本文件的情况下找到从一个点到另一个点的最短路径。

The input looks like this with the first value representing how many levels there are.

4  
14 10 15  
13 5 22  
13 7 11  
5

This would result in an answer of: 14+5+13+11+5=48

代表这样的图表

该问题要求从左下角到右上角的最短路径。

我尝试这样做的方法是比较可能的任一路径的值，然后将它们加到总和中。例如，我提供的输入的第一步是将 14 与 10 + 15 进行比较。我遇到的问题是，如果两个值相同，它将填满其余的工作。

我希望这有点道理。

任何关于使用算法或任何示例代码的建议将不胜感激。

4

4 回答 4

1

我的第一个想法是用矩阵表示图形，然后运行 ​​DFS 或 Dijkstra 来解决它。但是对于这个给定的问题，我们可以做得更好。

因此，这是一个在 O(n) 中运行的问题的可能解决方案。2*i表示 level 的左节点，表示 leveli的2*i+1右节点i。阅读此解决方案中的注释以获取解释。

#include <stdio.h>

struct node {
    int lup; // Cost to go to level up
    int stay; // Cost to stay at this level
    int dist; // Dist to top right node
};


int main() {
    int N;
    scanf("%d", &N);

    struct node tab[2*N];


    // Read input.
    int i;
    for (i = 0; i < N-1; i++) {
        int v1, v2, v3;
        scanf("%d %d %d", &v1, &v2, &v3);
        tab[2*i].lup = v1;
        tab[2*i].stay = tab[2*i+1].stay = v2;
        tab[2*i+1].lup = v3;
    }
    int v;
    scanf("%d", &v);
    tab[2*i].stay = tab[2*i+1].stay = v;


    // Now the solution:

    // The last level is obvious:
    tab[2*i+1].dist = 0;
    tab[2*i].dist = v;

    // Now, for each level, we compute the cost.
    for (i = N - 2; i >= 0; i--) {
        tab[2*i].dist = tab[2*i+3].dist + tab[2*i].lup;
        tab[2*i+1].dist = tab[2*i+2].dist + tab[2*i+1].lup;

        // Can we do better by staying at the same level ?
        if (tab[2*i].dist > tab[2*i+1].dist + tab[2*i].stay) {
            tab[2*i].dist = tab[2*i+1].dist + tab[2*i].stay;
        }
        if (tab[2*i+1].dist > tab[2*i].dist + tab[2*i+1].stay) {
            tab[2*i+1].dist = tab[2*i].dist + tab[2*i+1].stay;
        }
    }

    // Print result
    printf("%d\n", tab[0].dist);

    return 0;
}

（此代码已在给定示例中进行了测试。）

于 2013-09-15T09:16:19.120 回答
1

假设您的数据文件被读入以下形式的二维数组：

int weights[3][HEIGHT] = {
  {14, 10, 15},
  {13, 5, 22},
  {13, 7, 11},
  {X, 5, X}
};

X可以是任何东西，没关系。为此，我假设权重为正，因此永远不需要考虑“下降”一个级别的路径。

一般来说，您可以说最小成本是以下 2 个成本中的较小者：
1) 上升一个级别的成本：从下面 1 个级别到对面的路径的成本，加上上来的成本。
2) 穿越一个关卡的成本：从同一关卡到相反的路径的成本，加上穿越的成本。

int MinimumCost(int weight[3][HEIGHT]) {
  int MinCosts[2][HEIGHT]; // MinCosts[0][Level] stores the minimum cost of reaching
                           // the left node of that level
                           // MinCosts[1][Level] stores the minimum cost of reaching
                           // the right node of that level

  MinCosts[0][0] = 0; // cost nothing to get to the start
  MinCosts[0][1] = weight[0][1]; // the cost of moving across the bottom

  for (int level = 1; level < HEIGHT; level++) {
     // cost of coming to left from below right
     int LeftCostOneStep = MinCosts[1][level - 1] + weight[2][level - 1];
     // cost of coming to left from below left then across
     int LeftCostTwoStep = MinCosts[0][level - 1] + weight[0][level - 1] + weight[1][level];
     MinCosts[0][level] = Min(LeftCostOneStep, LeftCostTwoStep);

     // cost of coming to right from below left
     int RightCostOneStep = MinCosts[0][level - 1] + weight[0][level - 1];
     // cost of coming to right from below right then across
     int RightCostTwoStep = MinCosts[1][level - 1] + weight[1][level - 1] + weight[1][level];
     MinCosts[1][level] = Min(RightCostOneStep, RightCostTwoStep);

  }

  return MinCosts[1][HEIGHT - 1];
}

我没有仔细检查语法，请仅使用它来大致了解如何解决问题。您还可以重写算法，以便 MinCosts 使用常量内存 MinCosts[2][2] 并且您的整个算法可以成为状态机。

您也可以使用 dijkstra 的算法来解决这个问题，但这有点像用核弹头杀死苍蝇。

于 2013-09-15T09:07:42.363 回答
1

使用深度优先搜索并仅添加最小值。然后检查哪一边是最短的楼梯。如果是图问题，请查看有向图。对于每个楼梯，您需要 2 个顶点。从梯子到梯子的成本可以是别的东西。

于 2013-09-15T07:09:02.380 回答
0

该算法的简单版本的想法如下：

  • 定义一个顶点列表（你可以停留的地方）和边（你可以走）
  • 每个顶点都有一个连接到其他顶点的边列表
  • 对于每个边缘存储步行长度
  • 对于每个顶点存储一个 1000000000 的字段，其含义是“步行到这里需要多长时间”
  • 创建仅使用起点初始化的“活动”顶点列表
  • 将起始顶点的步行距离字段设置为 0（你在这里）

现在搜索算法进行如下

  1. 从“活动列表”中选择最低的（a）顶点walk_distance并将其从列表中删除
  2. 如果顶点是你完成的目的地。

  3. other_vertex否则，对于该顶点中的每条边，计算到as的步行距离

    new_dist = vertex.walk_distance + edge.length

  4. 检查新距离是否短于other_vertex.walk_distance，在这种情况下更新other_vertex.walk_distance为新值，如果该顶点不存在，则将该顶点放入“活动列表”中。

  5. 从 1 重复

如果您用完活动列表中的节点并且从未处理过目标顶点，则意味着无法从起始顶点到达目标顶点。

对于 C++ 中的数据结构，我会使用类似的东西

struct Vertex {
    double walk_distance;
    std::vector<struct Edge *> edges;
    ...
};

struct Edge {
    double length;
    Vertex *a, *b;
    ...
    void connect(Vertex *va, Vertex *vb) {
        a = va; b = vb;
        va->push_back(this); vb->push_back(this);
    }
    ...
};

然后从输入中我知道，对于n级别，需要2*n顶点（每个楼层的左侧和右侧）和2*(n-1) + n边缘（每个楼梯一个，每个楼层步行一个）。

对于除最后一层外的每一层，您需要构建三个边缘，对于最后一层只有一个。

我还会先在向量中分配所有边和顶点，然后再修复指针（构建后设置是一种反模式，但这里是为了避免重新分配问题并且仍然保持非常简单）。

int n = number_of_levels;

std::vector<Vertex> vertices(2*n);
std::vector<Edge> edges(2*(n-1) + n);

for (int i=0; i<n-1; i++) {
    Vertex& left = &vertices[i*2];
    Vertex& right = &vertices[i*2 + 1];
    Vertex& next_left = &vertices[(i+1)*2];
    Vertex& next_right = &vertices[(i+1)*2 + 1];
    Edge& dl_ur = &edges[i*3];   // down-left to up-right stair
    Edge& dr_ul = &edges[i*3+1]; // down-right to up-left stair
    Edge& floor = &edges[i*3+2];

    dl_ur.connect(left, next_right);
    dr_ul.connect(right, next_left);
    floor.connect(left, right);
}

// Last floor
edges.back().connect(&vertex[2*n-2], &vertex[2*n-1]);

注意：未经测试的代码

编辑

当然，这个算法可以解决一个更普遍的问题，即顶点和边的集合是任意的（但长度是非负的）。

对于非常具体的问题，可以使用更简单的算法，它甚至不需要任何数据结构，而是可以在读取输入时动态计算结果。

#include <iostream>
#include <algorithm>

int main(int argc, const char *argv[]) {
    int n; std::cin >> n;
    int l=0, r=1000000000;
    while (--n > 0) {
        int a, b, c; std::cin >> a >> b >> c;
        int L = std::min(r+c, l+b+c);
        int R = std::min(r+b+a, l+a);
        l=L; r=R;
    }
    int b; std::cin >> b;
    std::cout << std::min(r, l+b) << std::endl;
    return 0;
}

这个解决方案的想法很简单：

  • l变量是walk_distance地板左侧的
  • r变量是walk_distance右侧的

算法：

  1. 我们初始化l=0，r=1000000000因为我们在左侧

  2. 对于所有中间步骤，我们读取三个距离：

    a是从左下到右上楼梯的长度

    b是地板的长度

    c是从右下到左上楼梯的长度

  3. 我们计算walk_distance下一层的左侧和右侧

    Lr+c是和之间的最小值l+b+c（要么我们从右侧开始，要么我们先从左侧开始）

    Rl+a是和之间的最小值r+b+a（要么我们从左边开始，要么我们从右边开始，然后先穿过地板）

  4. 对于最后一步，我们只需要通过穿过最后一层来选择r从那里到那里的最小值l

于 2013-09-15T08:12:24.467 回答