1

ユーザー指定の頂点から開始し、特定の距離を移動した後に同じ頂点で終了するように、頂点と重み付けされたエッジのグラフをトラバースする必要がある C++ プログラムに取り組んでいます。これをコードで実装する方法はわかりませんが、これまでのところ次のとおりです。

void DijkstrasShortestPath()
{
    while (vertices.size() != 0)
    {
        Vertex* u = extract_min(vertices);
        vector<Vertex*>* adjVertex = AdjVertices(u);

        const int size = adjVertex->size();
        for (int i=0; i<size; ++i)
        {
            Vertex* v = adjVertex->at(i);
            int distance = travel_dist(u, v) +
                u->distFromStart;

            if (distance < v->distFromStart)
            {
                v->distFromStart = distance;
                v->previous = u;
            }
        }
        delete adjVertex;
    }
}

Vertex* extract_min(vector<Vertex*>& vertices)
{
    int size = vertices.size();
    if (size == 0) {
        return NULL;
    }
    int minimum = 0;
    Vertex* min = vertices.at(0);
    int i = 0;
    for( i=1; i<size; ++i)
    {
        Vertex* temp = vertices.at(i);
        if( temp->distFromStart < min->distFromStart) {
            min = temp;
            minimum = i;
        }
    }
    vertices.erase(vertices.begin() + minimum);
    return min;
}

vector <Vertex*>* AdjVertices(Vertex* vert)
{
    vector<Vertex*>* adjVertex = new vector <Vertex*> ();
    const int size = edges.size();
    for(int i=0; i<size; ++i)
    {
        Edge* edge = edges.at(i);
        Vertex* adjacent = NULL;
        if (edge->intersection1 == vert)
        {
            adjacent = edge->intersection2;
        }
        else if (edge->intersection2 == vert)
        {
            adjacent = edge->intersection1;
        }
        if (adjacent && vertices_check(vertices, adjacent))
        {
            adjVertex->push_back(adjacent);
        }
    }
    return adjVertex;
}

int travel_dist(Vertex* u, Vertex* v)
{
    const int size = edges.size();
    for(int i=0; i<size; ++i)
    {
        Edge* edge = edges.at(i);
        if (edge->street_connection(u, v))
        {
            return edge->distance;
        }
    }
    return -1;
}

bool vertices_check(vector<Vertex*>& vertices, Vertex* vert)
{
    const int size = vertices.size();
    for(int i=0; i<size; ++i)
    {
        if (vert == vertices.at(i))
        {
            return true;
        }
    }
    return false;
}

これは本質的にダイクストラの最短パス アルゴリズムですが、これはまさに私が望んでいるものではありません。私がやろうとしているのは、距離がユーザー指定の距離の 1 単位以内で、同じ頂点で開始および終了するルートをプログラムに計算させることです。私が持っているものを変えることでそれを行う方法はありますか？

これは、ダイクストラのアルゴリズムではなく、幅優先検索または深さ優先検索を必要としますか?

4

2 に答える 2

1

ダイクストラのアルゴリズムは、開始ノードから他のノードへの最短パスのみを保存します。代わりに必要なのは、ノードにつながるすべてのパスを追跡することです。それらがある場合は、ノードへの新しいパスを見つけるたびに、その長さと新しいパスの長さがユーザー指定の距離の1単位以内にあるパスが以前に見つかったかどうかを確認できます。次に、一方のパスを前方に、もう一方のパスを後方に歩くと、ループが発生します。

于 2012-12-05T09:01:59.323 に答える
0

考えられる方法の1つ。

境界のあるbest-first search.

Pこれまでに作成されたループの長さとともに、潜在的なループを形成するノードのリストを格納する構造体を作成します。

リンク先Sのノードごとに個別の P 構造を作成することにより、指定された頂点で検索を開始します。Sこれらの P 構造を、P 構造によって記述されたパスの長さによってソートされる優先キューに追加します。

これらのノードのそれぞれが順番に優先キューから P 構造を削除し、それらの P 構造をコピーし、リンク先のノードを追加することを検討してください。追加するノードが P 構造に既に存在し、そうでない場合はS、構造を破棄し、そのルートを考慮しません。同様に、指定された cost を超えるパスがある場合は、Cそのパスを破棄し、それ以上考慮しません。パスが破棄されていない場合は、関連する P 構造を優先キューに追加します。

SP 構造に 2 回出現し、P 構造によって記述されたパスの長さが許容範囲内にある場合、正常に終了します。そうでない場合は、priortiy-queue が空になるまで検索を続けます。

許容ヒューリスティックを使用して特定のノードから までの距離を推定し、Sこれを進行中のパスの確立されたコストに追加し、合計を優先キューのソート キーとして使用することで、アルゴリズムを高速化できる場合があります。このようなヒューリスティックは、A* アルゴリズムの中心にあり、興味があるかもしれません。

これは明らかですか？そうでない場合は、短いサンプル コードを記述できます。

于 2012-12-06T01:02:07.043 に答える