1

グラフは重み付けされておらず、HashSets neighbours[] の配列の要素はノード neighbours[1] はノード 1 (0 から始まることに注意してください) であり、一意の隣接ノードは 2 3 4 5 となります (したがって、neighbours[5] 1) が含まれます。そして、理論をはるかに超えるアルゴリズムを取得できないため、多大な助けを借りて行った次の方法があります。返される数値は、グラフ内の 2 つのノード間の平均距離である必要があります。

次のグラフがあると想像してください (ノード: in_links | out_links; neighbours[] には、ノード 0 に 0 ループが含まれておらず、前述のように重複もありません。)

0: 0 0 0 | 0 0 0 1 1 1 2 3 5 6 7 7 8 8 9 9 11 
1: 0 0 0 | 2 2 3 4 4 5 6 8 
2: 0 1 1 | 3 
3: 0 1 2 | 4 9 
4: 1 1 3 | 5 12 
5: 0 1 4 | 6 7 10 
6: 0 1 5 | 10 11 12 
7: 0 0 5 | 
8: 0 0 1 | 10 
9: 0 0 3 | 12 
10: 5 6 8 | 11 
11: 0 6 10 | 
12: 4 6 9 |

そして、この自明なグラフでは、返される距離は 5.781686749230769E8 ?!?! です。コード：

    public double getAvgDistance() {
    double total = 0;
    int[] dist = new int[n];
    ArrayList<Integer> Q = new ArrayList<Integer>();
    int tmp, index = 0, w = 0;

    for (int u=0; u<n; u++) {
        System.out.print("Avg Dist at "+u+"\r");
        // Initialise Q and dist for this iteration
        for (int v=u+1; v<n; v++) {
            Q.add(v);

            if (neighbours[u].contains(v)) {
                dist[v] = 1;
            } else {
                dist[v] = Integer.MAX_VALUE;
            }
        }

        while (!Q.isEmpty()) {

            tmp = dist[0];
            for (int e=1; e<Q.size(); e++) {
                if (dist[e] < tmp) {
                    w = Q.get(e);
                    tmp = dist[w]; // smallest dist is for this element w so far
                    index = e;
                }
            }
            Q.remove(index);

            for (int z : neighbours[w]) {
                if ( Q.contains(z)
                        && (dist[w]+1 < dist[z]) ) {

                    dist[z] = dist[w]+1;
                }
            }

        } // while end

        for (int v = u+1; v < n; v++ ) {
            total += dist[v];
        }

    } // for 0-n end

    return total /= (double)(n*(n-1)/2);
}

私は実数のキャストや印刷の経験があまりないので、それらと関係があることを願っています! すべてのコメントを歓迎

4

3 に答える 3

1

あなたの質問を正しく理解できれば、ノード 7、11、および 12 にはアウト リンクがないため、他のノードへの有効なパスはありません。

これらの場合、アルゴリズムは Integer.MAX_VALUE のコストでリンクを挿入することによってパスを強制しますか? もしそうなら、平均コストが非常に高い理由が説明できます。

また、順路と逆路の両方を評価したほうがよいのではないかと考えました。有向グラフでは、パス AB のコストはパス BA のコストと必ずしも同じではありません。現在のアルゴリズムでは、ノード 12 で終了するすべてのパスのコストが計算されますが、ノード 12 で開始するパスは評価されません。

于 2010-07-11T14:24:39.843 に答える
0

あなたの質問を完全に理解しているかどうかはわかりませんが、印刷している値が期待どおりではないことに問題があるようです。double の値を出力しているときに問題が発生する可能性があると思われます。double を String に直接変換すると、予期しない結果が得られることがわかっています。

この投稿では、double の代わりに BigDecimal を使用して精度を維持することを提案しています: Retain precision with double in Java

したがって、次のようなことを試して、より良い結果が得られるかどうかを確認してください。

BigDecimal.valueOf(<your double value here>).toPlainString();
于 2010-07-09T16:30:17.063 に答える
0

推測ですが、ときどき距離が に設定されているのを見ますInteger.MAX_VALUE。これらの数値が実際に結果に入力され、10 の 1 つまたは 2 つの係数で除算されている場合、平均が予想よりもはるかに大きく、MAX_VALUE とほぼ同じ球場にある理由が非常にうまく説明されます。

代替案の中から最短経路を決定するためにグラフを使用する場合、この大きな値をグラフに表示しても問題ありませんが、実際の距離を決定するポイントに到達すると、その数値は失われます!

MAX_VALUE の球場にパスの長さがあるか、つまりパスがないと言っています。したがって、そのパスの長さは平均に入りません。または、パスの長さがグラフ内の距離と同じ大きさの小さな整数である場合、それは有効であり、計算に含めることができます。

このことから得られる教訓: 数値がコンピューター プログラムから出たからといって、それが信頼できる、または正しいとは限りません。

于 2010-07-11T14:33:55.343 に答える