c++ - テキスト入力からの最短経路アルゴリズム

Question

私はこの最短経路問題を解こうとしてきましたが、私が試みていた方法がほぼ完全に間違っていて、それを完了する方法がまったくわからないことに気付きました。

この質問では、入力のテキストファイルを指定して、ある地点から別の地点までの最短経路を見つける必要があります。

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 を比較します。両方の値が同じ場合、残りの作業が台無しになるという問題に遭遇しました。

これが意味をなすことを願っています。

使用するアルゴリズムまたはサンプルコードに関する提案は大歓迎です。

score 1 · Accepted Answer

データファイルが次の形式の 2D 配列に読み込まれると仮定します。

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

X は何でもかまいません。このため、正の重みを想定しているため、レベルを「下る」パスを考慮する必要はありません。

一般に、最小コストは次の 2 つのコストのいずれか小さい方であると言えます
。
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] を使用し、アルゴリズム全体がステートマシンになるようにアルゴリズムを書き直すこともできます。

ダイクストラのアルゴリズムを使用してこれを解決することもできますが、それは核弾頭でハエを殺すようなものです。

score 0 · Accepted Answer

アルゴリズムの単純なバージョンのアイデアは次のとおりです。

頂点(滞在できる場所) とエッジ(できる散歩)のリストを定義する
すべての頂点には、それを他の頂点に接続するエッジのリストがあります
すべてのエッジストアのウォーク長
すべての頂点に対して、「ここまでの距離」という意味の 1000000000 のフィールドを格納します
開始点だけで初期化された「アクティブな」頂点のリストを作成する
開始頂点の徒歩距離フィールドを 0 に設定します (ここにいます)

検索アルゴリズムは次のように進みます。

(a)「アクティブなリスト」から最低の頂点を選択しwalk_distance、リストから削除します
頂点が目的地の場合は完了です。
それ以外の場合は、その頂点の各エッジについて、other_vertexasまでの徒歩距離を計算します。

new_dist = vertex.walk_distance + edge.length
新しい距離がより短いかどうかを確認other_vertex.walk_distanceし、この場合は新しい値に更新other_vertex.walk_distanceし、その頂点がまだそこにない場合は「アクティブリスト」に入れます。
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必要なエッジ (階段ごとに 1 つ、フロアウォークごとに 1 つ) があることがわかります。

最後のフロアを除く各フロアには、3 つのエッジを構築する必要があります。最後のフロアには 1 つだけです。

また、最初にすべてのエッジと頂点をベクトルに割り当て、後でポインターを修正します (構築後のセットアップはアンチパターンですが、再割り当ての問題を回避し、物事を非常にシンプルに維持するためです)。

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右側の

アルゴリズム：

初期化l=0しr=1000000000、左側にいるように
すべての中間ステップで、3 つの距離を読み取ります。

a左下から右上への階段の長さ

b床の長さです

cは、右下から左上への階段の長さです
walk_distance次のフロアの左側と右側を計算します

Lr+cとの間の最小値ですl+b+c(右側から上に行くか、左側から最初にそこに行きます)

Rl+aとの間の最小値ですr+b+a(左から開始するか、右から開始して最初に床を横切ります)
最後のステップでは、最後のフロアを横切っrてそこから来るまでの最小値を選択する必要がありますl

c++ - テキスト入力からの最短経路アルゴリズム

4 に答える 4

編集

Related

Reference