7

HoffmanPavleyRankedShortestPathAlgorithmQuickGraph であまり多くのドキュメントを見つけられなかったので、ここでは少し長めのショットです 。そのため、多くの人が使用していないと推測していますが、ランク付けされた最短パスで正しい結果を返す問題がいくつかあります。アルゴリズムと、誰かが同じ問題を見つけたのだろうか。

1900 個の頂点と 20000 個のエッジを使用して BiDirectional グラフを生成し、150 個のパスを返すようにグラフを設定しました。これは実行されますが、予想されるいくつかのパス、つまり上位 20 の最短パスにランク付けされるパスは返されません。私がシステムに期待するのは、150 のパスを要求すると、150 の最短パスが順番に返されるということです。

ここで、1000 を超えるパスを返すように設定すると、予想されるパスが表示されます。誰かが以前にこのような問題に遭遇したことがあり、グラフの設定を改善する方法があるかもしれませんか? 処理に時間がかかりすぎるため、システムに 1000 パスを返させることはできません。

関連するコードは次のとおりです。 グラフのセットアップ:

BidirectionalGraph<string, TaggedEdge<string, int>> pathGraph = new BidirectionalGraph<string, TaggedEdge<string, int>>();

... add vertices and edges

アルゴリズムのセットアップ:

HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, int>> hoffmanAlgorithm = new HoffmanPavleyRankedShortestPathAlgorithm<string, TaggedEdge<string, int>>(pathGraph, E => 1.0);
try
{
    hoffmanAlgorithm.ShortestPathCount = 150;
    hoffmanAlgorithm.SetRootVertex(startPoint.ToString());
    hoffmanAlgorithm.Compute(startPoint.ToString(), endPoint.ToString());

    foreach (IEnumerable<TaggedEdge<string, int>> path in hoffmanAlgorithm.ComputedShortestPaths)
    {
         //process results...
    }
}

私が言ったように、私はここで反応を得られる自信があまりありませんが、とにかく試してみようと思いました. CodePlex の QuickGraph ディスカッション フォーラムには、もう人がいないようです。

どうもありがとう

4

0 に答える 0